JavaScript の質問です。

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

回答の条件
  • 1人5回まで
  • 登録:2014/03/07 16:01:10
  • 終了:2014/03/08 15:06:24

ベストアンサー

id:vow No.2

ghost回答回数21ベストアンサー獲得回数92014/03/08 14:03:33

ポイント150pt

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

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

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

若干追記しました

他2件のコメントを見る
id:vow

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

2014/03/08 15:31:28
id:Lhankor_Mhy

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

2014/03/08 16:15:17

その他の回答(1件)

id:snow0214 No.1

snow0214回答回数470ベストアンサー獲得回数1162014/03/08 00:05:04

ポイント5pt

いずれも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未満の場合
→負側に偏っている。

他1件のコメントを見る
id:snow0214

Math.random自体に偏りがあるためです。
下のスクリプトを実行してもらうと、乱数の分布が一様でないことが分かります。

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);
2014/03/08 12:22:33
id:Lhankor_Mhy

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

2014/03/08 12:55:26
id:vow No.2

ghost回答回数21ベストアンサー獲得回数92014/03/08 14:03:33ここでベストアンサー

ポイント150pt

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

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

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

若干追記しました

他2件のコメントを見る
id:vow

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

2014/03/08 15:31:28
id:Lhankor_Mhy

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

2014/03/08 16:15:17

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません