Ist es richtig, die JavaScript Array.sort () -Methode zum Mischen zu verwenden?

126

Ich habe jemandem mit seinem JavaScript-Code geholfen und meine Augen wurden von einem Abschnitt erfasst, der so aussah:

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

Mein erstes war jedoch: Hey, das kann unmöglich funktionieren! Aber dann habe ich ein bisschen experimentiert und festgestellt, dass es tatsächlich zumindest gut randomisierte Ergebnisse zu liefern scheint.

Dann habe ich eine Websuche durchgeführt und fast oben einen Artikel gefunden, aus dem dieser Code am besten kopiert wurde. Sah aus wie eine ziemlich respektable Seite und Autor ...

Aber mein Bauchgefühl sagt mir, dass das falsch sein muss. Zumal der Sortieralgorithmus nicht im ECMA-Standard festgelegt ist. Ich denke, dass unterschiedliche Sortieralgorithmen zu unterschiedlichen ungleichmäßigen Mischvorgängen führen. Einige Sortieralgorithmen können wahrscheinlich sogar unendlich schleifen ...

Aber was denkst du?

Und als weitere Frage ... wie würde ich jetzt messen, wie zufällig die Ergebnisse dieser Mischtechnik sind?

Update: Ich habe einige Messungen durchgeführt und die folgenden Ergebnisse als eine der Antworten veröffentlicht.

Rene Saarsoo
quelle
nur um zu bemerken, dass es sinnlos ist, das Ergebnis nur die Zeichenanzahl zu runden
Bormat
2
" Ich fand, dass es gut randomisierte Ergebnisse zu liefern scheint. " - WIRKLICH ???
Bergi

Antworten:

109

Es war nie meine bevorzugte Art zu mischen, auch weil es, wie Sie sagen, implementierungsspezifisch ist . Insbesondere erinnere ich mich daran, dass die Standardbibliothekssortierung von Java oder .NET (nicht sicher, welche) häufig erkennen kann, ob Sie einen inkonsistenten Vergleich zwischen einigen Elementen erhalten (z. B. behaupten Sie zuerst A < Bund B < C, aber dann C < A).

Es wird auch zu einem komplexeren (in Bezug auf die Ausführungszeit) Shuffle, als Sie wirklich brauchen.

Ich bevorzuge den Shuffle-Algorithmus, der die Sammlung effektiv in "gemischt" (zu Beginn der Sammlung, anfangs leer) und "nicht gemischt" (der Rest der Sammlung) unterteilt. Wählen Sie bei jedem Schritt des Algorithmus ein zufälliges nicht gemischtes Element aus (das das erste sein könnte) und tauschen Sie es gegen das erste nicht gemischte Element aus. Behandeln Sie es dann als gemischt (dh verschieben Sie die Partition mental, um es einzuschließen).

Dies ist O (n) und erfordert nur n-1 Aufrufe an den Zufallszahlengenerator, was sehr schön ist. Es wird auch ein echtes Shuffle erzeugt - jedes Element hat eine 1 / n-Chance, in jedem Feld zu landen, unabhängig von seiner ursprünglichen Position (unter der Annahme eines angemessenen RNG). Die sortierte Version ist ungefähr einer geraden Verteilung (vorausgesetzt, der Zufallszahlengenerator wählt nicht zweimal denselben Wert aus, was höchst unwahrscheinlich ist, wenn zufällige Zufallsdoppelwerte zurückgegeben werden), aber ich finde es einfacher, über die Zufallsversion nachzudenken :)

Dieser Ansatz wird als Fisher-Yates-Shuffle bezeichnet .

Ich würde es als bewährte Methode betrachten, dieses Shuffle einmal zu codieren und überall dort wiederzuverwenden, wo Sie Elemente mischen müssen. Dann müssen Sie sich keine Gedanken über Sortierimplementierungen in Bezug auf Zuverlässigkeit oder Komplexität machen. Es sind nur ein paar Codezeilen (die ich in JavaScript nicht versuchen werde!)

Der Wikipedia-Artikel über das Mischen (und insbesondere den Abschnitt über Zufallsalgorithmen) befasst sich mit dem Sortieren einer zufälligen Projektion. Es lohnt sich, den Abschnitt über schlechte Implementierungen des Mischens im Allgemeinen zu lesen, damit Sie wissen, was Sie vermeiden sollten.

Jon Skeet
quelle
5
Raymond Chen geht eingehend auf die Wichtigkeit ein, dass Sortiervergleichsfunktionen den Regeln folgen: blogs.msdn.com/oldnewthing/archive/2009/05/08/9595334.aspx
Jason Kresowaty
1
Wenn meine Argumentation richtig ist, erzeugt die sortierte Version kein "echtes" Mischen!
Christoph
@Christoph: Wenn man darüber nachdenkt, wird selbst Fisher-Yates nur dann eine "perfekte" Verteilung liefern, wenn Rand (x) garantiert genau über seiner Reichweite liegt. Angesichts der Tatsache, dass es für einige x normalerweise 2 ^ x mögliche Zustände für das RNG gibt, denke ich nicht, dass es für Rand (3) genau gleich sein wird .
Jon Skeet
@ Jon: aber Fisher-Yates erstellt 2^xZustände für jeden Array-Index, dh es gibt insgesamt 2 ^ (xn) Zustände, die etwas größer sein sollten als 2 ^ c - siehe meine bearbeitete Antwort für Details
Christoph
@Christoph: Ich habe mich vielleicht nicht richtig erklärt. Angenommen, Sie haben nur 3 Elemente. Sie wählen das erste Element zufällig aus allen 3. Um eine völlig gleichmäßige Verteilung zu erhalten, müssten Sie in der Lage sein, eine Zufallszahl im Bereich [0,3) völlig gleichmäßig zu wählen - und wenn der PRNG 2 ^ n hat mögliche Zustände, das können Sie nicht - eine oder zwei der Möglichkeiten haben eine etwas höhere Wahrscheinlichkeit des Auftretens.
Jon Skeet
118

Nachdem Jon die Theorie bereits behandelt hat , folgt eine Implementierung:

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;
}

Der Algorithmus ist O(n), während das Sortieren sein sollte O(n log n). Abhängig vom Aufwand für die Ausführung von JS-Code im Vergleich zur nativen sort()Funktion kann dies zu einem spürbaren Leistungsunterschied führen, der mit der Arraygröße zunehmen sollte.


In den Kommentaren zu Bobobobos Antwort stellte ich fest, dass der betreffende Algorithmus möglicherweise keine gleichmäßig verteilten Wahrscheinlichkeiten erzeugt (abhängig von der Implementierung von sort()).

Mein Argument geht in diese Richtung: Ein Sortieralgorithmus erfordert eine bestimmte Anzahl cvon Vergleichen, z c = n(n-1)/2. B. für Bubblesort. Unsere zufällige Vergleichsfunktion macht das Ergebnis jedes Vergleichs gleich wahrscheinlich, dh es gibt 2^c gleich wahrscheinliche Ergebnisse. Jetzt muss jedes Ergebnis einer der n!Permutationen der Einträge des Arrays entsprechen, was im allgemeinen Fall eine gleichmäßige Verteilung unmöglich macht. (Dies ist eine Vereinfachung, da die tatsächliche Anzahl der erforderlichen Vergleiche vom Eingabearray abhängt, die Behauptung jedoch weiterhin gelten sollte.)

Wie Jon betonte, ist dies allein kein Grund, Fisher-Yates der Verwendung vorzuziehen sort(), da der Zufallszahlengenerator den n!Permutationen auch eine endliche Anzahl von Pseudozufallswerten zuordnet. Aber die Ergebnisse von Fisher-Yates sollten immer noch besser sein:

Math.random()erzeugt eine Pseudozufallszahl im Bereich [0;1[. Da JS Gleitkommawerte mit doppelter Genauigkeit verwendet, entspricht dies 2^xmöglichen Werten, bei denen 52 ≤ x ≤ 63(ich bin zu faul, um die tatsächliche Zahl zu finden). Eine mit erzeugte Wahrscheinlichkeitsverteilung Math.random()verhält sich nicht mehr gut, wenn die Anzahl der atomaren Ereignisse in der gleichen Größenordnung liegt.

Bei Verwendung von Fisher-Yates ist der relevante Parameter die Größe des Arrays, die sich 2^52aus praktischen Gründen niemals annähern sollte .

Beim Sortieren mit einer zufälligen Vergleichsfunktion kümmert sich die Funktion grundsätzlich nur darum, ob der Rückgabewert positiv oder negativ ist, sodass dies niemals ein Problem darstellt. Aber es gibt eine ähnliche: Da sich die Vergleichsfunktion gut verhält, sind die 2^cmöglichen Ergebnisse, wie gesagt, ebenso wahrscheinlich. Wenn c ~ n log ndann 2^c ~ n^(a·n)wo a = const, was es zumindest möglich macht, dass 2^ces die gleiche Größe wie (oder sogar weniger als) hat n!und somit zu einer ungleichmäßigen Verteilung führt, selbst wenn der Sortieralgorithmus gleichmäßig auf die Permutationen abgebildet werden soll. Ob dies praktische Auswirkungen hat, ist mir ein Rätsel.

Das eigentliche Problem besteht darin, dass nicht garantiert wird, dass die Sortieralgorithmen gleichmäßig auf die Permutationen abgebildet werden. Es ist leicht zu erkennen, dass Mergesort symmetrisch funktioniert, aber wenn man über etwas wie Bubblesort oder, was noch wichtiger ist, Quicksort oder Heapsort nachdenkt, ist dies nicht der Fall.


Fazit: Solange sort()Sie Mergesort verwenden, sollten Sie einigermaßen sicher sein, außer in Eckfällen (zumindest hoffe ich, dass dies 2^c ≤ n!ein Eckfall ist). Wenn nicht, sind alle Wetten ungültig.

Christoph
quelle
Danke für die Implementierung. Es ist unglaublich schnell! Besonders im Vergleich zu dem langsamen Mist, den ich in der Zwischenzeit selbst geschrieben habe.
Rene Saarsoo
1
Wenn Sie die Bibliothek underscore.js verwenden, können Sie sie mit der oben genannten Fisher-Yates-Shuffle-Methode erweitern: github.com/ryantenney/underscore/commit/…
Steve
Vielen Dank dafür. Die Kombination aus Ihrer und Johns Antwort hat mir geholfen, ein Problem zu beheben, an dem ich und ein Kollege zusammen fast 4 Stunden verbracht haben! Wir hatten ursprünglich eine ähnliche Methode wie das OP, stellten jedoch fest, dass die Randomisierung sehr flockig war. Daher haben wir Ihre Methode übernommen und sie leicht geändert, um mit ein wenig Abfrage eine Liste von Bildern (für einen Schieberegler) durcheinander zu bringen, um einige zu erhalten tolle Randomisierung.
Hallo Welt
16

Ich habe einige Messungen durchgeführt, wie zufällig die Ergebnisse dieser zufälligen Sorte sind ...

Meine Technik bestand darin, ein kleines Array [1,2,3,4] zu nehmen und alle (4! = 24) Permutationen davon zu erstellen. Dann würde ich die Mischfunktion eine große Anzahl von Malen auf das Array anwenden und zählen, wie oft jede Permutation erzeugt wird. Ein guter Mischalgorithmus würde die Ergebnisse ziemlich gleichmäßig über alle Permutationen verteilen, während ein schlechter nicht dieses einheitliche Ergebnis erzeugen würde.

Mit dem folgenden Code habe ich in Firefox, Opera, Chrome, IE6 / 7/8 getestet.

Überraschenderweise haben für mich sowohl die zufällige Sortierung als auch das echte Mischen gleichmäßige Verteilungen erzeugt. Es scheint also, dass (wie viele vorgeschlagen haben) die Hauptbrowser die Zusammenführungssortierung verwenden. Dies bedeutet natürlich nicht, dass es keinen Browser gibt, der anders funktioniert, aber ich würde sagen, dass diese Zufallssortierungsmethode zuverlässig genug ist, um in der Praxis verwendet zu werden.

EDIT: Dieser Test hat die Zufälligkeit oder das Fehlen nicht wirklich richtig gemessen. Siehe die andere Antwort, die ich gepostet habe.

Aber auf der Leistungsseite war die von Cristoph gegebene Shuffle-Funktion ein klarer Gewinner. Selbst bei kleinen Arrays mit vier Elementen war das echte Mischen etwa doppelt so schnell wie das zufällige Sortieren!

// Die von Cristoph gepostete Shuffle-Funktion.
var shuffle = Funktion (Array) {
    var tmp, current, top = array.length;

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

    Array zurückgeben;
};

// die zufällige Sortierfunktion
var rnd = function () {
  return Math.round (Math.random ()) - 0.5;
};
var randSort = Funktion (A) {
  return A.sort (rnd);
};

var permutations = Funktion (A) {
  if (A. Länge == 1) {
    return [A];
  }}
  sonst {
    var perms = [];
    für (var i = 0; i <A.Länge; i ++) {
      var x = A. slice (i, i + 1);
      var xs = A. slice (0, i) .concat (A. slice (i + 1));
      var subperms = Permutationen (xs);
      für (var j = 0; j <subperms.length; j ++) {
        perms.push (x.concat (subperms [j]));
      }}
    }}
    Dauerwellen zurückgeben;
  }}
};

var test = Funktion (A, Iterationen, Funktion) {
  // Permutationen initialisieren
  var stats = {};
  var perms = Permutationen (A);
  für (var i in Dauerwellen) {
    stats ["" + perms [i]] = 0;
  }}

  // viele Male mischen und Statistiken sammeln
  var start = neues Datum ();
  für (var i = 0; i <Iterationen; i ++) {
    var shuffled = func (A);
    stats ["" + shuffled] ++;
  }}
  var end = new Date ();

  // Ergebnis formatieren
  var arr = [];
  für (var i in stats) {
    arr.push (i + "" + stats [i]);
  }}
  return arr.join ("\ n") + "\ n \ nZeit:" + ((Ende - Start) / 1000) + "Sekunden";
};

alert ("zufällige Sortierung:" + Test ([1,2,3,4], 100000, randSort));
alert ("shuffle:" + test ([1,2,3,4], 100000, shuffle));
Rene Saarsoo
quelle
11

Interessanterweise verwendete Microsoft dieselbe Technik auf seiner Pick-Random-Browser-Seite.

Sie verwendeten eine etwas andere Vergleichsfunktion:

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

Sieht für mich fast gleich aus, aber es stellte sich heraus, dass es nicht so zufällig war ...

Also habe ich wieder einige Testläufe mit der gleichen Methode durchgeführt, die im verlinkten Artikel verwendet wurde, und tatsächlich stellte sich heraus, dass die Zufallssortierungsmethode zu fehlerhaften Ergebnissen führte. Neuer Testcode hier:

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"));
Rene Saarsoo
quelle
Ich verstehe nicht, warum es 0,5 sein muss - Math.random (), warum nicht einfach Math.random ()?
Alexander Mills
1
@AlexanderMills: Die übergebene Komparatorfunktion sort()soll je nach Vergleich von aund eine Zahl zurückgeben, die größer, kleiner oder gleich Null ist b. ( developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… )
LarsH
@ LarsH ja das macht Sinn
Alexander Mills
9

Ich habe eine einfache Testseite auf meiner Website platziert, die die Tendenz Ihres aktuellen Browsers im Vergleich zu anderen gängigen Browsern zeigt, die unterschiedliche Methoden zum Mischen verwenden. Es zeigt die schreckliche Tendenz, nur ein Math.random()-0.5anderes "zufälliges" Mischen zu verwenden, das nicht voreingenommen ist, und die oben erwähnte Fisher-Yates-Methode.

Sie können sehen, dass bei einigen Browsern eine Wahrscheinlichkeit von bis zu 50% besteht, dass bestimmte Elemente während des "Mischens" überhaupt nicht den Platz wechseln!

Hinweis: Sie können die Implementierung des Fisher-Yates-Shuffle von @Christoph für Safari etwas beschleunigen, indem Sie den Code in Folgendes ändern:

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;
}

Testergebnisse: http://jsperf.com/optimized-fisher-yates

Phrogz
quelle
5

Ich denke, es ist in Ordnung für Fälle, in denen Sie nicht wählerisch in Bezug auf die Verteilung sind und der Quellcode klein sein soll.

In JavaScript (wo die Quelle ständig übertragen wird) macht klein einen Unterschied bei den Bandbreitenkosten.

Nosredna
quelle
2
Die Sache ist, dass Sie in Bezug auf die Verteilung fast immer wählerischer sind, als Sie denken, und für "kleinen Code" gibt es immer einen arr = arr.map(function(n){return [Math.random(),n]}).sort().map(function(n){return n[1]});, der den Vorteil hat, dass er nicht zu lange dauert und tatsächlich richtig verteilt ist. Es gibt auch sehr komprimierte Knuth / FY-Shuffle-Varianten.
Daniel Martin
@ DanielMartin Dieser Einzeiler sollte eine Antwort sein. Um Analysefehler zu vermeiden, müssen zwei Semikolons hinzugefügt werden, damit es so aussieht : arr = arr.map(function(n){return [Math.random(),n];}).sort().map(function(n){return n[1];});.
Giacomo1968
2

Es ist sicherlich ein Hack. In der Praxis ist ein Endlosschleifenalgorithmus nicht wahrscheinlich. Wenn Sie Objekte sortieren, können Sie das Koordinatenarray durchlaufen und Folgendes tun:

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;
}

(und durchlaufen Sie sie dann erneut, um den sortValue zu entfernen.)

Trotzdem ein Hack. Wenn du es gut machen willst, musst du es auf die harte Tour machen :)

Thorarin
quelle
2

Es ist vier Jahre her, aber ich möchte darauf hinweisen, dass die Zufallsvergleichsmethode nicht korrekt verteilt wird, unabhängig davon, welchen Sortieralgorithmus Sie verwenden.

Beweis:

  1. Für ein Array von nElementen gibt es genau n!Permutationen (dh mögliche Mischvorgänge).
  2. Jeder Vergleich während eines Shuffle ist eine Wahl zwischen zwei Permutationssätzen. Für einen zufälligen Komparator besteht eine halbe Chance, jeden Satz auszuwählen.
  3. Somit ist für jede Permutation p die Chance, mit der Permutation p zu enden, ein Bruch mit dem Nenner 2 ^ k (für einige k), da es sich um eine Summe solcher Brüche handelt (z. B. 1/8 + 1/16 = 3/16) ).
  4. Für n = 3 gibt es sechs gleich wahrscheinliche Permutationen. Die Chance jeder Permutation beträgt also 1/6. 1/6 kann nicht als Bruch mit einer Potenz von 2 als Nenner ausgedrückt werden.
  5. Daher wird die Münzwurfsorte niemals zu einer fairen Verteilung der Mischvorgänge führen.

Die einzigen Größen, die möglicherweise korrekt verteilt werden könnten, sind n = 0,1,2.


Versuchen Sie als Übung, den Entscheidungsbaum verschiedener Sortieralgorithmen für n = 3 zu zeichnen.


Es gibt eine Lücke im Beweis: Wenn ein Sortieralgorithmus von der Konsistenz des Komparators abhängt und eine unbegrenzte Laufzeit mit einem inkonsistenten Komparator hat, kann er eine unendliche Summe von Wahrscheinlichkeiten haben, die sich zu 1/6 addieren kann, selbst wenn Jeder Nenner in der Summe ist eine Potenz von 2. Versuchen Sie, einen zu finden.

Wenn ein Komparator eine feste Chance hat, eine der beiden Antworten zu geben (z. B. (Math.random() < P)*2 - 1für eine Konstante P), gilt der obige Beweis. Wenn der Komparator stattdessen seine Gewinnchancen basierend auf früheren Antworten ändert, können möglicherweise faire Ergebnisse erzielt werden. Das Finden eines solchen Komparators für einen gegebenen Sortieralgorithmus könnte eine Forschungsarbeit sein.

leewz
quelle
1

Wenn Sie D3 verwenden, gibt es eine integrierte Shuffle-Funktion (mit Fisher-Yates):

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

Und hier geht Mike auf Details ein:

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

Renaud
quelle
0

Hier ist ein Ansatz, der ein einzelnes Array verwendet:

Die Grundlogik lautet:

  • Beginnend mit einem Array von n Elementen
  • Entfernen Sie ein zufälliges Element aus dem Array und schieben Sie es auf das Array
  • Entfernen Sie ein zufälliges Element aus den ersten n - 1 Elementen des Arrays und schieben Sie es auf das Array
  • Entfernen Sie ein zufälliges Element aus den ersten n - 2 Elementen des Arrays und schieben Sie es auf das Array
  • ...
  • Entfernen Sie das erste Element des Arrays und schieben Sie es auf das Array
  • Code:

    for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);
    ic3b3rg
    quelle
    Ihre Implementierung birgt ein hohes Risiko, dass eine erhebliche Anzahl von Elementen unberührt bleibt. Sie werden nur im gesamten Array um die Anzahl der minderwertigen Elemente verschoben, die nach oben gedrückt wurden. In diesem Mischen ist ein Muster gezeichnet, das es unzuverlässig macht.
    Kir Kanos
    @KirKanos, ich bin mir nicht sicher, ob ich deinen Kommentar verstehe. Die von mir vorgeschlagene Lösung ist O (n). Es wird definitiv jedes Element "berühren". Hier ist eine Geige zu demonstrieren.
    ic3b3rg
    0

    Können Sie die Array.sort()Funktion verwenden, um ein Array zu mischen - Ja.

    Sind die Ergebnisse zufällig genug - Nein.

    Betrachten Sie das folgende Code-Snippet:

    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(", ") + "]");
    })

    Beispielausgabe:

    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]

    Idealerweise sollten die Zählungen gleichmäßig verteilt sein (für das obige Beispiel sollten alle Zählungen bei etwa 20 liegen). Aber das sind sie nicht. Anscheinend hängt die Verteilung davon ab, welcher Sortieralgorithmus vom Browser implementiert wird und wie er die Array-Elemente zum Sortieren iteriert.

    Weitere Informationen finden Sie in diesem Artikel:
    Array.sort () sollte nicht zum Mischen eines Arrays verwendet werden

    Salman A.
    quelle
    -3

    Daran ist nichts auszusetzen.

    Die Funktion, die Sie normalerweise an .sort () übergeben sieht aus

    Funktion sortingFunc (erste, zweite)
    {
      // Beispiel:
      kehre zuerst zurück - zweitens;
    }}
    

    Ihre Aufgabe bei sortingFunc ist es, Folgendes zurückzugeben:

    • eine negative Zahl, wenn die erste vor der zweiten steht
    • eine positive Zahl, wenn die erste nach der zweiten gehen soll
    • und 0, wenn sie vollständig gleich sind

    Die obige Sortierfunktion ordnet die Dinge.

    Wenn Sie -s und + zufällig als das zurückgeben, was Sie haben, erhalten Sie eine zufällige Reihenfolge.

    Wie in MySQL:

    SELECT * aus der Tabelle ORDER BY rand ()
    
    Bobobobo
    quelle
    5
    es ist etwas falsch mit diesem Ansatz: Je nach Sortieralgorithmus in Verwendung durch die JS Implementierung werden die Wahrscheinlichkeiten nicht gleich verteilt werden!
    Christoph
    Ist das etwas, worüber wir uns praktisch Sorgen machen?
    Bobobobo
    4
    @bobobobo: je nach anwendung ja, manchmal tun wir das; Außerdem muss ein korrekt funktionierendes shuffle()Programm nur einmal geschrieben werden, sodass es nicht wirklich ein Problem ist: Legen Sie das Snippet einfach in Ihren Code-Tresor und graben Sie es aus, wann immer Sie es benötigen
    Christoph