Collections.shuffle () est-il vraiment assez aléatoire? Des exemples pratiques semblent nier cette affirmation

java.util.List 1 000 objects uniques, chacun faisant référence à une image, chaque image de la liste 1 000 est unique et j’aimerais maintenant les mélanger pour pouvoir utiliser les 20 premiers objects et les présenter. à l’utilisateur du site. L’utilisateur peut ensuite cliquer sur un bouton indiquant “Aléatoire”, et je récupère à nouveau les 1000 images à partir de zéro et j’appelle à nouveau shuffle() . Cependant, il semble que sur 1 000 objects d’image, je vois très souvent la même image encore et encore entre les 20 sélections d’images.

Quelque chose ne va pas, une meilleure suggestion, des conseils?

Mon code est très simple:

 List imagePaths = get1000Images(); Collections.shuffle(imagePaths); int i = 0; for (Ssortingng path: imagePaths) { ... do something with the path ... i++; if (i >= 20) break; } 

Je sais que Collections.shuffle() est bien dissortingbué: voir par exemple http://blog.ryanrampersad.com/2012/03/03/more-on-shuffling-an-array-correctly/

Cependant, j’ai juste le sentiment que la probabilité de voir la même image encore et encore dans un ensemble de 20 images sur 1 000 devrait être bien moindre …

Des intrants très appréciés.

Si vous montrez 20 images sur 1 000, la probabilité de voir l’une de ces 20 images répétées à la prochaine itération est d’environ 0,34; vous ne devriez donc pas être surpris de voir les images se répéter.

Les chances de voir une image spécifique sont toujours de une sur mille, mais si vous recherchez vingt images, les chances sont beaucoup plus grandes.

Nous pouvons calculer la probabilité qu’aucune des 20 images précédentes ne se répète:

  980 979 961 ———— × ——— × ... × ——— ≈ 0.66 1000 999 981 

Et donc la probabilité de voir une répétition est un moins ceci, ou approximativement 0.34.

Et la probabilité de voir une image répétée dans l’une des deux itérations suivantes est:

 1 - (0.66 × 0.66) ≈ 0.56 

En d’autres termes, il est plus probable qu’improbable que vous voyiez une image répétée au cours des deux cycles suivants. (Et cela n’inclut pas les images répétées du deuxième cycle dans le troisième cycle, ce qui ne fera que le rendre plus probable.)

Pour ce que ça vaut, voici du code Java pour faire le calcul ci-dessus:

 float result = 1.0f; int totalImages = 1000; int displayedImages = 20; for (int i = 0; i < displayedImages; i++) { result = result * (totalImages - displayedImages - i) / (totalImages - i); } System.out.println(result); 

Sa nature humaine de voir des modèles qui ne sont pas là. Beaucoup de gens voient des modèles dans les planètes et les écanvass guider leur vie.

Dans les 1000 premiers chiffres de PI, il y a six neuf à la suite. Est-ce que cela signifie que les chiffres de PI ne sont pas aléatoires? non. La tendance ne se reproduit pas plus que ce à quoi vous pourriez vous attendre.

Cela dit, Random n’est pas complètement aléatoire et se répète après 2 ^ 48 appels. (il utilise une graine de 48 bits) Cela signifie qu’il n’est pas possible de produire tous les doublons possibles. Si vous voulez plus d’aléatoire, vous pouvez utiliser à la place SecureRandom avec shuffle.

Cela ressemble à ce que vous voulez est quelque chose comme ça

 List imagePaths = new ArrayList<>(); // called repeatedly if (imagePaths.size() <= 500) { imagePaths = get1000Images(); Collections.shuffle(imagePaths); } for (String path: imagePaths.subList(0, 20)) { ... do something with the path ... } imagePaths = imagePaths.subList(20, imagePaths.size()); 

Cela garantira que vous ne voyez pas la même image lors des 500 derniers appels.

Votre intuition est correcte pour une image spécifique [vous n’êtes pas susceptible de voir une image spécifique encore et encore], mais pas pour une image générale [vous êtes susceptible de voir une image se répéter]. C’est l’un de ces endroits où il est probable que notre intuition automatique soit fausse…

Cela me rappelle le paradoxe de l’anniversaire , qui contredit l’intuition, et dit: pour un groupe de 23 personnes, la probabilité que deux d’entre elles aient le même anniversaire est de 0,5, bien plus que l’intuition attend!

J’ai fait un mélange de cartes 52 fois quatre fois et je marquais chaque fois que chaque itération répétait exactement la même carte dans le même emplacement, ce qui me donnait environ 14 cartes sur 208, soit environ 93,3% de manière aléatoire.

Suite à votre question, j’ai écrit le programme suivant. J’ai créé une liste d’entiers séquentiels et l’ai mélangée 10, 100, 1000 et 10 000 fois. Après chaque série de armsages, j’ai vérifié la valeur de l’élément en 5ème position du tableau et créé un tableau de compteurs: combien de fois chaque nombre apparaît en 5ème position.

Voici le programme:

 public class MyTest { public static void main(Ssortingng[] args) { int n = 10; List list = new ArrayList(); for (int i = 0; i < n; i++) { list.add(i); } int[] counters = new int[n]; for(int shuffles : new int[] {10, 100, 1000, 10000}) { Arrays.fill(counters, 0); for (int i = 0; i < shuffles; i++) { Collections.shuffle(list); // check 5-th element int fifth = list.get(5); counters[fifth] = counters[fifth] + 1; } System.out.println(shuffles + ": " + Arrays.toString(counters)); } } } 

Et voici les résultats:

10: [0, 1, 1, 1, 2, 0, 0, 3, 2, 0] 100: [11, 9, 9, 7, 10, 12, 13, 13, 8, 8] 1000: [100 , 101, 107, 101, 95, 96, 109, 83, 93, 115] 10000: [1015, 942, 990, 1003, 1015, 1037, 977, 1060, 950, 1011]

Comme vous pouvez le constater, la "randomalité" dépend du nombre de mélanges. Si vous mélangez un tableau 10 fois, le compteur minimal est 0 et le maximum est 3. L'écart entre ces valeurs pour 100 mélanges (en pour cent) est beaucoup plus petit. Les chiffres sont presque les mêmes pour 10000 shuffles.

Je pense que ce test modélise votre cas d'utilisation: vous montrez des images dans une position spécifique de la collection mélangée.

S'il vous plaît voir poste de @ amit qui décrit la signification de shuffle.

Donc, la solution pour vous est de mélanger votre tableau 10 fois.

EDIT: @Dave Webb a donné une explication parfaite pour l’affaire.

La seconde pensée est la suivante: vous n’avez pas besoin de mélanger votre liste de 1000 éléments pour en tirer 20 premiers éléments. Il suffit de prendre 20 éléments aléatoires. Vous obtiendrez le même effet mais une solution bien plus efficace:

 Set show = new HashSet(); Random r = new Random(System.currentTimeMillis()); for (int i = 0; show.size() < 20; i++) { show.add(list.get(r.nextInt())); } 

Avec ce code, si vous voyez la même image à plusieurs resockets, cela signifie que la même image existe plusieurs fois dans la liste. Où que vous obteniez vos 1000 images, il y a des doublons.