先日、When Random Isn't Random Enough: Lessons from an Online Poker Exploit（英文注意）という記事がタイムラインに流れてきて、同僚と少し配列ランダマイズの話になったので備忘録として書いておきます。
配列のランダマイズというのは、たとえば上の記事にあるようなトランプのシャッフルであるとか、音楽プレイヤーの再生リストのランダム再生とかで実装しますね。ゲームを作るときなどには実装することが多いでしょうが、記事を読む前に、自分だったらどのように実装するか是非少し考えてみてください。
自分が中学生の頃に書いた記憶のあるコードは、たしか次のようなものでした。
// 配列の初期化
var a = [];
for(var i = 0; i < 1000; i++) {
a[i] = i;
}
function swap(s, d) {
var t = a[s];
a[s] = a[d];
a[d] = t;
}
// ランダマイズ、その1
for(var i = 0; i < 100000; i++) {
swap((Math.random() * a.length) | 0, (Math.random() * a.length) | 0);
}
このコードは簡単に言うと、ランダムに2つの要素を取り出して交換する実装です。例として10万回シャッフルしましたが、実際何回シャッフルするのが正しいのでしょうか。</p>
仮にこれが1回だとまったくシャッフルできていないのは明らかですね。1000回でもシャッフル出来たとはいえないでしょう。配列の長さが1000なので、1000回のシャッフルだと1回もシャッフルの対象にならないカードが相当数存在することが予想されます。直感で100枚以上はもとの位置にありそうで、1000回のシャッフルではまったく使い物になりません。
では1万回？10万回？理論上は無限回のシャッフルをすれば良いのでしょうが、10万回のループでも重いのに無限なんてとんでもない。もし仮に「これだけシャッフルすれば大丈夫」という指標が出来たとしても、配列の個数に対して指数関数的にシャッフル回数が伸びてしまうことでしょう。まったく駄目なアルゴリズムですね！
さて、上記のアルゴリズムの問題は、すべて配列要素が確実にシャッフルの対象にならないことでした。というわけで、それを修正したアルゴリズムを思いつくのは自然だと思います。次のような感じですね。
// 配列の初期化
var a = [];
for(var i = 0; i < 1000; i++) {
a[i] = i;
}
function swap(s, d) {
var t = a[s];
a[s] = a[d];
a[d] = t;
}
// ランダマイズ、その2
for(var i = 0; i < a.length; i++) {
swap(i, (Math.random() * a.length) | 0);
}
これだと、すべての配列要素が必ず1回はシャッフルの対象になります。ランダマイズのfor文も配列の要素数のみになるので、計算量もたいしたことがありません。すべての要素がシャッフルされ、一見問題ないように見えます。しかし、これは上の記事で「問題を抱えている」と指摘されていたアルゴリズムまさにそのものになります。実際問題、このランダマイズのコードは使い物になりません。一体上記のアルゴリズムのどこが問題か、わかるでしょうか？</p>
解説は大変長くなりそうなので、一旦ここで記事を切ります。後編は→こちら！