这是一个合理且符合惯用法的GoLang循环移位实现吗?

huangapple go评论93阅读模式
英文:

Is this a reasonable and idiomatic GoLang circular shift implementation?

问题

有人能否评论一下这种在Go语言中实现整数数组的循环移位的方式是否合理和惯用?(我故意选择不使用位运算。)

如何改进这个实现?

package main

import "fmt"

func main() {
    a := []int{1,2,3,4,5,6,7,8,9,10}
    fmt.Println(a)
    rotateR(a, 5)
    fmt.Println(a)
    rotateL(a, 5)
    fmt.Println(a)
}

func rotateL(a []int, i int) {
    for count := 1; count <= i; count++ {
        tmp := a[0]
        for n := 1;n < len(a);n++ {
            a[n-1] = a[n]
        }
        a[len(a)-1] = tmp
    }
}

func rotateR(a []int, i int) {
    for count := 1; count <= i; count++ {
        tmp := a[len(a)-1]
        for n := len(a)-2;n >=0 ;n-- {
            a[n+1] = a[n]
        }
        a[0] = tmp
    }
}
英文:

Can anyone comment on whether this is a reasonable and idiomatic way of implementing circular shift of integer arrays in Go? (I deliberately chose not to use bitwise operations.)

How could it be improved?

package main

import &quot;fmt&quot;

func main() {
	a := []int{1,2,3,4,5,6,7,8,9,10}
	fmt.Println(a)
	rotateR(a, 5)
	fmt.Println(a)
	rotateL(a, 5)
	fmt.Println(a)
}

func rotateL(a []int, i int) {
	for count := 1; count &lt;= i; count++ {
		tmp := a[0]
		for n := 1;n &lt; len(a);n++ {
			a[n-1] = a[n]
		}
		a[len(a)-1] = tmp
	}
}

func rotateR(a []int, i int) {
	for count := 1; count &lt;= i; count++ {
		tmp := a[len(a)-1]
		for n := len(a)-2;n &gt;=0 ;n-- {
			a[n+1] = a[n]
		}
		a[0] = tmp
	}
}

答案1

得分: 5

逐个位置旋转切片,并重复此过程以获得所需的总旋转次数,这意味着所需的时间与“旋转距离”ד切片长度”成正比。通过直接将每个元素移动到其最终位置,您可以在时间上仅与切片长度成正比来完成此操作。

这段代码比您的代码要复杂一些,您需要一个GCD函数来确定需要遍历切片的次数:

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    
    return a
}

func rotateL(a []int, i int) {

    // 确保移动量小于数组长度,并且为正数。
    i = i % len(a)
    if i < 0 {
        i += len(a)
    }

    for c := 0; c < gcd(i, len(a)); c++ {

        t := a[c]

        j := c

        for {
            k := j + i
            // 如果超过切片末尾,则循环回到开头
            if k >= len(a) {
                k -= len(a)
            }
            // 当回到起始位置时结束
            if k == c {
                break
            }
            // 直接将元素移动到其最终位置
            a[j] = a[k]
            j = k
        }

        a[j] = t
    }
}

将大小为_l_的切片向右旋转_p_个位置等效于将其向左旋转_l_ - _p_个位置,因此您可以通过使用rotateL来简化rotateR函数:

func rotateR(a []int, i int) {
    rotateL(a, len(a) - i)
}
英文:

Rotating the slice one position at a time, and repeating to get the total desired rotation means it will take time proportional to rotation distance × length of slice. By moving each element directly into its final position you can do this in time proportional to just the length of the slice.

The code for this is a little more tricky than you have, and you’ll need a GCD function to determine how many times to go through the slice:

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a % b
	}
	
	return a
}

func rotateL(a []int, i int) {

    // Ensure the shift amount is less than the length of the array,
    // and that it is positive.
    i = i % len(a)
    if i &lt; 0 {
        i += len(a)
    }

	for c := 0; c &lt; gcd(i, len(a)); c++ {

		t := a[c]

		j := c

		for {
			k := j + i
			// loop around if we go past the end of the slice
			if k &gt;= len(a) {
				k -= len(a)
			}
			// end when we get to where we started
			if k == c {
				break
			}
			// move the element directly into its final position
			a[j] = a[k]
			j = k
		}

		a[j] = t
	}
}

Rotating a slice of size l right by p positions is equivalent to rotating it left by lp positions, so you can simplify your rotateR function by using rotateL:

func rotateR(a []int, i int) {
	rotateL(a, len(a) - i)
}

答案2

得分: 2

你的代码对于原地修改是没问题的。

我不太明白你所说的位运算是什么意思。也许这段代码可以帮到你:

package main

import "fmt"

func main() {
    a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    fmt.Println(a)
    rotateR(&a, 4)
    fmt.Println(a)
    rotateL(&a, 4)
    fmt.Println(a)
}

func rotateL(a *[]int, i int) {
    x, b := (*a)[:i], (*a)[i:]
    *a = append(b, x...)
}

func rotateR(a *[]int, i int) {
    x, b := (*a)[:(len(*a)-i)], (*a)[(len(*a)-i):]
    *a = append(b, x...)
}

代码在这里可以运行:https://play.golang.org/p/0VtiRFQVl7

在Go语言中,这被称为重新切片(reslicing)。你的代码中复制和循环的开销相对较大,而重新切片则需要动态分配内存。这是你的选择,但是如果要将一个包含10000个元素的数组向右移动一个位置,重新切片看起来更加高效。

英文:

Your code is fine for in-place modification.

Don't clearly understand what you mean by bitwise operations. Maybe this

package main

    import &quot;fmt&quot;
    
    func main() {
    	a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    	fmt.Println(a)
    	rotateR(&amp;a, 4)
    	fmt.Println(a)
    	rotateL(&amp;a, 4)
    	fmt.Println(a)
    }
    
    func rotateL(a *[]int, i int) {
    	x, b := (*a)[:i], (*a)[i:]
    	*a = append(b, x...)
    }
    
    func rotateR(a *[]int, i int) {
    	x, b := (*a)[:(len(*a)-i)], (*a)[(len(*a)-i):]
    	*a = append(b, x...)
    }

Code works https://play.golang.org/p/0VtiRFQVl7

It's called reslicing in Go vocabulary. Tradeoff is coping and looping in your snippet vs dynamic allocation in this. It's your choice, but in case of shifting 10000 elements array by one position reslicing looks much cheaper.

答案3

得分: 0

我喜欢Uvelichitel的解决方案,但如果你想要模数算术,它的复杂度将是O(n)。

package main

import "fmt"

func main() {
    s := []string{"1", "2", "3"}
    rot := 5
    fmt.Println("Before RotL", s)
    fmt.Println("After RotL", rotL(rot, s))
    fmt.Println("Before RotR", s)
    fmt.Println("After RotR", rotR(rot, s))
}

func rotL(m int, arr []string) []string {
    newArr := make([]string, len(arr))

    for i, k := range arr {
        newPos := (((i - m) % len(arr)) + len(arr)) % len(arr)
        newArr[newPos] = k
    }

    return newArr
}

func rotR(m int, arr []string) []string {
    newArr := make([]string, len(arr))

    for i, k := range arr {
        newPos := (i + m) % len(arr)
        newArr[newPos] = k
    }

    return newArr
}

以上是你提供的代码。

英文:

I like Uvelichitel solution but if you would like modular arithmetic which would be O(n) complexity

package main
func main(){
   s := []string{&quot;1&quot;, &quot;2&quot;, &quot;3&quot;}
   rot := 5
   fmt.Println(&quot;Before RotL&quot;, s)
   fmt.Println(&quot;After RotL&quot;, rotL(rot, s))
   fmt.Println(&quot;Before RotR&quot;, s)
   fmt.Println(&quot;After RotR&quot;, rotR(rot,s))

}
func rotL(m int, arr []string) []string{
     newArr := make([]string, len(arr))

     for i, k := range arr{
	     newPos := (((i - m) % len(arr)) + len(arr)) % len(arr)
	     newArr[newPos] = k
     }

     return newArr
}

func rotR(m int, arr []string) []string{

     newArr := make([]string, len(arr))

     for i, k := range arr{
	     newPos := (i + m) % len(arr)
	     newArr[newPos] = k
      }
      return newArr
}

答案4

得分: 0

如果您需要输入多个值,无论您想要什么(更新代码Uvelichitel)

package main

import "fmt"

func main() {
    var N, n int
    fmt.Scan(&N)
    a := make([]int, N)
    for i := 0; i < N; i++ {
        fmt.Scan(&a[i])
    }
    fmt.Scan(&n)
    if n > 0 {
        rotateR(&a, n%len(a))
    } else {
        rotateL(&a, (n*-1)%len(a))
    }
    for _, elem := range a {
        fmt.Print(elem, " ")
    }
}

func rotateL(a *[]int, i int) {
    x, b := (*a)[:i], (*a)[i:]
    *a = append(b, x...)
}

func rotateR(a *[]int, i int) {
    x, b := (*a)[:(len(*a)-i)], (*a)[(len(*a)-i):]
    *a = append(b, x...)
}
英文:

If you need to enter multiple values, whatever you want (upd code Uvelichitel)

package main

import &quot;fmt&quot;

func main() {
	var N, n int
	fmt.Scan(&amp;N)
	a := make([]int, N)
	for i := 0; i &lt; N; i++ {
		fmt.Scan(&amp;a[i])
	}
	fmt.Scan(&amp;n)
	if n &gt; 0 {
		rotateR(&amp;a, n%len(a))
	} else {
		rotateL(&amp;a, (n*-1)%len(a))
	}
	for _, elem := range a {
		fmt.Print(elem, &quot; &quot;)
	}
}

func rotateL(a *[]int, i int) {
	x, b := (*a)[:i], (*a)[i:]
	*a = append(b, x...)
}

func rotateR(a *[]int, i int) {
	x, b := (*a)[:(len(*a)-i)], (*a)[(len(*a)-i):]
	*a = append(b, x...)
}

huangapple
  • 本文由 发表于 2015年10月11日 06:04:59
  • 转载请务必保留本文链接:https://go.coder-hub.com/33059420.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定