最速インターフェース研究会

実践JavaScriptで配列をシャッフルする方法リファクタリング

JavaScriptで配列をシャッフルする話を見て、そういえばArray#shuffleは以前書いた記憶があるなーと思って調べてみたらコピペだった。
http://www.fumiononaka.com/TechNotes/Flash/FN0212002.html

Fisher-Yatesというアルゴリズムだそうです。

Array.prototype.shuffle = function() {
    var i = this.length;
    while(i){
        var j = Math.floor(Math.random()*i);
        var t = this[--i];
        this[i] = this[j];
        this[j] = t;
    }
    return this;
}
a = [1,2,3,4,5];
a.shuffle() // 3,1,5,2,4
a // 3,1,5,2,4

ごく普通に実装するとランダムに一件ずつ取り出すのがわかりやすいんじゃないかと思う。Rubyの本とか見ると大体そんな感じで書いてある気がする。JavaScriptには破壊的sliceがないので代わりにspliceを使えば良い。

Array.prototype.shuffle = function(){
    var len = this.length;
    var ary = this.concat();
    var res = [];
    while(len) res.push(ary.splice(Math.floor(Math.random()*len--),1));
    return res
}
a = [1,2,3,4,5];
a.shuffle() // 3,1,5,2,4
a // 1,2,3,4,5

元の配列には変更を加えず、ランダムに並べ替えられた新しい配列を返す。要素数の増減があるから遅くなるかも。ベンチ取ってないけど。

配列に独自のプロパティを持たせてあったり、toStringをインスタンス固有の関数に置き換えてある配列オブジェクトがあったとして、元のオブジェクトのまま中身をシャッフルしたい、という場合には、中身を直接入れ替えるのが良いでしょう。(最初に書いたやり方のように)

lazyな処理をしたい場合はランダムピック方式の方がやりやすい。巨大な配列をシャッフルしたい場合は、ランダムな順番で要素を返すイテレータを作るのがよいだろう。

Array.prototype.random_iter = function(){
    var len = this.length;
    var ary = this.concat();
    return {
        has_next: function(){
            return len ? true : false
        },
        next: function(){
            if(!len) return null;
            var i = Math.floor(Math.random() * len--);
            return ary.splice(i,1)
        }
    }
}

これなら一万件ぐらいの配列からでも高速に一件ずつ取り出すことができる。

あと配列をランダムに並べ替えるのにsortメソッドを使ってコンペア関数にランダムな値を返すようにする、という方式は片寄る、って話をしてて、なんで片寄るのかを少しわかりやすくしてみた。
http://la.ma.la/misc/js/randomize.html

端っこの要素があまり比較されないで片寄る様子がわかると思います。


なんか大した話でもないのに無理矢理発展させた感が否めない。

A quick preview will be rendered here when you click "Preview" button.