Java Collections.shuffle fait quoi?

StackOverflow https://stackoverflow.com/questions/2249520

  •  20-09-2019
  •  | 
  •  

Question

Je me suis récemment trouvé devant être sûr que ma liste n'a pas été dans l'ordre. Mise en veille prolongée a été assez gentil pour le retourner en parfait état. Mise en veille prolongée idiot, ne pas lire mon esprit.

Je regardais mon API Java et il me dit sa méthode de lecture aléatoire fait ceci:

permute aléatoirement la liste spécifiée en utilisant une source de défaut de caractère aléatoire.

Être le george curieux que je suis, je veux savoir ce que cela signifie exactement. Y at-il un cours de mathématiques que je peux apprendre cela? Puis-je voir le code? Java, qu'est-ce que tu fais à mon ArrayList?!?!?

Pour être plus précis, les concepts mathématiques sont utilisés ici?

Était-ce utile?

La solution

Oui, vous pouvez regarder le code; il fait essentiellement un Fisher-Yates lecture aléatoire. Ici, il est (grâce OpenJDK, et youpi pour :-P open source): 

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

Le procédé d'échange: 

 private static void swap(Object[] x, int a, int b) {
    Object t = x[a];
    x[a] = x[b];
    x[b] = t;
}
scroll top