ちょっと引っ張り過ぎなんですが。
comma separationのテスト結果をGoogle Char APIをつかってグラフ表示してみた - さらさら宇宙忍法帖
↑このグラフを書くとき、ボタンを押すたびに評価の順番をランダムに変えて、
順番による影響がなるべくでないようにしようとしています。
で、ランダムに順番をかえるのに、
// funcsは評価対象の関数の情報を並べた配列 funcs.sort(function(a,b){return Math.random() - 0.5;});
としていたのですが、これだと配列の端の方があまり並び替えられないということが分かりました。
ランダム並び替えはFisher-Yates shuffleと呼ばれる方法がよく知られているようで、
↓このように修正しました。
（wikipediaに載っているコードをjavascriptで書き直したもの）
function shuffle_fy(array){ var n = array.length; while (--n) { var k = Math.floor(Math.random() * n); // 0 <= k <= n (!) var temp = array[n]; array[n] = array[k]; array[k] = temp; } return array; }
で、最初の方法だとどれほどまずいのか、
Fisher-Yatesだとどれほどよいのか、
あんまり実感できなかったので、見て分かるようにしてみました。
こちらです。
（↑例によって試したのはFirefoxだけで、多分他のブラウザだとまともに動きません。。）
結果の絵もはっておきます。
最初のグラデーションな帯が初期配列で、色が配列の値を表しています。
これに対してシャッフル処理したものが下にあるまだら模様なのですが、
一つ目のまだら模様は安直シャッフルによるもので、左端は黒く、右端は明るくなってます。
つまり端の方はあまり並び替えられていません。だめですね。
二つ目のまだら模様はFisher-Yates shuffleによるもので、
均等にまだらになっていて、場所によって偏りがありません。ナイスですね。
重み付きシャッフルについても同じような可視化を試みていたんですが、
ちょっと問題の意味をはき違えてしまっていました。
ですがそれっぽい結果に見えるので一応こちらもひっそりとリンクだけはっておきます。
あ、こういうのGoogle Gearsのworker pool使うとサクサク結果表示できるかな。。
