実践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

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


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


WriteBacks

javascript - シャッフルシャッフル

なるほど。Schwartzian Transform"の意外な利用法だなあ。
snippets from shinichitomita’s journal - JavaScriptの配列をsort関数でシャッフルする
Array.prototype.shuffle = function() {
return this.map(function(a){ return { weight: Math.random(), value: a ...

Posted by 404 Blog Not Found at 2006/08/30 (Wed) 18:31:07

Arry#splice の戻り値は常にArrayですね(除NN4)。

Posted by 通りすがり at 2006/08/30 (Wed) 19:58:07

Good site

anime carte m竪re TUOI DI RADO CANADA NO TUBO solvente quimico et trop tard dict達 e vocale negra gijon ANIME UM BURRO ANIME REDATTA

Posted by petushokbkw at 2006/10/26 (Thu) 13:49:34

Good site

agv per auto Www dpfanatics com ALLENAMENTI NUOTO CAMPIONI SYSRTMVS BENJAMIKN MOOR free pantyhosewifes Naked gymnast DISK DEFRAGMENTER FREE DOWNLOAD Gemellidiversithebest motyw taa�a w literaturze

Posted by flatmog at 2006/11/01 (Wed) 00:07:21

Good site

GIANMARCO GOTA DE anime a situa estado fisico de La marinera en ANIME NORMAS DE AUDITOR鱈A GENERALMENTE ACEPTADAS ANIME EL ATENEO ARGENTINA Di duplicazione SINO HOTEL Nvidia quadro fx 4000 loro parque tenerife

Posted by dewdewduov at 2006/11/22 (Wed) 01:34:14

Posted by at 2006/12/03 (Sun) 01:32:58

Good site

anime pier vittorio tondelli Limitato verona Anime e marcia gallbladder fossa DVR STUDIO z pornografico ANIME STIPENDI GIOCATORI lobo solitario y su anime paya konjac tuber GRAFICI WEB

Posted by romtravelgpf at 2006/12/16 (Sat) 18:31:35

Good site

innova 2005 [url=http://fettl旦sliche-vitamine.italytoursite.info/innova-2005.html]innova 2005[/url] Lagrima de amor mi [url=http://anime-pompa-wodna.italytoursite.info/lagrima-de-amor-mi.html]Lagrima de amor mi[/url] Naturali 2005 [url=http://anime-en-california.italytoursite.info/naturali-2005.html]Naturali 2005[/url] TRANSITO DEL ESTADO DE [url=http://transito-del-estado-de.italytoursite.info/]TRANSITO DEL ESTADO DE[/url] Protese odontologica [url=http://protese-odontologica.italytoursite.info/]Protese odontologica[/url] Luglio 1980 n [url=http://eucalipto-baby-blue.italytoursite.info/luglio-1980-n.html]Luglio 1980 n[/url]

Posted by toursiteeng at 2007/01/15 (Mon) 04:09:33

Posted by at 2007/04/17 (Tue) 17:09:12

clonedvd

Here’ s something I discovered a couple weeks ago that some people may find useful. It’ s not rocket science or anything and a lot of people probably already knew about it. But I’ m posting it here partially so I remember about it. Anyway, I found you can lock your computer using a shortcut pointed to“% windir%\\ system32\\ rundll32. exe user32. dll, LockWorkStation”. This is very useful for when you have to work on keyboard that is lacking the windows key (like IBM Thinkpads). Once you have the shortcut you...

Posted by clonedvd at 2008/05/01 (Thu) 10:29:39

BogosortをJavaScriptで実装してみた

暇でWikipedia見てたらボゴソートとかいうのを見つけた。JavaScriptでの実装例があまりないようだったので、どうせだからと実装してみることにした。ちなみに、ボゴソートとは「要素をシャッフル→ソートされてたら処理終了、されてなければまたシャッフル」を繰り返す、非常に効率の悪いアルゴリズムである。function isSorted(aArray){ for(var i=0,l=aArray.length-1;i<l;i++){ if(! (aArray[i] <= aArray[i+1])) return false; } return true;}function shuffle(aArray){ return aArray.sort(function(){ return Math.random()*100 <= 50; });}function bogoSort(aArray){ while(!isSorted(aArray)){ shuffle(aArray); }}

Posted by Studencheskie Programmisty at 2011/02/01 (Tue) 12:03:16

while(i)について

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;
}
上のwhile(i)は、while(i-1)の方が良いと思います。
while(i)ですと、i=1の時、j=0, t=this[0], this[0]=this[0], this[0]=t(=this[0])となり、this[0]とthis[0]を交換します。これはやらない方が良いと思います。

Posted by 林 at 2013/02/12 (Tue) 08:39:59
TrackBack ping me at
http://la.ma.la/blog/diary_200608300350.trackback
Post a comment

writeback message: Ready to post a comment.







spam yoke. nanimo ireruna.