tableau aléatoire dans Go

J'ai essayé de traduire le code Python suivant pour Aller

import random

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

Mais j'ai trouvé ma version Go longue et maladroite car il n'y a pas de fonction de lecture aléatoire et j'ai dû implémenter des interfaces et convertir des types.

Quelle serait une version go idiomatique de mon code?

69
demandé sur 0xcaff 2012-09-04 17:42:28

7 réponses

Que votre liste est juste les entiers de 1 à 25, vous pouvez utiliser Perm :

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

Notez que l'utilisation d'une permutation donnée par rand.Perm est un moyen efficace de mélanger n'importe quel tableau.

dest := make([]int, len(src))
perm := rand.Perm(len(src))
for i, v := range perm {
    dest[v] = src[i]
}
85
répondu Denys Séguret 2012-09-04 14:28:07

La réponse de Dystroy est parfaitement raisonnable, mais il est également possible de mélanger sans allouer de tranches supplémentaires.

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

Voir cet article de Wikipédia pour plus de détails sur l'algorithme. rand.Perm utilise également cet algorithme en interne.

94
répondu Evan Shaw 2017-05-23 12:03:01

Go 1.10 peut inclure une fonction officielleFisher-Yates shuffle .

Voir CL 51891:

Math / rand: ajouter Shuffle

Shuffle utilise L'algorithme de Fisher-Yates.

Comme il s'agit d'une nouvelle API, cela nous offre l'opportunité pour utiliser une implémentation Int31n beaucoup plus rapide qui évite principalement la division.

En conséquence, BenchmarkPerm30ViaShuffle est environ 30% plus rapide que BenchmarkPerm30, malgré la nécessité d'une boucle d'initialisation séparée et à l'aide de appels de fonction pour échanger des éléments.

Documentation: pkg/math/rand/#Shuffle

Exemple:

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)
18
répondu VonC 2018-02-13 10:05:01

Réponse de Evan Shaw a un bug mineur. Si nous parcourons la tranche de l'index le plus bas au plus haut, pour obtenir un aléatoire uniforme (pseudo) aléatoire, selon le même article , nous devons choisir un entier aléatoire à partir de l'intervalle [i,n) par opposition à [0,n+1).

Cette implémentation fera ce dont vous avez besoin pour des entrées plus grandes, mais pour des tranches plus petites, elle effectuera un shuffle non uniforme.

Utiliser rand.Intn(), nous pouvons faire:

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

Suivant le même algorithme de L'article Wikipedia.

6
répondu heranglo 2017-05-23 12:10:32

Peut-être que vous pouvez également utiliser la fonction suivante:

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]
   }
}
2
répondu hkucuk 2018-05-03 18:46:22

Lorsque vous utilisez le paquet math/rand, n'oubliez pas de définir une source

// 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.

J'ai donc écrit une fonction Shuffle qui prend cela en considération:

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]
    }
}

, Et pour l'utiliser:

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

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

Si vous souhaitez l'utiliser, vous pouvez le trouver ici https://github.com/shomali11/util

1
répondu Raed Shomali 2017-06-06 02:16:34

L'approche de Raed est très inflexible en raison de []interface{} en entrée. Voici une version plus pratique pour 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)
    }
}

Exemple d'utilisation:

    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]

Et aussi, n'oubliez pas que un peu de copie vaut mieux qu'un peu de dépendance

1
répondu Joseph Buchma 2017-07-24 06:53:12