人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

JavaScript の質問です。
http://qiita.com/minodisk@github/items/94b6287468d0e165f6d9
↑この sort を使ったシャッフル法はなぜ偏るんでしょうか?
よろしくお願い致します。

●質問者: Lhankor_Mhy
●カテゴリ:コンピュータ ウェブ制作
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● snow0214
●5ポイント

いずれもsortのユーザー関数の戻り値に正負の偏りがあるためです。

badShuffle1

roundで四捨五入しているため
負になるのはMath.randomが0.0以上0.75未満の場合
正になるのはMath.randomが0.75以上1.0未満の場合
→負側に偏っている。

badShuffle2

roundしているだけなので
→負にならない。

badShuffle3

正になる確率は0.5
負になる確率は0.5未満
それ以外はゼロになる(シャフルが起きない)
→正側に偏っている。

badShuffle4

負になるのはMath.randomが0.0以上0.33...以下の場合
正になるのはMath.randomが0.66...以上1.0未満の場合
それ以外はゼロになる(シャフルが起きない)
→シャフルが起きないケースが3分の1ある。

badShuffle5

負になるのはMath.randomが0.0以上0.5以下の場合
正になるのはMath.randomが0.5を超えて1.0未満の場合
→負側に偏っている。


Lhankor_Mhyさんのコメント
ありがとうございます。 ご指摘の部分、比較関数を修正してみました。 >|javascript| var badShuffle = function (arr) { return arr.slice().sort(function () { if (Math.random() > 0.5) { return 1; } else if (Math.random() < 0.5) { return -1; } else { return 0; } }); }; ||< これですと正負に偏りがないはずですが、リンク先の分布集計コードを使ってみたところ結果は以下の通りでした。 >> A:2.739 B:2.647 C:3.221 D:4.41 E:4.502 F:5.039 G:5.152 H:5.193 I:5.844 J:6.253 << たしかに少しマシな結果になっているようですが、それでも偏りがあるようです。他にも原因があるのではないでしょうか?

snow0214さんのコメント
Math.random自体に偏りがあるためです。 下のスクリプトを実行してもらうと、乱数の分布が一様でないことが分かります。 >|JavaScript| var array = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; var times = 1000; for (i = 0; i < times; i++) { t = Math.floor(Math.random() * 10); array[t]++; } console.log(array); ||<

Lhankor_Mhyさんのコメント
当方の環境で1千万回試行しましたが、3桁程度の一様性は見られるようでした。ソート結果に影響を与えてしまう程の誤差であるのか、いささか疑問です。 FireFoxではJavaScriptの乱数はメルセンヌツイスタを使用していると聞いたことがあります。あれは一様乱数だと思っていましたが、違うのでしょうか?

2 ● ghost
●150ポイント ベストアンサー

「先に乱数決定した仮順位の大小比較に従ってソートする」のと、
「大小比較の結果を乱数決定してソート(のフリ)をする」のは、全く違います。

根本的に、sort()の大小比較関数にどのような乱数を詰め込んでも、一般的には均一なシャッフルにはなりません。実際にそれがどういうシャッフルになるかはsort()の内部実装に依存します。

AとBを大小比較した結果が、sort()の進行途中でコロコロ変わってしまう(正確には複数回の大小比較の間で結果に一貫性が無い)点が問題です。たとえ個々の大小比較の結果が均一であっても、それによって行われる並べ替えの方向にはsort()自体のアルゴリズムによる偏りがあるので、得られる結果は均一なシャッフルにはなりません。

若干追記しました


Lhankor_Mhyさんのコメント
ありがとうございます。 >> AとBを大小比較した結果が、sort()の進行途中でコロコロ変わってしまう点が問題です << なるほど、納得です。 たとえ比較関数の結果がコロコロ変わらなくても、矛盾する大小関係が発生してしまえばどのようにソートされるか分からない、ということですね。 試しに比較関数のクロージャで要素ごとの評価値を保持するようにしてみたら、偏りなくシャッフルできました(それでも、例に上がってるシャッフルアルゴリズムの方が速いですよね)

ghostさんのコメント
あるいは hash(A+c)-hash(B+c) のような疑似乱数でも大丈夫ですな (cはシャッフル実行毎に乱数決定する定数)。いずれにせよsort()を経由しても確実に丸損するだけで意味は無いです、はい。

ghostさんのコメント
あダメだ、上記のhash方式だと同値の要素が複数あった場合に確実に固まって配置されますね。アハハ。

Lhankor_Mhyさんのコメント
hashが十分に散らしてくれるなら、定数の代わりにタイムスタンプを使えばなんとかいけるはず……!
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ