Panda Noir

JavaScript の限界を究めるブログです。

世界最速の配列シャッフルアルゴリズム、Fisher-Yatesアルゴリズム

調べ物をしていたら、Fisher–Yatesというアルゴリズムを見つけました。有名なのかな?とにかく考え方がとてもシンプルでよかったので紹介します。

Fisher–Yatesって何?

Fisher–Yatesとは、要するにシャッフルする方法のひとつです。最速です。

どういうアルゴリズム?

Fisher–Yatesは、 配列からランダムに要素を抽出して並べていくアルゴリズム です。そのままですね。では、実装されたコードを紹介します。実物を解説した方が早そうなので。コードは配列を少ない仕事量でシャッフルするFisher-Yates法参照です。

var n = arr.length;
for(var i = n - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));
    var tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

私が関数化してさらに高速化施したコード

function shuffle(arr){
    for (var i = arr.length - 1; i > 0; i = 0 | i - 1) {
        var j = 0 | Math.random() * (i + 1);
        var swap = arr[i];
        arr[i] = arr[j];
        arr[j] = swap;
    }
}

コードの小ささに重きを置いたコード

function shuffle(arr){
    for (var i = arr.length; i--;) {
        var j = 0 | Math.random() * (i + 1);
        arr[i] = [arr[j], arr[j] = arr[i]][0];
    }
}

破壊的変更を加えない関数も作ろうとしましたが、オブジェクトを格納した配列を渡された時に予期しない挙動を起こしかねないのでやめました。

アルゴリズム解説

このアルゴリズム、一見ただ単に適当に後ろへ並べているように見えます。しかし、これでもきちんとランダムに並べ替えられています。

このアルゴリズムのポイントは、 入れ替えられた数字が2回入れ替わることがない という点です。

このアルゴリズムでは、i(つまり、後ろから回しているループの現在地点)と、iより前のランダムに選ばれた要素を入れ替えます。 iは、はじめは配列arrの長さ分-1、つまりarrの末尾を指しています。そして1回入れ替えるごとにiは1つずつ減っていきます。 一度ランダムに選ばれた要素は i の位置に回され、i はひとつ減るので入れ替えられた要素はもう選ばれることはありません 。だからランダムに並べ替えることができるのです。

実は、このアルゴリズムは本質的には配列から一個ずつ要素をランダムに抽出して別の配列に追加していくのとなんら変わりありません(ちなみに別の配列に追加していく方法だと抜き出した配列の穴を埋めるため、配列の再構築する必要があり時間がかかります)。 i より前部分が与えられた配列で、iから後ろが新しい配列と考えると分かりますね。

ちなみに一つずつ抽出して別の新しい配列に入れていくコードはこちら

function shuffle2(arr){
    // arrに破壊的変更を加える
    var result = [];
    for(var len = arr.length; len > 0; len = 0 | len - 1) {
        var i = 0 | Math.random() * len;
        result.push(arr[i]);
        arr.splice(i, 1);
    }
    return result;
}
// arr = shuffle2(arr);

みるとわかると思いますが、shuffle2()はほぼshuffle()と同じです。

さて、ここまでの解説で理解していただけたかと思いますが、Fisher-Yatesは 計算量が配列の長さ分 しかないため時間がかかりません。これが最速と呼ばれる所以です。

終わりに

Fisher-Yatesアルゴリズムはきちんと論理立てられて、簡潔化、最適化されています。 しかし、論理的で簡潔であるがゆえに直感的でなくわかりづらいです。この解説がみなさんの理解の助けになったらうれしいです。