Elemente eines Array mischen
Im Gegensatz zum Sortieren eines Array sucht man beim Array-Objekt lange nach einer Methode "shuffle()". Man kann sich jedoch eine solche Methode selbst schreiben und sie dann dem Array-Objekt am Besten via prototyping zuordnen.
Der hier vorgestellte Algorithmus arbeitet nach folgende Maßgaben:
- Durchlaufe das zu mischende Array
- Erzeuge eine Zufallszahl zwischen 0 und der Länge des zu mischende Arrays
- Vertausche das Element an der aktuellen Position mit dem Element an der soeben zufällig bestimmten Stelle
Der Algorithmus hat zur Folge, dass jedes Element mindestens einmal vertauscht und an eine zufällig ausgewählte Position gesetzt wird. Allerdings kann ein Element dabei auch mehrfach vertauscht werden, was den Algorithmus dagegen sicher nicht schwächer macht.
Das Script dazu sieht folgendermaßen aus:
function arrayShuffle(){
var tmp, rand;
for(var i =0; i < this.length; i++){
rand = Math.floor(Math.random() * this.length);
tmp = this[i];
this[i] = this[rand];
this[rand] =tmp;
}
}
Array.prototype.shuffle =arrayShuffle;
Durch zuweisen dieser Funktion an den Array Prototypen, lässt sich jedes Array durch arrayInstance.shuffle() mischen. Beispiel:
var zahlen = new Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
zahlen.shuffle();
var ausgabe = zahlen.join(", ");
alert(ausgabe);
Die Performance ist natürlich abhängig vom Rechner, auf dem diese Methode ausgeführt wird. Vor einigen Jahren (ich denke es war 2002) habe ich einen Performance-Test auf einem AMD K6/2 mit 128 MB RAM ausgeführt. Die Ergebnisse damals lauteten:
| # Arrayeinträge | MSIE 5.5 [Win95] | NN 4.6 [Win95] | Opera 6.0 [Win95] | Mozilla 0.97 [Win95] |
|---|---|---|---|---|
| Test auf einem AMD K6/2 mit 128 MB RAM | ||||
| 500 | 50 ms | 110 ms | 270 ms | 160 ms |
| 5.000 | 110 ms | 550 ms | 1.820 ms | 1.380 ms |
| 10.000 | 330 ms | 1.480 ms | 4.670 ms | 2.750 ms |
| 50.000 | 1.650 ms | 7.750 ms | 23.780 ms | 14.120 ms |
2005 habe ich den Test wiederholt:
| # Arrayeinträge | MSIE 5.5 [Win2k] | Firefox [Linux] | Opera 8.5 [Linux] | Konquerer 3.4 [Linux] |
|---|---|---|---|---|
| Test auf einem AMD Athlon(tm) XP 2600+ mit 512 MB RAM | ||||
| 500 | -- | 2 ms | 1 ms | 7 ms |
| 5.000 | -- | 22 ms | 23 ms | 63 ms |
| 10.000 | -- | 69 ms | 44 ms | 125 ms |
| 50.000 | -- | 484 ms | 236 ms | 1095 ms |
Das Skript zum Performance-Test auf dem eigenen Rechner steht auch zur Verfügung.
Die hier vorgestellte Lösung wurde von mir am 30. Juni 2000 in der Newsgroup dcljs gepostet und von Thomas Fischer in diese Form gebracht. Das Original findet sich unter der Msg. Id <8ji56q$llhh$1@ID-19598.news.cis.dfn.de>