Der Mischungsalgorithmus ist ein häufiges zufälliges Problem, auf das wir beim Spielen und zufällig sortierenden Sortieren stoßen. Es kann so abstrahiert werden: Holen Sie sich eine zufällige Reihenfolge aller natürlichen Zahlen innerhalb von M.
Auf der Suche nach "Reshuffle -Algorithmus" auf Baidu war das erste Ergebnis "Baidu Library - Umschulungsalgorithmus". Nach dem Scannen des Inhalts sind viele der Inhalte leicht in die Irre zu führen, einschließlich der Verwendung verknüpfter Listen zum Ersetzen von Arrays am Ende, was nur eine begrenzte Optimierung darstellt (Linklisten führen auch den Verlust der Lese -Effizienz ein).
Die erste Methode in diesem Artikel kann einfach als: zufällig Karten zeichnen und in eine andere Gruppe einfügen; Zeichnen Sie sie erneut und zeichnen Sie sie wiederholt, wenn Sie die leeren Karten zeichnen.
"Zeichnen Sie die Karten, nachdem Sie sie wieder gezogen haben" wird dazu führen, dass die Chance der Karten später zunimmt, was offensichtlich unangemessen ist.
Ein Schritt kann optimiert werden: Nachdem die Karten gezogen wurden, werden die Originalkarten weniger. (anstatt leere Karten zu lassen)
Der Code ist wie folgt:
Die Codekopie lautet wie folgt:
Funktion shuffle_pick_1 (m) // Shush // Kartenzeichnung Methode
{
// M -Karten erzeugen
var arr = new Array (m);
für (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Zeichne jeweils eine Karte und lege sie auf einen anderen Stapel. Da Sie Elemente aus dem Array extrahieren und alle nachfolgenden Elemente nacheinander nach vorne ziehen müssen, ist es zeitaufwändig.
var arr2 = new Array ();
für (var i = m; i> 0; i--) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
Arr.SPLICE (RND, 1);
}
arr2 zurückgeben;
}
Dies ist auch offensichtlich problematisch, denn wenn das Array groß ist, führt die Löschung eines bestimmten Elements in der Mitte dazu, dass die Warteschlange einen Schritt nach vorne macht, was eine sehr zeitaufwändige Aktion ist.
Erinnern Sie sich an den Zweck von "Warum löschen wir dieses Element?" ist leere Karten zu vermeiden.
Haben wir neben dem Löschen dieses Elements auch andere Möglichkeiten, leere Karten zu entfernen?
---- Ja, wir müssen nur die letzte, nicht protedische Karte in die Ziehposition setzen.
Wir können diese Idee also wie folgt optimieren:
Die Codekopie lautet wie folgt:
Funktion shuffle_pick (m) // Shut // Kartenzeichnung, um die Karte zu optimieren
{
// M -Karten erzeugen
var arr = new Array (m);
für (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Zeichne jeweils eine Karte und lege sie auf einen anderen Stapel. Legen Sie die letzte nicht festgelegte Karte auf den offenen Platz.
var arr2 = new Array ();
für (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
arr2 zurückgeben;
}
Neben der Idee des Zeichnens von Karten können wir auch die Idee des Kartenwechsels verwenden.
"Baidu Wenku-Shut-Algorithmus" erwähnt eine Kartenänderungsidee: "Wechseln Sie zwei Positionen zufällig und tauschen Sie sie insgesamt n-mal aus. Je größer das N ist, desto näher ist es zufällig."
Dieser Ansatz ist falsch. Selbst wenn N sehr groß ist (z. B. 10 Karten, 10 Schalter), besteht immer noch eine hohe Möglichkeit, dass "einige Karten überhaupt keine Positionen ändern".
Befolgen Sie diese Idee und nehmen Sie ein wenig Anpassung vor: Ändern Sie die I-Th-Karte mit jeder Karte und ändern Sie sie einfach für eine Runde.
Der Code ist wie folgt:
Die Codekopie lautet wie folgt:
Funktion shuffle_swap (m) // Shush // Kartenänderungsmethode
{
// M -Karten erzeugen
var arr = new Array (m);
für (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Die I-Th-Karte wird verwendet, um die Sitze zu ändern, und Sie können sie für eine Runde ändern
für (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
arr zurückgeben;
}
Zusätzlich zu der Idee, Karten zu zeichnen und zu wechseln, können wir auch die Idee verwenden, Karten einzufügen
Der Code ist wie folgt:
Die Codekopie lautet wie folgt:
Funktion shuffle_insert_1 (m) // shunt // Karteninsertionsmethode
{
// Jedes Mal wird die größte Karte erzeugt und vor einer Zufallskarte eingefügt. Da Sie Elemente in das Array einfügen und alle nachfolgenden Elemente nacheinander zurückdrücken müssen, ist es zeitaufwändig.
var arr = [0];
für (var i = 1; i <m; i ++) {
arr
}
arr zurückgeben;
}
Der obige Code hat auch einige Probleme: Wenn die Anzahl der Karten zunimmt, wird es immer schwieriger, Karten einzufügen, da das Einfügen von Karten zu vielen Karten führt, die einen Schritt zurück folgen.
Natürlich können wir auch angemessen optimieren: Zuerst gibt es eine N-1-Karte, die N-TH-Karte wird am Ende platziert und dann Positionen mit jeder Karte austauschen.
Der Code ist wie folgt:
Die Codekopie lautet wie folgt:
Funktion shuffle_insert (m) // Shush // Optimierte Version der Karteninsertionsmethode kann durch mathematische Induktion nachgewiesen werden, dass dieser Shuffle einheitlich ist.
{
// erzeugt jedes Mal die größte Karte und wechselt Positionen mit einer Zufallskarte aus
var arr = new Array (m);
arr [0] = 0;
für (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
arr zurückgeben;
}
Ok, alle Codes sind wie folgt. Interessierte Schüler können sie auf ihrer eigenen Maschine ausprobieren, um festzustellen, ob ihre jeweilige Ausführungseffizienz und ob das Endergebnis theoretisch zufällig ist.
Die Codekopie lautet wie folgt:
<html>
<kopf>
<meta http-äquiv = "content-type" content = "text/html; charset = gb2312">
<titels> JK: JavaScript -Mischalgorithmus </title>
</head>
<body>
<script type = "text/javaScript">
Funktion shuffle_pick_1 (m) // Shush // Kartenzeichnung Methode
{
// M -Karten erzeugen
var arr = new Array (m);
für (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Zeichne jeweils eine Karte und lege sie auf einen anderen Stapel. Da Sie Elemente aus dem Array extrahieren und alle nachfolgenden Elemente nacheinander nach vorne ziehen müssen, ist es zeitaufwändig.
var arr2 = new Array ();
für (var i = m; i> 0; i--) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
Arr.SPLICE (RND, 1);
}
arr2 zurückgeben;
}
Funktion shuffle_pick (m) // Shut // Kartenzeichnung, um die Karte zu optimieren
{
// M -Karten erzeugen
var arr = new Array (m);
für (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Zeichne jeweils eine Karte und lege sie auf einen anderen Stapel. Legen Sie die letzte nicht festgelegte Karte auf den offenen Platz.
var arr2 = new Array ();
für (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
arr2 zurückgeben;
}
Funktion shuffle_swap (m) // Shush // Kartenänderungsmethode
{
// M -Karten erzeugen
var arr = new Array (m);
für (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Die I-Th-Karte wird verwendet, um die Sitze zu ändern, und Sie können sie für eine Runde ändern
für (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
arr zurückgeben;
}
Funktion shuffle_insert_1 (m) // shunt // Karteninsertionsmethode
{
// Jedes Mal wird die größte Karte erzeugt und vor einer Zufallskarte eingefügt. Da Sie Elemente in das Array einfügen und alle nachfolgenden Elemente nacheinander zurückdrücken müssen, ist es zeitaufwändig.
var arr = [0];
für (var i = 1; i <m; i ++) {
arr
}
arr zurückgeben;
}
Funktion shuffle_insert (m) // Shush // Optimierte Version der Karteninsertionsmethode kann durch mathematische Induktion nachgewiesen werden, dass dieser Shuffle einheitlich ist.
{
// erzeugt jedes Mal die größte Karte und wechselt Positionen mit einer Zufallskarte aus
var arr = new Array (m);
arr [0] = 0;
für (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
arr zurückgeben;
}
// alarm (shuffle_pick (10))
var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
funcnames = ["Karte zeichnen", "Kartenoptimierung zeichnen", "Kartenänderung", "Karteneinfügung", "Karteneinfügungsoptimierung"]
M = 10000,
mal = [];
für (var i = 0; i <funcs.length; i ++) {
var d0 = neues Datum ();
Funcs [i] (m);
funcnames [i] = (new Date () - d0) + '/t' + funcnames [i];
}
alert (funcnames.join ('/n'));
</script>
</body>
</html>