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;
    }
}

圧縮したコード

// ES2015不使用版
function shuffle(a,i,j){for(i=a.length;a[j=0|Math.random()*i]=[a[--i],a[i]=a[j]][0],i;);}

// ES2015使用版
const shuffle=(a,i=a.length,j)=>{for(;[a[i],a[j]]=[a[j=0|Math.random()*i],a[--i]],i;);};

このアルゴリズムは一見すると適当に並べているように見えますが、きちんとランダムに並べ替えられます。

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

入れ替えた要素が再び移動することはない

  1. Fisher-yatesはループの現在地点iと、iより前にある要素からランダムに選んで入れ替える
  2. iは、はじめは配列の末尾を指していて、1回入れ替えるごとに1つずつ減っていく

つまり、一度選ばれた要素は i の位置に回されてi はひとつ減るので、入れ替えられた要素が再び選ばれることはありません 。見方を変えると、配列を「入れ替えていない要素」と「入れ替え済みの要素」に分け、iは入れ替えていない要素の末尾を指していると考えられます。だからランダムに並べ替えられます。

f:id:panda_noir:20190329194644p:plain
入れ替えの途中経過

抜き出して並べるアルゴリズムと比較する

実はこのアルゴリズムは、配列から一個ずつ要素をランダムに選んで空の配列に移していくのと本質的に変わりません。これを1つの配列内で行っているだけです。i より前部分が与えられた配列で、iから後ろが新しい配列と考えると分かると思います。

ちなみに一つずつ抽出して別の新しい配列に入れていくコードはこのようになります。見るとわかりますが、shuffle2()はほとんどshuffle()と同じです。

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

さて、ここまでの解説で理解していただけたかと思いますが、Fisher-Yatesは 計算量が配列の長さ分 しかありません。ランダウ記法を用いると、配列の長さをnとしてO(n)です。O(n)を超えるにはO(log n)O(1) にしなければなりませんが、少なくともn回の入れ替えを実施しなければならないので、不可能です。これが最速と呼ばれる所以です。

終わりに

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