Comment rendre aléatoire (shuffle) un tableau JavaScript?
J'ai un tableau comme ceci:
var arr1 = ["a", "b", "c", "d"];
Comment puis-je rendre aléatoire /aléatoire?
jsPerf comparaison des performances de plusieurs méthodes
Juste jeter cette ici que vous pouvez visualiser de façon aléatoire une fonction de lecture aléatoire est en fait avec cette visualizer Mike Bostock fait: bost.ocks.org/mike/shuffle/compare.html
jsPref est mort. Pouvez-vous poster ici ce qui est le plus rapide?
J'ai ajouté réponse qui peuvent être concaténés et de ne pas prolonger le natif de la Matrice de prototype.
Que penser d'un one-liner? Le tableau retourné est battu. arr1.réduire((a,v)=>un.splice(Math.floor(Math.random () *.la longueur), 0, v) && a, [])
Juste jeter cette ici que vous pouvez visualiser de façon aléatoire une fonction de lecture aléatoire est en fait avec cette visualizer Mike Bostock fait: bost.ocks.org/mike/shuffle/compare.html
jsPref est mort. Pouvez-vous poster ici ce qui est le plus rapide?
J'ai ajouté réponse qui peuvent être concaténés et de ne pas prolonger le natif de la Matrice de prototype.
Que penser d'un one-liner? Le tableau retourné est battu. arr1.réduire((a,v)=>un.splice(Math.floor(Math.random () *.la longueur), 0, v) && a, [])
OriginalL'auteur Click Upvote | 2010-03-15
Vous devez vous connecter pour publier un commentaire.
Ici est un code JavaScript de la mise en œuvre de la Durstenfeld shuffle, un ordinateur-version optimisée de Fisher-Yates:
De Fisher-Yates algorithme fonctionne par la sélection d'un élément aléatoire pour l'original de chaque élément du tableau, et puis l'exclure du tirage suivant. Tout comme choisissant au hasard à partir d'un jeu de cartes.
Cette exclusion est fait de façon intelligente (inventé par Durstenfeld pour une utilisation par les ordinateurs) par le remplacement de l'élément choisi avec l'élément en cours, puis en sélectionnant le prochain élément aléatoire du reste. Pour une efficacité optimale, la boucle s'exécute en arrière de sorte que le random pick est simplifié (il peut toujours commencer à 0), et il saute le dernier élément, car il n'y a pas d'autres choix plus.
Le temps d'exécution de cet algorithme est O(n). Notez que la lecture aléatoire est effectuée sur place. Donc, si vous ne voulez pas modifier le tableau d'origine, en faire une copie d'abord avec
.slice(0)
.Mise à jour à ES6 /ECMAScript 2015
La nouvelle ES6 nous permet d'attribuer deux variables à la fois. Ceci est particulièrement utile lorsque l'on veut permuter les valeurs de deux variables, comme on peut le faire en une seule ligne de code. Ici est une forme courte de la même fonction, à l'aide de cette fonction.
Les gens sont de l'attribution de la mauvaise personne pour l'algorithme. Ce n'est pas de Fisher-Yates shuffle mais Durstenfeld shuffle. La véritable origine de Fisher-Yates est l'algorithme s'exécute en n^2 temps, pas de temps n
Il n'est pas nécessaire pour
return array
depuis JavaScript passe tableaux de référence lorsqu'il est utilisé comme arguments de la fonction. Je suppose que c'est pour économiser sur l'espace de pile, mais c'est intéressant, cette petite fonctionnalité. Effectuer la lecture aléatoire sur la matrice de mélange le tableau d'origine.La mise en œuvre dans cette réponse, favorise l'extrémité inférieure de la matrice. Découvert la manière dure.
Math.random() should not be multiplied with the loop counter + 1, but with
tableau.s()`. Voir la Génération aléatoire de nombres entiers en JavaScript dans une gamme spécifique? pour un très explication complète.Vous ne savez pas si vous regardez cet espace, mais cette réponse est correct, et le changement que vous êtes ce qui suggère effectivement introduit un biais. Voir blog.codinghorror.com/the-danger-of-naivete pour une belle description de cette erreur.
OriginalL'auteur Laurens Holst
[communauté edit: Cette réponse est incorrecte; voir les commentaires. Il est parti d'ici pour référence future, parce que l'idée n'est pas rare.]
Downvoting que ce n'est pas vraiment aléatoire. Je ne sais pas pourquoi il a tant de upvotes. N'utilisez pas cette méthode. Il semble assez, mais ce n'est pas tout à fait correct. Voici les résultats après 10 000 itérations sur combien de fois chaque nombre dans votre tableau de frappe index [0] (je peux donner à l'autre les résultats de): 1 = 29.19%, 2 = 29.53%, 3 = 20.06%, 4 = 11.91%, 5 = 5.99%, 6 = 3.32%
C'est aussi le la moins efficace de toutes les méthodes disponibles.
mais il est très mignon
Le problème est qu'il n'est pas déterministe, ce qui donnera de mauvais résultats (si 1 > 2 et 2 > 3, il devrait être donné que 1 > 3, mais ce ne sera pas le garantir. Cela perturbera les trier, et de donner le résultat commenté par @radtad).
OriginalL'auteur deadrunk
On pourrait (ou devrait) l'utiliser comme un protoype de la Matrice:
De ChristopheD:
Vraiment aucun avantage à cela, IMOHO, sauf peut-être en piétinant sur quelqu'un d'autre ..
On pourrait (ou devrait) éviter l'extension Native Prototypes: javascriptweblog.wordpress.com/2011/12/05/...
Vous ne devriez pas faire cela; chaque tableau touchés par cela ne peut plus être réitéré en toute sécurité à l'aide de for...in. Ne pas prolonger les prototypes natifs.
En fait: ne pas utiliser
for...in
boucles pour itérer sur tous les tableaux.OriginalL'auteur con
Utiliser le underscore.js de la bibliothèque. La méthode
_.shuffle()
est bien pour cette affaire.Voici un exemple de la méthode:
Il n'y a aucun point en incluant une bibliothèque entière juste pour obtenir un
shuffle
fonction.Je suis en désaccord avec @Blender. Il existe de nombreuses raisons pour inclure une bibliothèque entière juste pour obtenir une fonction dont vous avez besoin. L'un d'entre eux est qu'il ya moins de risque de bug quand vous écrivez vous-même. Si c'est un problème de performances, alors vous ne devriez pas l'utiliser. Mais juste parce que c' être un problème de performance ne signifie pas qu'il sera.
Alors, pourquoi avez-vous besoin du reste de la bibliothèque? Le shuffle de Fisher-Yates est trivial à mettre en œuvre. Vous n'avez pas besoin d'une bibliothèque pour choisir un élément aléatoire d'un tableau (je l'espère), donc il n'y a pas de raison d'utiliser une bibliothèque, sauf si vous êtes réellement allons utiliser plus d'une fonction.
J'ai donné une raison. 1) je vous rassure, vous pouvez introduire un bogue dans le code que vous écrivez, peu importe comment trivial qu'il est. Pourquoi prendre le risque? 2) Ne pas pré-optimiser. 3) 99% du temps lorsque vous avez besoin d'un shuffle algo, votre application n'est pas sur la rédaction d'un shuffle algo. Il s'agit de quelque chose que besoins un shuffle algo. Exploiter le travail des autres. Ne pense pas à des détails de mise en œuvre, sauf si vous avez.
OriginalL'auteur vn_grv
NOUVEAU!
Plus court & probablement *plus rapide de Fisher-Yates algorithme de shuffle
taille d'un script (avec l'af comme le nom de la fonction): 90bytes
DÉMO
http://jsfiddle.net/vvpoma8w/
*plus rapide, probablement sur tous les navigateurs, sauf chrome.
Si vous avez des questions n'hésitez pas.
MODIFIER
oui, il est plus rapide
PERFORMANCE: http://jsperf.com/fyshuffle
en utilisant le haut voté fonctions.
MODIFIER
Il y avait un calcul dans l'excès (n'avez pas besoin-c+1) et personne n'a remarqué
plus courte(4 octets)&plus rapide(à tester!).
La mise en cache quelque part d'autre
var rnd=Math.random
et ensuite utiliserrnd()
permettrait également d'augmenter légèrement les performances sur de grands tableaux.http://jsfiddle.net/vvpoma8w/2/
Version lisible (utiliser la version originale. c'est plus lent, vars sont inutiles, comme les fermetures & ";", le code lui-même est également plus courte ... peut-être lire ce Comment minifier' code Javascript , d'ailleurs vous n'êtes pas capable de compresser le code suivant dans un javascript minifiers comme ci-dessus.)
Oui, très bien, mais ce n'est pas la raison pour la rendre illisible.
js est un langage qui accepte de nombreux raccourcis et les différentes manières de l'écrire.. alors qu'il y a de nombreux lent lisible fonctions dans ici, j'aime juste pour montrer comment il pourrait être fait dans une plus performantes moyen, également de gagner quelques octets... au niveau du bit et de l'abréviation est vraiment sous-estimé ici et le web est plein de buggy et ralentit le code.
Et minifiers ne fonctionnent pas correctement....stackoverflow.com/a/21353032/2450730
ungolf et nous allons vous donner plus de upvotes
OriginalL'auteur cocco
Vous pouvez le faire facilement avec une carte et de tri:
Vous pouvez mélanger des tableaux polymorphes, et le tri est aussi aléatoire que les Mathématiques.aléatoire, ce qui est assez bon pour la plupart des besoins.
Puisque les éléments sont triés contre cohérente clés qui ne sont pas régénérés à chaque itération, et chaque comparaison tire de la même distribution, tous les non-aléatoire dans la distribution de Mathématiques.aléatoire est annulée.
Oups, vous avez raison. Notez que cette réponse déjà utilisé la même approche.
Ah oui, vous avez raison, bien que je pense de ma mise en œuvre est un peu plus joli.
Très agréable. C'est le Schwartzian transformer en js.
Mais la performance est pire que de l'EXERCICE.
OriginalL'auteur superluminary
L'ajout de @Laurens Holsts réponse. C'est 50% comprimé.
Pourquoi devrais-je inclure un ensemble de 4 ko bibliothèque juste à mélanger un tableau?
nom de l'appelant est aussi ne conduisent pas à un assemblage d'une collectivité raisonnable.
est-il efficace pour faire
var b =
dans une boucle au lieu de déclarer b en dehors de la boucle et de l'affecter àb =
dans une boucle?faire une différence; le levage se produit lorsque le code source est analysé. Pas probablement impliqués.
OriginalL'auteur KingKongFrog
Certaines des réponses pourrait être raccourci à l'aide de ES6 syntaxe.
ES6 Pur, Itératif
Personnellement, j'utilise cette fonction car il est pur, relativement simple, et selon mes tests sur Google Chrome le plus efficace (par rapport à d'autres pure versions).
Shuffle réseau En place
De fiabilité et de Performance
Comme vous pouvez le voir dans cette page, il y a eu des solutions incorrectes offert ici dans le passé. Donc, avec la fiabilité et la performance à l'esprit, j'ai écrit cette fonction permet de tester toute pure (sans effets secondaires) tableau de randomisation des fonctions. Je l'ai utilisé pour tester toutes les options présentées dans cette réponse.
Tapuscrit de type pour un pur tableau de randomisation fonction
Vous pouvez utiliser l'une des opérations suivantes.
Autres Options
ES6 Pur, Récursive
Cette version est moins efficace que l'itératif version pure.
ES6 Pur à l'aide du tableau.carte
Cette version est légèrement moins efficace que l'itératif version pure.
ES6 Pur à l'aide du tableau.réduire
Cette version est légèrement moins efficace que l'itératif version pure.
[array[i], array[rand]]=[array[rand], array[i]]
? Peut-être que vous pouvez décrire comment cela fonctionne. Pourquoi choisissez-vous pour effectuer une itération vers le bas?Oui, l'ES6 fonctionnalité que j'utilise est la cession de deux vars à la fois, ce qui nous permet de permuter deux vars en une seule ligne de code.
Crédit @sheriffderek qui ont proposé l'Algorithme ascendant. L'ascendant de l'algorithme puisse être prouvé dans la phase d'induction.
OriginalL'auteur Ben Carp
Avec ES2015 vous pouvez utiliser celui-ci:
Utilisation:
n >>> 0
au lieu de~~n
. Indices de tableau peut être plus élevé que 231-1.Déstructuration comme cela rend pour un nettoyage de mise en œuvre +1
OriginalL'auteur BrunoLM
Je me trompe ou c'est complètement cassé?
Le code a été rompu en raison du fait que la longueur du tableau est modifiée à l'intérieur de la boucle for. Avec la dernière édition c'est corrigé.
OriginalL'auteur Tophe
J'ai trouvé cette variante de traîner dans la "a été supprimé par l'auteur" répond à un double de cette question. Contrairement à certains des autres réponses qui ont beaucoup de upvotes déjà, c'est:
shuffled
nom, plutôt que deshuffle
)Voici un jsfiddle le montrant en cours d'utilisation.
Ouais, mais étant donné que le bien-connu de mauvaise réponse est toujours avec un tas de voix, un inefficace, mais la bonne solution devrait au moins être mentionné.
Qui est le "bien connu de mauvaise réponse"?
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });
- il ne donne pas un hasard sorte, et si vous l'utilisez, vous pouvez vous retrouver embarrassé: robweir.com/blog/2010/02/microsoft-random-browser-ballot.htmlVous avez besoin d'utiliser
.sort(function(a,b){ return a[0] - b[0]; })
si vous voulez du genre à comparer les valeurs numériques. La valeur par défaut.sort()
comparateur est lexicographique ce qui signifie qu'il va considérer10
à moins de2
depuis1
est à moins de2
.OriginalL'auteur Daniel Martin
Une solution récursive:
OriginalL'auteur Julian
De Fisher-Yates shuffle en javascript. Je poste ici parce que l'utilisation de deux fonctions utilitaires (swap et randInt) précise l'algorithme par rapport aux autres réponses ici.
OriginalL'auteur dpatru
Tout d'abord, jetez un oeil ici pour un grand visuel comparaison de différentes méthodes de tri en javascript.
Deuxièmement, si vous avez un coup d'oeil sur le lien ci-dessus, vous constaterez que le
random order
trier semble fonctionner relativement bien par rapport aux autres méthodes, tout en étant très facile et rapide à mettre en œuvre, comme illustré ci-dessous:Modifier: comme l'a souligné @gregers, la fonction de comparaison est appelé avec les valeurs plutôt que des indices, qui est pourquoi vous devez utiliser des
indexOf
. Notez que cette modification rend le code moins adapté pour les grands tableaux commeindexOf
s'exécute en O(n) fois.Array.prototype.sort
passe en deux commea
etb
, pas l'index. Si ce code ne fonctionne pas.vous avez raison, j'ai édité la réponse. Merci.
Ce n'est pas très aléatoire. En fonction de la mise en œuvre de la sorte, l'élément le plus bas de tableau d'index peut nécessiter plus de comparaisons afin d'obtenir le plus haut indice de l'élément à côté de l'indice le plus élevé. Cela signifie qu'il est moins probable que l'élément à l'indice le plus bas pour aller à l'indice le plus élevé.
OriginalL'auteur 0sh
une fonction de lecture aléatoire qui ne change pas le tableau source
Mise à jour: Ici je suis en proposant une relativement simple (pas de complexité point de vue) et court algorithme qui permettra de faire tout aussi bien avec de petites et moyennes dimensions des tableaux, mais il va certainement coûter beaucoup plus cher que le classique Durstenfeld algorithme lorsque vous traitez avec des gros tableaux. Vous pouvez trouver la Durstenfeld dans l'une des premières réponses à cette question.
Réponse originale à cette question:
Si vous ne souhaitez pas votre fonction de lecture aléatoire de la mutation de l' tableau source, vous pouvez le copier sur une variable locale, puis faire le reste avec un simple brassage logique.
Brassage logique: ramasser un hasard de l'index, puis ajouter l'élément correspondant à la tableau résultat et le supprimer de la de la source matrice de copie. Répétez cette action jusqu'à ce que le tableau source obtient vide.
Et si vous voulez vraiment court, voici comment loin que j'ai pu obtenir:
splice
être horriblement inefficace moyen de faire ce qu'ils appellent la "suppression". Si vous ne voulez pas muter le tableau d'origine, puis il suffit de le copier, et ensuite mélanger cette copie à l'aide de la beaucoup plus efficace Durstenfeld variante.merci pour vos commentaires. J'ai mis à jour ma réponse, pour le rendre clair que je suis plutôt offrant une belle-la recherche de la solution, qu'un super-mise à l'échelle d'un
Nous pourrions aussi utiliser la
splice
méthode pour créer une copie de la sorte:source = array.slice();
.OriginalL'auteur Evgenia Manolova
encore une autre mise en œuvre de Fisher-Yates, en utilisant le mode strict:
Pour en savoir plus sur le mode strict et comment elle influe sur la performance que vous pouvez lire à ce sujet ici: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/...
Hmm, pourriez-vous point quelque chose de spécifique dans le document référencé? Rien n'y semble de référence "amélioration des performances", à part une vague de commentaires sur ce qui pourrait le rendre difficile pour le js moteur pour optimiser. Dans ce cas, il est clair pour moi ce que l'utilisation stricte de s'améliorer.
Le mode Strict a été autour depuis un certain temps, et il y a suffisamment de lit pour ceux à faire leur propre opinion si ils doivent toujours utiliser ou pas et pourquoi. Jslint pour instance, il est assez clair que vous devriez toujours utiliser le mode strict. Douglas Crockford a écrit tout à fait une quantité d'articles et des vidéos sur pourquoi il est important de toujours utiliser le mode strict, non seulement comme une bonne pratique, mais aussi la façon dont elle est interprétée différemment par navigateur js moteurs V8. Je vous conseille fortement de Google et de faire votre propre opinion à ce sujet.
Voici un vieux thread sur les perfs en mode strict, un peu vieux mais toujours d'actualité: stackoverflow.com/questions/3145966/...
OriginalL'auteur Raphael C
https://javascript.info/task/shuffle
OriginalL'auteur hakiko
Moderne, court inline solution à l'aide de ES6 caractéristiques:
(à des fins pédagogiques)
OriginalL'auteur icl7126
D'une simple modification de CoolAJ86 de réponse qui ne modifie pas le tableau d'origine:
OriginalL'auteur abumalick
Si il y a un certain nombre d'implémentations déjà conseillé, mais je sens que nous pouvons faire plus court et plus facile à l'aide d'une boucle forEach, donc on n'a pas besoin de s'inquiéter sur le calcul de la longueur du tableau et aussi nous pouvons éviter d'utiliser une variable temporaire.
OriginalL'auteur Hafizur Rahman
les plus brefs
arrayShuffle
fonctionOriginalL'auteur Tusko Trush
À partir d'un point de vue théorique, la façon la plus élégante de le faire, à mon humble avis, est d'obtenir une unique nombre aléatoire entre 0 et n!-1 et pour calculer une association de
{0, 1, …, n!-1}
de toutes les permutations de(0, 1, 2, …, n-1)
. Tant que vous pouvez utiliser une (pseudo-)aléatoire générateur suffisamment fiable pour obtenir un tel numéro, sans aucun biais important, vous avez suffisamment d'informations pour la réalisation de ce que vous voulez sans avoir besoin de plusieurs autres nombres aléatoires.Lors du calcul avec IEEE754 double précision nombres flottants, vous pouvez vous attendre de votre générateur aléatoire pour fournir environ 15 décimales. Puisque vous avez 15!=1,307,674,368,000 (à 13 chiffres), vous pouvez utiliser les fonctions suivantes avec des tableaux contenant jusqu'à 15 éléments et supposons qu'il n'y aura pas de biais significatif avec des tableaux renfermant jusqu'à 14 éléments. Si vous travaillez sur une taille fixe de problème qui nécessite de calculer plusieurs fois cette lecture aléatoire de l'opération, vous pouvez essayer le code suivant qui peut être plus rapide que les autres codes car il utilise
Math.random
qu'une seule fois (il s'agit de plusieurs opérations de copie).La fonction suivante ne sera pas utilisé, mais je donne quand même; il renvoie l'index d'une permutation de
(0, 1, 2, …, n-1)
selon l'une à une cartographie utilisées dans ce message (le plus naturel lors de l'énumération permuations); il est prévu pour fonctionner avec jusqu'à 16 éléments:La réciproque de la fonction précédente (nécessaire pour votre propre question) est au-dessous; il est prévu pour fonctionner avec jusqu'à 16 éléments; elle renvoie la permutation de l'ordre n de
(0, 1, 2, …, s-1)
:Maintenant, ce que vous voulez, simplement:
Il devrait travailler jusqu'à 16 éléments avec un peu théorique de biais (si imperceptible à partir d'un point de vue pratique); il peut être considéré comme pleinement utilisable pour 15 éléments; avec des tableaux contenant moins de 14 éléments, vous pouvez en toute sécurité envisager il n'y aura absolument pas de parti pris.
OriginalL'auteur Thomas Baruchel
n >>> 0
au lieu den | 0
. Indices de tableau peut être plus élevé que 231-1.OriginalL'auteur user1289673
Aléatoire tableau à l'aide du tableau.splice()
démo
OriginalL'auteur Saravanan Rajaraman