Catégorie : Snippets

Quand le hasard est trop prévisible, un petit coup de shuffle pour épauler random().

Le hasard et la statistique

Dans la vie, le hasard fait plus ou moins bien les choses. En informatique, c’est un peu plus tordu : au delà d’un certain nombre d’itérations, le hasard rencontre la statistique.
Si vous devez piocher au hasard des valeurs dans un tableau, l’algorithme tape au milieu la plupart du temps et touche rarement les bords (elle est pour toi Chriis).  

Pour philosopher plus loin sur le sujet, je conseille vivement d’aller se cultiver un petit quart d’heure sur « La puissance organisatrice du hasard » de l’excellent Mickaël Launay :

Je ne ferai pas ici la liste des différents algorithmes permettant de tirer « mieux » une valeur au hasard, chacun y va de sa méthode (utiliser le timestamp, piocher un pixel dans une image, parser le md5 de la dernière vidéo postée sur Youporn, …). Je ne me lancerai pas non plus dans un comparatif des ressources nécessaire pour accomplir les calculs.

Shuffle au secours de Random

Pour les besoins ponctuels, le bon vieux Math.random() fera l’affaire :

var rand = myArray[Math.floor(Math.random() * myArray.length)];

Dans le cas où le hasard ne fait pas bien les choses, il vaut mieux mélanger le tableau. Voici une méthode basée sur l’algorithme de Fisher-Yates :

function shuffle(array) {
 var m = array.length, t, i;

// While there remain elements to shuffle…
 while (m) {

// Pick a remaining element…
 i = Math.floor(Math.random() * m--);

// And swap it with the current element.
 t = array[m];
 array[m] = array[i];
 array[i] = t;
 }

return array;
}

Pour comprendre la différence, je recommande d’aller voir les excellentes visualisations faites par Mike Bostock.

Conclusion

• Besoin du hasard une ou deux fois : random()
• Du hasard moins prévisible : shuffle() et random()
• Attention à la vitesse d’exécution sur les grands tableaux