2010年2月25日木曜日

JavaScript のランダムソート

昨日の TechCrunch 日本語版に出てた「ヨーロッパ人のためのランダムなブラウザ選択画面‐その‘ランダム性’を検証してみた」が気になったのでソースを覗いてみた。

肝心な部分は次のスクリプト。

var aBrowserOrderTop5 = new Array(0,1,2,3,4);
aBrowserOrderTop5.sort(RandomSort);
function RandomSort (a,b){return (0.5 - Math.random());}

ランダムソートをsortの比較関数でやっつけているw。この発想、思いつかんわwww。

噂によれば IE の擬似乱数がダメダメだからだとか言われているけど、ランダムソートはちゃんと関数書いたほうがよろしいようで、という教訓として語られるべき話のようです。

以下参考までに、1万回ループさせて調べた結果。


Safari


Google Chrome


Mozilla Firefox


Opera


Internet Explorer

ランダムなら 10000 / 5 = 2000 が期待値となるので、単純にカイ2乗検定してみると、手許のブラウザはすべて1%有意水準で有意差あり(ランダムでない)。一番まともに見えた Safari でさえ P = 10-211。というかそれ以外は32bitマシンで普通に計算すると確率は0という結果…。

比較関数が呼び出される平均回数は、IE で9.77回、Firefox で6.18回、Safari で6.74回、Chrome で6.76回、Opera で6.12回。

ちなみにブラウザのバージョンはすべて最新。

※ 図中の記号は、SA:Safari、GC:Google Chrome、OP:Opera、MF:Mozilla Firefox、IE:Internet Explorer。A~E は配置。

0 件のコメント:

コメントを投稿