はじめに
JavaScriptでArrayの中身をシャッフルしたいことがあり、
そういえばどういう仕組みなんだろうと考えたことがきっかけで調べてみることにしました。
フィッシャー–イェーツの手法
ウィキペディアを参考に考えてみます。
前提
ここに1から5までの数字が格納された配列があります。
これをフィッシャー–イェーツの手法でシャッフルしてみます。
array = [1, 2, 3, 4, 5]
1. 1 から N までの数字を書く。
前提で準備した配列の状態から N は 5 です。
[1, 2, 3, 4, 5]
2. まだ消されてない数字の数を数え、1 からその数以下までのランダムな数字 k を選ぶ。
まだ消されていない数字の数 は 5(array.length)です。
配列なので0から4までのランダムな数字 k を求めます。
n = array.length
k = Math.floor(Math.random() * n); // 3
ランダムな数字 3 が出力されました。
3. 残っている数字から k 番目の数字を消し、別の場所にその数字を書き出す。
配列 array の 3 番目の数字を別の配列( newArray )に移します。
配列 array の 3 番目を削除します。
newArray = []
newArray.push(array[k]); // array の3番目を newArray に追加
array.splice(k, 1); // array の3番目を削除
console.log(newArray); // [4]
console.log(array); // [1, 2, 3, 5]
4. すべての数字が消されるまで手順 2, 3 を繰り返す。
arrayのlengthが0になるまで繰り返すそうです。
1回目からarrayのlengthが0になるまで繰り返してみます。
n |
array |
newArray |
k |
3の手順実行後のarray
|
3の手順実行後のnewArray
|
|---|---|---|---|---|---|
| 5 | [1,2,3,4,5] | [] | 3 | [1,2,3,5] | [4] |
| 4 | [1,2,3,5] | [4] | 0 | [2,3,5] | [4,1] |
| 3 | [2,3,5] | [4,1] | 2 | [2,3] | [4,1,5] |
| 2 | [2,3] | [4,1,5] | 1 | [2] | [4,1,5,3] |
| 1 | [2] | [4,1,5,3] | 0 | [] | [4,1,5,3,2] |
※nはarrayの残り個数、kは0からnまでのランダムな数字です。
5. 手順 3 で書かれた数列が元の数値からのランダム順列となる。
手順 3 で書かれた数列は newArray です。
最終的なnewArrayの値は [4, 1, 5, 3, 2] となりました。
JavaScriptでやってみる
array = [1, 2, 3, 4, 5];
newArray = [];
while (array.length > 0) {
n = array.length;
k = Math.floor(Math.random() * n);
newArray.push(array[k]);
array.splice(k, 1);
}
console.log("ランダムな数列", newArray);
ランダムな数列 [ 2, 4, 1, 5, 3 ]
ランダムな数列 [ 3, 1, 5, 4, 2 ]
シャッフルされてそうですね。
ダステンフェルドの手法
上記の手順3において、残っている数を数え上げるという不要な時間を要する。
残っている数を数え上げてるの手順2じゃね？。。。
確かに毎回残っている数を数え上げる処理はもったいない気がしますね。
もし、配列の要素数が大きい場合、時間がかかりそう。
そこで改良されたアルゴリズムが ダステンフェルドの手法 です。
この方法は添字を利用し、配列の個数 - 1回、カウントダウンのループ処理を行います。
ループ毎に0から添字 - 1までのランダムな数字kを求め、
配列の添字 - 1番目とk番目を交換する方法です。
最後の 1 回、ループをスキップする理由は、手順の方に書きます。
フィッシャー–イェーツの手順にダステンフェルドの手法を組み込んでみます。
1. 1 から N までの数字を書く。
準備した配列の状態から N は 5 です。
[1, 2, 3, 4, 5]
2. 0 から添字までのランダムな数字 k を選ぶ。
ランダムな数字は 0 から i - 1 から求めます。
添字 i は、配列の要素数からスタートするので、
初回は 0 から 4 までのランダムな数字を求めます。
この方法で、添字をカウントダウンし、 N - 1 回繰り返されます。
ループの最後は i - 1 が 0の為、 0から0までのランダムな数字は0です。
配列のi - 1番目とk番目を交換しますが、 0 番目と 0 番目の交換は意味が無いのでスキップします。
添字 i に配列の要素数を定義し、カウントダウンしますが初回のイメージは以下です。
i = array.length
k = Math.floor(Math.random() * i); // 3
こちらもランダムな数字 3 が出力されたものとして考えます。
3. k 番目の数字を i - 1 番目の数字と入れ替える。
この方法では、別の領域(newArray)を使いません。
[array[k], array[i - 1]] = [array[i - 1], array[k]]; // array の3番目と4番目を入れ替え
console.log(array); // [1, 2, 3, 5, 4]
4. 添字が 0 になるまで手順 2, 3 を繰り返す。
for (i = array.length; 1 < i; i--) {
// 手順 `2`, `3` の処理
}
i |
array |
k |
3の手順実行後のarray
|
|---|---|---|---|
| 5 | [1,2,3,4,5] | 3 | [1,2,3,5,4] |
| 4 | [1,2,3,5,4] | 0 | [5,2,3,1,4] |
| 3 | [5,2,3,1,4] | 2 | [5,2,3,1,4] |
| 2 | [5,2,3,1,4] | 0 | [2,5,3,1,4] |
※iは添字、kは0からi - 1までのランダムな数字です。
5. 手順 3 で書かれた数列が元の数値からのランダム順列となる。
手順 3 で array 内の入れ替えを行っているだけなので array が答えです。
最終的なarrayの値は [2, 5, 3, 1, 4] となりました。
JavaScriptでやってみる
array = [1, 2, 3, 4, 5];
for (i = array.length; 1 < i; i--) {
k = Math.floor(Math.random() * i);
[array[k], array[i - 1]] = [array[i - 1], array[k]];
}
console.log("ランダムな数列", newArray);
ランダムな数列 [ 4, 2, 1, 5, 3 ]
ランダムな数列 [ 3, 2, 4, 5, 1 ]
こちらもちゃんとシャッフルされてそうですね。
計測してみる
配列の要素数 10件
| fisherYates | dustenfeld |
|---|---|
| 0.00011 s | 0.00006 s |
| 0.00008 s | 0.00006 s |
| 0.00012 s | 0.00006 s |
| 0.00009 s | 0.00018 s |
| 0.00008 s | 0.00006 s |
あまり差はでないですね。
配列の要素数 10万件
| fisherYates | dustenfeld |
|---|---|
| 1.93609 s | 0.00702 s |
| 2.12999 s | 0.00746 s |
| 1.92727 s | 0.00681 s |
| 1.93922 s | 0.00691 s |
| 1.98414 s | 0.00679 s |
書き方かもしれませんが、ダステンフェルドの手法が断トツ速いです。
終わりに
Rubyにはshuffleメソッドがあるので、楽ですね。
ソースはこちらに置いてます。