Est-il correct d'utiliser la méthode JavaScript Array.sort () pour la lecture aléatoire?

J'aidais quelqu'un avec son code JavaScript et mes yeux ont été attirés par une section qui ressemblait à ça:

function randOrd(){
  return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);

Mon premier avis était: hé, cela ne peut pas fonctionner! Mais ensuite, j'ai fait quelques expériences et j'ai trouvé que cela semble au moins fournir des résultats bien aléatoires.

Ensuite, j'ai fait une recherche sur le Web et presque tout en haut j'ai trouvé un article à partir duquel ce code a été copié le plus ceartanly. Cela ressemblait à un site et à un auteur assez respectables ...

Mais mon instinct me dit que cela doit être faux. D'autant que l'algorithme de tri n'est pas spécifié par la norme ECMA. Je pense que des algorithmes de tri différents entraîneront différents mélanges non uniformes. Certains algorithmes de tri peuvent même probablement boucler indéfiniment ...

Mais qu'est ce que tu penses?

Et comme autre question ... comment pourrais-je maintenant mesurer le caractère aléatoire des résultats de cette technique de mélange?

mise à jour: j'ai fait quelques mesures et posté les résultats ci-dessous comme l'une des réponses.

Il n'a jamais été ma façon préférée de brassage, en partie parce qu'elle est mise en œuvre spécifique comme vous le dites. En particulier, je semble me souvenir que la bibliothèque standard de tri à partir de Java ou .NET (je ne sais pas laquelle) peut souvent détecter si vous vous retrouvez avec une comparaison incohérente entre certains éléments (par exemple, vous revendiquez d'abord A < Bet B < C, mais ensuite C < A).

Cela finit également par être un mélange plus complexe (en termes de temps d'exécution) que vous n'en avez vraiment besoin.

Je préfère l'algorithme shuffle qui partitionne efficacement la collection en "shuffled" (au début de la collection, initialement vide) et "unshuffled" (le reste de la collection). À chaque étape de l'algorithme, choisissez un élément aléatoire non mélangé (qui pourrait être le premier) et échangez-le avec le premier élément non mélangé - puis traitez-le comme mélangé (c'est-à-dire déplacez mentalement la partition pour l'inclure).

Ceci est O (n) et ne nécessite que n-1 appels au générateur de nombres aléatoires, ce qui est bien. Il produit également un véritable mélange - tout élément a une chance de 1 / n de se retrouver dans chaque espace, quelle que soit sa position d'origine (en supposant un RNG raisonnable). La version triée se rapproche d'une distribution paire (en supposant que le générateur de nombres aléatoires ne choisit pas la même valeur deux fois, ce qui est hautement improbable s'il renvoie des doubles aléatoires) mais je trouve qu'il est plus facile de raisonner sur la version shuffle :)

Cette approche est appelée un mélange Fisher-Yates .

Je considère qu'il est préférable de coder cette lecture aléatoire une fois et de la réutiliser partout où vous avez besoin de mélanger les éléments. Ensuite, vous n'avez pas à vous soucier des implémentations de tri en termes de fiabilité ou de complexité. Ce ne sont que quelques lignes de code (que je n'essaierai pas en JavaScript!)

L' article de Wikipédia sur la lecture aléatoire (et en particulier la section sur les algorithmes de lecture aléatoire) parle de trier une projection aléatoire - il vaut la peine de lire la section sur les mauvaises implémentations de la lecture aléatoire en général, afin que vous sachiez quoi éviter.

Une fois que Jon a déjà couvert la théorie , voici une implémentation:

function shuffle(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
}

L'algorithme est O(n), alors que le tri devrait l'être O(n log n). En fonction de la surcharge de l'exécution du code JS par rapport à la sort()fonction native , cela peut entraîner une différence notable de performances qui devrait augmenter avec la taille des tableaux.

Dans les commentaires à la réponse de bobobobo , j'ai déclaré que l'algorithme en question pourrait ne pas produire des probabilités uniformément réparties (en fonction de l'implémentation de sort()).

Mon argument va dans ce sens: Un algorithme de tri nécessite un certain nombre cde comparaisons, par exemple c = n(n-1)/2pour Bubblesort. Notre fonction de comparaison aléatoire rend le résultat de chaque comparaison également probable, c'est-à-dire que les résultats sont 2^c également probables . Désormais, chaque résultat doit correspondre à l'une des n!permutations des entrées du tableau, ce qui rend impossible une distribution uniforme dans le cas général. (Ceci est une simplification, car le nombre réel de comparaisons nécessaires dépend du tableau d'entrée, mais l'assertion doit toujours être valable.)

Comme Jon l'a souligné, cela seul n'est pas une raison pour préférer Fisher-Yates à l'utilisation sort(), car le générateur de nombres aléatoires mappera également un nombre fini de valeurs pseudo-aléatoires aux n!permutations. Mais les résultats de Fisher-Yates devraient encore être meilleurs:

Math.random()produit un nombre pseudo-aléatoire dans la plage [0;1[. Comme JS utilise des valeurs à virgule flottante double précision, cela correspond aux 2^xvaleurs possibles où 52 ≤ x ≤ 63(je suis trop paresseux pour trouver le nombre réel). Une distribution de probabilité générée en utilisant Math.random()cessera de bien se comporter si le nombre d'événements atomiques est du même ordre de grandeur.

Lors de l'utilisation de Fisher-Yates, le paramètre pertinent est la taille du tableau, qui ne devrait jamais s'approcher en 2^52raison de limitations pratiques.

Lors du tri avec une fonction de comparaison aléatoire, la fonction ne se soucie essentiellement que si la valeur de retour est positive ou négative, ce ne sera donc jamais un problème. Mais il y en a un similaire: parce que la fonction de comparaison se comporte bien, les 2^crésultats possibles sont, comme indiqué, également probables. Si c ~ n log nalors 2^c ~ n^(a·n)où a = const, ce qui rend au moins possible qui 2^cest de la même grandeur que (ou même inférieure à) n!et conduisant ainsi à une distribution inégale, même si l'algorithme de tri où mapper sur les permutaions de manière uniforme. Si cela a un impact pratique, cela me dépasse.

Le vrai problème est que les algorithmes de tri ne sont pas garantis de mapper uniformément sur les permutations. Il est facile de voir que Mergesort fait comme il est symétrique, mais le raisonnement sur quelque chose comme Bubblesort ou, plus important encore, Quicksort ou Heapsort, ne l'est pas.

La ligne du bas: tant que sort()vous utilisez Mergesort, vous devriez être raisonnablement en sécurité sauf dans les cas de coin (du moins j'espère que 2^c ≤ n!c'est un cas de coin), sinon, tous les paris sont ouverts.

J'ai fait quelques mesures sur le caractère aléatoire des résultats de ce tri aléatoire ...

Ma technique était de prendre un petit tableau [1, 2, 3, 4] et d'en créer toutes (4! = 24) permutations. Ensuite, j'appliquerais la fonction de mélange au tableau un grand nombre de fois et compterais combien de fois chaque permutation est générée. Un bon algorithme de brassage répartirait les résultats assez uniformément sur toutes les permutations, tandis qu'un mauvais algorithme ne créerait pas ce résultat uniforme.

En utilisant le code ci-dessous, j'ai testé dans Firefox, Opera, Chrome, IE6 / 7/8.

Étonnamment pour moi, le tri aléatoire et le mélange réel ont tous deux créé des distributions tout aussi uniformes. Il semble donc que (comme beaucoup l'ont suggéré) les principaux navigateurs utilisent le tri par fusion. Bien sûr, cela ne signifie pas qu'il ne peut pas y avoir de navigateur là-bas, qui fait différemment, mais je dirais que cela signifie que cette méthode de tri aléatoire est suffisamment fiable pour être utilisée dans la pratique.

EDIT: Ce test n'a pas vraiment mesuré correctement le caractère aléatoire ou son absence. Voir l'autre réponse que j'ai postée.

Mais du côté des performances, la fonction de lecture aléatoire donnée par Cristoph était un gagnant clair. Même pour les petits tableaux à quatre éléments, la lecture aléatoire réelle a été environ deux fois plus rapide que le tri aléatoire!

// La fonction shuffle publiée par Cristoph.
var shuffle = fonction (tableau) {
    var tmp, courant, top = array.length;

    if (top) while (- top) {
        current = Math.floor (Math.random () * (top + 1));
        tmp = tableau [courant];
        tableau [courant] = tableau [haut];
        tableau [haut] = tmp;
    }

    return array;
};

// la fonction de tri aléatoire
var rnd = fonction () {
  return Math.round (Math.random ()) - 0,5;
};
var randSort = fonction (A) {
  retourne A.sort (rnd);
};

var permutations = fonction (A) {
  si (A.length == 1) {
    retour [A];
  }
  autre {
    var perms = [];
    pour (var i = 0; i <A.length; i ++) {
      var x = A.slice (i, i + 1);
      var xs = A.slice (0, i) .concat (A.slice (i + 1));
      var subperms = permutations (xs);
      pour (var j = 0; j <subperms.length; j ++) {
        perms.push (x.concat (sous-permis [j]));
      }
    }
    return perms;
  }
};

var test = function (A, itérations, func) {
  // permutations d'initiation
  var stats = {};
  var perms = permutations (A);
  for (var i in perms) {
    stats ["" + perms [i]] = 0;
  }

  // Mélange plusieurs fois et collecte des statistiques
  var début = nouvelle date ();
  pour (var i = 0; i <itérations; i ++) {
    var shuffled = func (A);
    stats ["" + mélangé] ++;
  }
  var end = nouvelle date ();

  // résultat du format
  var arr = [];
  for (var i dans les statistiques) {
    arr.push (i + "" + stats [i]);
  }
  return arr.join ("\ n") + "\ n \ nTemps pris:" + ((fin - début) / 1000) + "secondes.";
};

alert ("tri aléatoire:" + test ([1,2,3,4], 100000, randSort));
alert ("shuffle:" + test ([1,2,3,4], 100000, shuffle));

Fait intéressant, Microsoft a utilisé la même technique dans sa page de navigateur de sélection aléatoire.

Ils ont utilisé une fonction de comparaison légèrement différente:

function RandomSort(a,b) {
    return (0.5 - Math.random());
}

Cela me semble presque identique, mais cela s'est avéré pas si aléatoire ...

J'ai donc refait quelques tests avec la même méthodologie que celle utilisée dans l'article lié, et en effet - il s'est avéré que la méthode de tri aléatoire produisait des résultats erronés. Nouveau code de test ici:

function shuffle(arr) {
  arr.sort(function(a,b) {
    return (0.5 - Math.random());
  });
}

function shuffle2(arr) {
  arr.sort(function(a,b) {
    return (Math.round(Math.random())-0.5);
  });
}

function shuffle3(array) {
  var tmp, current, top = array.length;

  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }

  return array;
}

var counts = [
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
];

var arr;
for (var i=0; i<100000; i++) {
  arr = [0,1,2,3,4];
  shuffle3(arr);
  arr.forEach(function(x, i){ counts[x][i]++;});
}

alert(counts.map(function(a){return a.join(", ");}).join("\n"));

J'ai placé une simple page de test sur mon site Web montrant le biais de votre navigateur actuel par rapport à d'autres navigateurs populaires en utilisant différentes méthodes de lecture aléatoire. Cela montre le terrible biais de la simple utilisation Math.random()-0.5, un autre mélange `` aléatoire '' qui n'est pas biaisé et la méthode de Fisher-Yates mentionnée ci-dessus.

Vous pouvez voir que sur certains navigateurs, il y a jusqu'à 50% de chances que certains éléments ne changent pas du tout de place pendant le «shuffle»!

Remarque: vous pouvez rendre l'implémentation du shuffle Fisher-Yates par @Christoph légèrement plus rapide pour Safari en changeant le code en:

function shuffle(array) {
  for (var tmp, cur, top=array.length; top--;){
    cur = (Math.random() * (top + 1)) << 0;
    tmp = array[cur]; array[cur] = array[top]; array[top] = tmp;
  }
  return array;
}

Résultats des tests: http://jsperf.com/optimized-fisher-yates

Je pense que c'est bien pour les cas où vous n'êtes pas pointilleux sur la distribution et que vous voulez que le code source soit petit.

En JavaScript (où la source est transmise en permanence), petit fait une différence dans les coûts de bande passante.

C'est un hack, certainement. En pratique, un algorithme à boucle infinie est peu probable. Si vous triez des objets, vous pouvez parcourir le tableau coords et faire quelque chose comme:

for (var i = 0; i < coords.length; i++)
    coords[i].sortValue = Math.random();

coords.sort(useSortValue)

function useSortValue(a, b)
{
  return a.sortValue - b.sortValue;
}

(puis bouclez-les à nouveau pour supprimer sortValue)

Encore un hack cependant. Si vous voulez bien le faire, vous devez le faire à la dure :)

Cela fait quatre ans, mais j'aimerais souligner que la méthode de comparaison aléatoire ne sera pas correctement distribuée, quel que soit l'algorithme de tri que vous utilisez.

Preuve:

1. Pour un tableau d' néléments, il y a exactement des n!permutations (c'est-à-dire des mélanges possibles).
2. Chaque comparaison lors d'un shuffle est un choix entre deux ensembles de permutations. Pour un comparateur aléatoire, il y a 1/2 chance de choisir chaque ensemble.
3. Ainsi, pour chaque permutation p, la chance de se retrouver avec la permutation p est une fraction de dénominateur 2 ^ k (pour certains k), car c'est une somme de telles fractions (par exemple 1/8 + 1/16 = 3/16 ).
4. Pour n = 3, il existe six permutations également probables. La chance de chaque permutation est donc de 1/6. 1/6 ne peut pas être exprimé comme une fraction avec une puissance de 2 comme dénominateur.
5. Par conséquent, le tri par retournement de pièces n'entraînera jamais une répartition équitable des mélanges.

Les seules tailles qui pourraient éventuellement être correctement distribuées sont n = 0,1,2.

À titre d'exercice, essayez de dessiner l'arbre de décision de différents algorithmes de tri pour n = 3.

Il y a une lacune dans la preuve: si un algorithme de tri dépend de la cohérence du comparateur, et a un temps d'exécution illimité avec un comparateur incohérent, il peut avoir une somme infinie de probabilités, qui est autorisée à additionner jusqu'à 1/6 même si chaque dénominateur de la somme est une puissance de 2. Essayez d'en trouver un.

De plus, si un comparateur a une chance fixe de donner l'une ou l'autre des réponses (par exemple (Math.random() < P)*2 - 1, pour une constante P), la preuve ci-dessus est valable. Si le comparateur modifie plutôt ses cotes en fonction des réponses précédentes, il peut être possible de générer des résultats équitables. Trouver un tel comparateur pour un algorithme de tri donné pourrait être un article de recherche.

Si vous utilisez D3, il existe une fonction de lecture aléatoire intégrée (en utilisant Fisher-Yates):

var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche'];
d3.shuffle(days);

Et voici Mike qui entre dans les détails à ce sujet:

http://bost.ocks.org/mike/shuffle/

Voici une approche qui utilise un seul tableau:

La logique de base est:

Code:

for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);

Pouvez-vous utiliser la Array.sort()fonction pour mélanger un tableau - Oui.

Les résultats sont-ils suffisamment aléatoires? Non.

Considérez l'extrait de code suivant:

var array = ["a", "b", "c", "d", "e"];
var stats = {};
array.forEach(function(v) {
  stats[v] = Array(array.length).fill(0);
});
//stats = {
//    a: [0, 0, 0, ...]
//    b: [0, 0, 0, ...]
//    c: [0, 0, 0, ...]
//    ...
//    ...
//}
var i, clone;
for (i = 0; i < 100; i++) {
  clone = array.slice(0);
  clone.sort(function() {
    return Math.random() - 0.5;
  });
  clone.forEach(function(v, i) {
    stats[v][i]++;
  });
}

Object.keys(stats).forEach(function(v, i) {
  console.log(v + ": [" + stats[v].join(", ") + "]");
})

Exemple de sortie:

a [29, 38, 20,  6,  7]
b [29, 33, 22, 11,  5]
c [17, 14, 32, 17, 20]
d [16,  9, 17, 35, 23]
e [ 9,  6,  9, 31, 45]

Idéalement, les comptes doivent être uniformément répartis (pour l'exemple ci-dessus, tous les comptes doivent être d'environ 20). Mais ils ne le sont pas. Apparemment, la distribution dépend de l'algorithme de tri implémenté par le navigateur et de la manière dont il itère les éléments du tableau pour le tri.

Plus d'informations sont fournies dans cet article:
Array.sort () ne doit pas être utilisé pour mélanger un tableau

Il n'y a rien de mal à cela.

La fonction que vous passez à .sort () ressemble généralement à quelque chose comme

fonction sortingFunc (premier, deuxième)
{
  // exemple:
  retour premier - deuxième;
}

Votre travail dans sortingFunc est de retourner:

• un nombre négatif si le premier passe avant le second
• un nombre positif si le premier doit aller après le second
• et 0 s'ils sont complètement égaux

La fonction de tri ci-dessus met les choses en ordre.

Si vous retournez des - et + au hasard comme ce que vous avez, vous obtenez un ordre aléatoire.

Comme dans MySQL:

SELECT * de la table ORDER BY rand ()