[arrays] Go에서 배열 셔플

Question 1

다음 Python 코드를 Go로 번역하려고했습니다.

import random

list = [i for i in range(1, 25)]
random.shuffle(list)
print(list)

하지만 셔플 기능이없고 인터페이스를 구현하고 유형을 변환해야했기 때문에 Go 버전이 길고 어색하다는 것을 알았습니다.

내 코드의 관용적 Go 버전은 무엇입니까?

Question 2

목록은 1에서 25까지의 정수이므로 Perm 을 사용할 수 있습니다 .

list := rand.Perm(25)
for i, _ := range list {
    list[i]++
}

에 의해 주어진 순열을 사용하는 rand.Perm것은 모든 배열을 섞는 효과적인 방법입니다.

dest := make([]int, len(src))
perm := rand.Perm(len(src))
for i, v := range perm {
    dest[v] = src[i]
}

Question 3

dystroy의 대답 은 완벽하게 합리적이지만 추가 슬라이스를 할당하지 않고 셔플하는 것도 가능합니다.

for i := range slice {
    j := rand.Intn(i + 1)
    slice[i], slice[j] = slice[j], slice[i]
}

알고리즘에 대한 자세한 내용 은 이 Wikipedia 기사 를 참조하십시오. rand.Perm실제로 내부적으로도이 알고리즘을 사용합니다.

Question 4

1.10 이후 Go에는 공식 Fisher-Yates 셔플 기능이 포함되어 있습니다.

선적 서류 비치: pkg/math/rand/#Shuffle

수학 / 랜드 : 셔플 추가

Shuffle은 Fisher-Yates 알고리즘을 사용합니다.

이것은 새로운 API이기 때문에 Int31n분할을 피하는 훨씬 빠른 구현 을 사용할 수있는 기회를 제공합니다 .

결과적으로 는 별도의 초기화 루프가 필요하고 요소를 교체하기 위해 함수 호출을 사용 함에도 불구하고 BenchmarkPerm30ViaShuffle보다 약 30 % 빠릅니다 BenchmarkPerm30.

원본 CL 51891 참조

첫째로 주석 에 의해 shelll :

무작위로 시드하는 것을 잊지 마십시오. 그렇지 않으면 항상 동일한 주문을 받게됩니다.
예를 들면rand.Seed(time.Now().UnixNano()

예:

words := strings.Fields("ink runs from the corners of my mouth")
rand.Shuffle(len(words), func(i, j int) {
    words[i], words[j] = words[j], words[i]
})
fmt.Println(words)

Question 5

Evan Shaw의 답변 에는 사소한 버그가 있습니다. 가장 낮은 인덱스에서 최고에 조각을 통해 우리 반복 처리가 균일하게 (의사) 랜덤 셔플을 얻을 경우에 따라 같은 글 , 우리는 간격에서 임의의 정수를 선택해야합니다 [i,n) 반대로[0,n+1) .

이 구현은 더 큰 입력에 필요한 것을 수행하지만 더 작은 슬라이스의 경우 균일하지 않은 셔플을 수행합니다.

를 활용하려면 rand.Intn()다음을 수행 할 수 있습니다.

    for i := len(slice) - 1; i > 0; i-- {
        j := rand.Intn(i + 1)
        slice[i], slice[j] = slice[j], slice[i]
    }

Wikipedia 기사의 동일한 알고리즘을 따릅니다.

Question 6

다음 기능을 사용할 수도 있습니다.

func main() {
   slice := []int{10, 12, 14, 16, 18, 20}
   Shuffle(slice)
   fmt.Println(slice)
}

func Shuffle(slice []int) {
   r := rand.New(rand.NewSource(time.Now().Unix()))
   for n := len(slice); n > 0; n-- {
      randIndex := r.Intn(n)
      slice[n-1], slice[randIndex] = slice[randIndex], slice[n-1]
   }
}

Question 7

math/rand패키지를 사용할 때 소스를 설정하는 것을 잊지 마십시오

// Random numbers are generated by a Source. Top-level functions, such as
// Float64 and Int, use a default shared Source that produces a deterministic
// sequence of values each time a program is run. Use the Seed function to
// initialize the default Source if different behavior is required for each run.

그래서 Shuffle이것을 고려 하는 함수를 작성했습니다 .

import (
    "math/rand"
)

func Shuffle(array []interface{}, source rand.Source) {
    random := rand.New(source)
    for i := len(array) - 1; i > 0; i-- {
        j := random.Intn(i + 1)
        array[i], array[j] = array[j], array[i]
    }
}

그리고 그것을 사용하려면 :

source := rand.NewSource(time.Now().UnixNano())
array := []interface{}{"a", "b", "c"}

Shuffle(array, source) // [c b a]

사용하고 싶다면 여기 https://github.com/shomali11/util에서 찾을 수 있습니다.

Question 8

Raed의 접근 방식 은 []interface{}입력으로 인해 매우 유연하지 않습니다 . go> = 1.8에 대한 더 편리한 버전은 다음과 같습니다 .

func Shuffle(slice interface{}) {
    rv := reflect.ValueOf(slice)
    swap := reflect.Swapper(slice)
    length := rv.Len()
    for i := length - 1; i > 0; i-- {
            j := rand.Intn(i + 1)
            swap(i, j)
    }
}

사용 예 :

    rand.Seed(time.Now().UnixNano()) // do it once during app initialization
    s := []int{1, 2, 3, 4, 5}
    Shuffle(s)
    fmt.Println(s) // Example output: [4 3 2 1 5]

또한 약간의 복사가 약간의 의존성보다 낫다는 것을 잊지 마십시오.