西尾泰和のはてなダイアリー

■ランダムソート(笑)とは

誰が「ソートするときに比較関数に『ランダムに1か-1を返す関数』を与えたらシャッフルできる」って言い出したのかしらないけど、真に受ける方も真に受ける方だと思う。

たとえばソート関数が下のような「リストの先頭の値をピボットにしてそれより大きいものと小さいものに振り分けるクイックソート」だったとする。比較関数の所はランダムにしてある。

>>> def quicksort(xs):
	from random import random
	if len(xs) < 2:
		return xs
	pivot = xs[0]
	left = []
	right = []
	for x in xs[1:]:
		if random() < 0.5:
			left.append(x)
		else:
			right.append(x)
	return quicksort(left) + [pivot] + quicksort(right)

で、その「ランダムソート」で[0, 1, 2, 3, 4, 5, 6]をシャッフルしてみる。

>>> range(7)
[0, 1, 2, 3, 4, 5, 6]
>>> quicksort(range(7))
[4, 1, 3, 6, 0, 2, 5]

一見混ざっているように見える。

でそれを7000回やってシャッフルした結果の0番目に来る数を集めたリストを作ってみる。きちんとシャッフルされているなら当然「どの数字もだいたい1000回出現する」という結果になるはずだよね。

>>> sample = [quicksort(range(7))[0] for _ in range(7000)]

じゃぁ表示してみよう。

>>> for i in range(7):
	print i, sample.count(i)

	
0 108
1 848
2 1102
3 1180
4 1227
5 1233
6 1302

見ての通り、0が出る確率がものすごく少ない。最初にピボットに選ばれる数は「残りの6個がすべてそのピボットよりも大きい」という場合しか先頭に来ないので、0.5を6回掛け合わせた確率でしか先頭に現れない。最初に選ぶピボットをどこに決めようがその数が先頭に来る確率はとても少なくなる。クイックソートが使われている限り、この方法で均等なシャッフルはできない。

プログラミングの勉強ってのはどこかの誰かが「こうすればできる」って言ったことをたくさん鵜呑みにして蓄えることじゃない。自分で納得するまでかみ砕かなくては、いくらたくさん飲み込んでも栄養にはならない。本当を言えば「嘘を嘘と見抜く能力」をつけて欲しいところだけども、まだその力がないのならせめて鵜呑みにする前にきちんと試してみたほうがいいのではないだろうか。

---

追記：Pythonの組み込みのsortedを使った場合を試してみたらやっぱり数字によって出現確率に差が出た。

>>> sample = [sorted(range(7), cmp=lambda x,y:choice([-1,1]))[0] for _ in range(70000)]
>>> for i in range(7):
	print i, sample.count(i)

	
0 17581
1 6827
2 8807
3 11613
4 7611
5 8089
6 9472

Permalink | コメント(0) | トラックバック(4) | 19:31