Wie man ein Array in JavaScript randomisiert oder mischt

1. Mischen eines Arrays je nach JavaScript-Engine
2. Die Zufälligkeit unseres einfachen Algorithmus messen
3. Mischen eines Arrays mit dem Fisher-Yates Shuffle-Algorithmus
4. Mischen eines Arrays mit der Underscore.js- oder Lo-Dash-Bibliothek

In diesem Tutorial werden wir lernen, wie man ein Array in JavaScript mischt oder randomisiert; es gibt viele Möglichkeiten, ein Array in JavaScriptwie durch die Implementierung von Shuffle-Algorithmen oder durch die Verwendung bereits vorhandener Shuffle-Funktionen in einigen Bibliotheken zu mischen.

Ein Array zu mischen bedeutet, sein Element zufällig anzuordnen, es hängt also hauptsächlich davon ab, wie Sie das Array mit einem gewissen Zufallsgrad neu ordnen oder sortieren.

Gehen wir weiter und entdecken wir verschiedene Möglichkeiten, ein Array zufällig anzuordnen oder zu mischen.

Mischen eines Arrays je nach JavaScript-Engine

Beginnen wir mit der Implementierung eines einfachen Algorithmus zum Mischen von Arrays, indem wir das Array mit array.sort() sortieren, aber mit Hilfe einer gewissen Zufälligkeit, die durch die Gleichung Math.random() - 0.5 und -0.5 erzeugt wird, stellen wir sicher, dass jedes Mal, wenn wir den Algorithmus aufrufen, der Zufallswert positiv oder negativ sein kann.

Lassen Sie uns diesen einfachen Algorithmus mit der Leistungsfähigkeit der JavaScript-Engine implementieren und das gemischte Array mit Console.log() auf die Konsole drucken:

function shuffleArray(inputArray) {
  inputArray.sort(() => Math.random() - 0.5);
}

var demoArray = [1, 3, 5];
shuffleArray(demoArray);
console.log(demoArray);

Ausgabe:

[1, 5, 3]

Die Zufälligkeit unseres einfachen Algorithmus messen

Die Wahrscheinlichkeit der Permutationen dieses Arrays kann berechnet werden, um zu überprüfen, wie hervorragend und zufällig unser Algorithmus implementiert ist.

Lassen Sie uns sehen, wie wir seine Zufälligkeit messen können.

1. Erstellen Sie ein Dictionary, das das Auftreten für alle Permutationen zählt.
2. Erstellen Sie eine Schleife, die 1000000 Mal läuft und jedes Mal die Anzahl der gebildeten Permutationen erhöht.
3. Drucken Sie die Zählungen aller möglichen Permutationen aus und beobachten Sie die Wahrscheinlichkeiten zwischen ihnen.

Dieser einfache Messalgorithmus kann wie folgt implementiert werden:

function shuffleArray(inputArray) {
  inputArray.sort(() => Math.random() - 0.5);
}

// counts of the appearances for all possible permutations
var countDic = {
  '153': 0,
  '135': 0,
  '315': 0,
  '351': 0,
  '531': 0,
  '513': 0,
};

// Creating the loop
for (var i = 0; i < 1000000; i++) {
  var arr = [1, 5, 3];
  shuffleArray(arr);
  countDic[arr.join('')]++;
}

// Print the counts of all possible permutations
for (var key in countDic) {
  console.log(`${key}: ${countDic[key]}`);
}

Ausgabe:

135: 62256
153: 375832
315: 62976
351: 311865
513: 124518
531: 62553

Aus der obigen Ausgabe können wir die Verzerrung deutlich erkennen, da 135, 315 und 531 viel weniger als andere und damit ähnliche Zählungen erscheinen.

Mischen eines Arrays mit dem Fisher-Yates Shuffle-Algorithmus

Dieser einfache Algorithmus, der auf der JavaScript-Engine basiert, ist im vergangenen Abschnitt unzuverlässig, aber ein großartiger Algorithmus namens Fisher-Yates ist hinsichtlich seiner Effizienz und Zuverlässigkeit besser.

Die Idee hinter dem Fisher-Yates-Algorithmus ist es, in umgekehrter Reihenfolge zum Array zu gehen und jedes Element mit einem zufälligen vor ihm zu vertauschen. Fisher-Yates ist ein einfacher, aber sehr effizienter und schneller Algorithmus.

Lassen Sie uns den Fisher-Yates-Algorithmus implementieren:

function fisherYatesShuffle(arr) {
  for (var i = arr.length - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));  // random index
    [arr[i], arr[j]] = [arr[j], arr[i]];          // swap
  }
}

var tmpArray = [1, 3, 5];
fisherYatesShuffle(tmpArray);
console.log(tmpArray);

Erklären wir ihn also Schritt für Schritt:

1. for(var i =array.length-1 ; i>0 ;i--) eine for-Schleife, die in umgekehrter Reihenfolge auf dem Array läuft.
2. Math.floor( Math.random() * (i + 1) ) Generierung eines Zufallsindex, der zwischen 0 und i liegt.
3. [arr[i],arr[j]]=[arr[j],arr[i]] vertauscht die Elemente arr[i] und arr[j] miteinander unter Verwendung der Syntax Destructuring Assignment.

Ausgabe:

(3) [3, 1, 5]

Nun lassen Sie uns Fisher-Yates testen, wie wir es zuvor getan haben:

// counts of the appearances for all possible permutations
var countDic = {
  '153': 0,
  '135': 0,
  '315': 0,
  '351': 0,
  '531': 0,
  '513': 0,
};

// Creating the loop
for (var i = 0; i < 1000000; i++) {
  var arr = [1, 5, 3];
  fisherYatesShuffle(arr);
  countDic[arr.join('')]++;
}

// Print the counts of all possible permutations
for (var key in countDic) {
  console.log(`${key}: ${countDic[key]}`);
}

Ausgabe:

135: 166734
153: 166578
315: 166908
351: 166832
513: 166535
531: 166413

Aus der obigen Ausgabe sehen Sie den großen Unterschied zwischen dem Fisher-Yates-Algorithmus und dem einfachen Algorithmus, den wir vorher implementiert haben, und wie zuverlässig der Fisher-Yates-Algorithmus ist.

Mischen eines Arrays mit der Underscore.js- oder Lo-Dash-Bibliothek

Die berühmte Underscore.js-Bibliothek bietet auch eine Shuffle-Funktion, mit der ein Array direkt randomisiert werden kann, ohne dass Sie Ihre Implementierung eines Algorithmus schreiben müssen.

Lassen Sie uns das folgende Beispiel für die Verwendung der _.shuffle() Methode sehen.

Zuerst müssen wir die Bibliothek unter Verwendung von Cloudflare CDN innerhalb der HTML-Vorlage importieren,

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.15/lodash.min.js"></script>

Dann verwenden wir die _.shuffle() Methode wie:

var tmpUnderscoreArray = [1, 3, 5];
resultArray = _.shuffle(tmpUnderscoreArray);
console.log(resultArray);

Ausgabe:

(3) [1, 5, 3]