Eingehende Analyse der Fähigkeiten des Javascript-Zufallsmischalgorithmus_Javascript

Der Mischalgorithmus ist ein häufiges Zufallsproblem, auf das wir beim Spielen und beim Zufallssortieren häufig stoßen. Es kann wie folgt abstrahiert werden: Erhalten Sie ein Zufallsfolgen-Array aller natürlichen Zahlen innerhalb von M.

Bei der Suche nach „Shuffling-Algorithmus“ auf Baidu ist das erste Ergebnis „Baidu Library-Shuffling-Algorithmus“. Nach dem Scannen des Inhalts können viele Inhalte andere leicht in die Irre führen, einschließlich der Verwendung verknüpfter Listen anstelle von Arrays Es handelt sich auch nur um eine begrenzte Optimierung (verknüpfte Listen führen auch zu einem Verlust der Leseeffizienz).

Die erste Methode in diesem Artikel kann einfach beschrieben werden: Ziehen Sie zufällig Karten und legen Sie sie in eine andere Gruppe. Wenn Sie eine leere Karte ziehen, wiederholen Sie das Ziehen.
„Wenn du eine leere Karte ziehst, ziehe sie noch einmal.“ Dadurch erhöht sich die Chance, später eine leere Karte zu ziehen, was offensichtlich unvernünftig ist.
Es kann in einem Schritt optimiert werden: Nach dem Entfernen der Karten werden die ursprünglichen Karten reduziert. (Anstatt eine leere Karte zu hinterlassen)
Der Code lautet wie folgt:

Kopieren Sie den CodeDer Code lautet wie folgt:

function shuffle_pick_1(m) //Shuffle//Kartenziehmethode
{
//m Karten generieren
var arr = new Array(m);
for (var i=0 ; i arr[i] = i;
}

//Zeichne jedes Mal eine Karte und lege sie auf einen anderen Stapel. Da Sie Elemente aus dem Array extrahieren und alle nachfolgenden Elemente um eins nach vorne ziehen müssen, ist dies sehr zeitaufwändig.
var arr2 = new Array();
for (var i=m; i>0; i--) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}

Das ist natürlich auch problematisch, denn wenn das Array sehr groß ist, führt das Löschen eines Elements in der Mitte dazu, dass die nachfolgende Warteschlange nach vorne verschoben wird, was eine sehr zeitaufwändige Aktion ist.
Erinnern Sie sich: „Warum wollen wir dieses Element löschen?“ Der Zweck besteht nicht darin, leere Karten zu erstellen.
Gibt es für uns neben dem Löschen dieses Elements noch andere Möglichkeiten, leere Karten zu entfernen?
----Ja, wir legen einfach die letzte nicht gezogene Karte in die gezogene Position.
So können wir diese Idee wie folgt optimieren:

Code kopieren Der Code lautet wie folgt:

function shuffle_pick(m) //shuffle/ /pump Kartenoptimierungskarte
{
// m Karten generieren
var arr = new Array(m);
for (var i=0; i arr [i] = i;
}

//Zeichne jedes Mal eine Karte und lege sie auf einen anderen Stapel. Legen Sie die letzte nicht gezogene Karte auf den freien Platz.
var arr2 = new Array();
for (var i=m; i>0;) {
var rnd = Math.floor(Math.random()*i);
arr2 .push(arr[rnd]);
arr[rnd] = arr[--i];
}
return arr2;
}

Außer beim Zeichnen Karten Als Idee können wir auch die Idee des Kartenwechsels nutzen.
„Baidu Wenku – Shuffling Algorithm“ erwähnt eine Idee zum Kartenwechsel: „Vertausche zwei Positionen nach dem Zufallsprinzip insgesamt n-mal. Je größer n ist, desto näher kommt es dem Zufall.“
Dieser Ansatz ist falsch. Selbst wenn n sehr groß ist (z. B. 10 Karten, 10 Swaps), besteht immer noch eine hohe Wahrscheinlichkeit, dass „einige Karten ihre Position überhaupt nicht geändert haben“.
Um dieser Idee zu folgen, nehmen Sie einfach eine kleine Anpassung vor: Ändern Sie die Position der i-ten Karte durch eine beliebige andere Karte und schließen Sie dann die Runde ab.
Der Code lautet wie folgt:

Code kopieren Der Code lautet wie folgt:

function shuffle_swap(m) //shuffle/ /swap Card method
{
// M Karten generieren
var arr = new Array(m);
for (var i=0; i arr[ i ] = i;
}

//Tausche die i-te Karte nach einer Runde mit einer beliebigen Karte
for (var i=0; i var rnd = Math.floor( Math.random()* (i 1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}

Neben der Idee, Karten zu ziehen und auszutauschen, können wir auch die Idee des Einlegens von Karten nutzen: Es gibt zuerst eine Karte, die zweite Karte hat zwei Positionen, die zufällig eingefügt werden können (vor oder nach dem erste Karte) und die dritte Es gibt drei Positionen, an denen eine Karte nach dem Zufallsprinzip eingefügt werden kann (hinten, oder an der ersten Stelle, oder an der zweiten Stelle) und so weiter
Der Code lautet wie folgt:

Code kopieren Der Code lautet wie folgt:

function shuffle_insert_1(m) //shuffle/ /insert Card method
{
//Generiere jedes Mal die größte Karte und füge sie vor einer zufälligen Karte ein. Da Sie Elemente in das Array einfügen und alle nachfolgenden Elemente um eine Position zurückschieben müssen, ist dies sehr zeitaufwändig.
var arr = [0];
for (var i=1; i arr.splice(Math.floor(Math.random()*(i 1)), 0,i);
}
return arr;
}

Der obige Code weist auch einige Probleme auf: Mit zunehmender Kartenanzahl wird das Einlegen von Karten immer schwieriger, da durch das Einlegen von Karten viele nachfolgende Karten zurückgeschoben werden.
Natürlich können wir es auch entsprechend optimieren: Zuerst gibt es n-1 Karten, am Ende kommt die n-te Karte und dann tauscht sie mit einer beliebigen Karte die Position.
Der Code lautet wie folgt:

Code kopieren Der Code lautet wie folgt:

function shuffle_insert(m) //shuffle/ /insert Die optimierte Version der Kartenmethode kann durch mathematische Induktion bewiesen werden, dass diese Art des Mischens gleichmäßig ist.
{
//Erzeuge jedes Mal die höchste Karte und tausche die Plätze mit einer zufälligen Karte
var arr = new Array(m);
arr[0] = 0;
for (var i=1; i var rnd = Math.floor(Math.random()*(i 1));
arr[i] = arr[rnd] ;
arr [rnd] = i;
}
return arr;
}

Okay, der gesamte Code lautet wie folgt. Interessierte Schüler können ihn auf ihren eigenen Computern ausprobieren, um zu sehen, wie effizient sie ausgeführt werden und ob das Endergebnis theoretisch zufällig ist.

Code kopieren Der Code lautet wie folgt:

< title>JK：Javascript-Shuffling-Algorithmus