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

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.

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.

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.

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

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"));

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

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.

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 :)

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.

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/

Hier ist ein Ansatz, der ein einzelnes Array verwendet:

Die Grundlogik lautet:

Code:

for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[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

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 ()