« 2006年07月 | メイン | 2006年09月 »
2006年08月31日
Schwartzian Transform でランダムシャッフル
Schwartzian Transform を使って配列をシャッフルする話をみて、なるほどな～と思いつつも、よくよく考えてみるとこれは2つの意味で駄目です。1. 計算量が O(n * log(n)) であること。
2. ランダムにシャッフルできない。
1. は説明するまでもないので、2の理由を考えてみます。
まず、rand() が 0..k-1 までの k種類の整数から 1 つ数値を返すものとします。配列のサイズが n の場合、 weightの並びの場合の数は k^n 通り存在します。ところが、配列の順列の場合の数は n! です。 ここで何か矛盾点があるように思えてきます。
実際に k = 2, n = 2 の場合を考えて見ましょう。この場合、サイズ2の配列をシャッフルするんですから、 要素を入れ替える場合と入れ替えない場合が 1/2 の確率で出現するのが正しいシャッフルです。
k = 2 の場合、各配列のweightは[0 0] [0 1] [1 0] [1 1] の 4通りあります。 これらをソートして降順に並べるわけですから、ソートが安定だと仮定すれば、入れ替わるのは [1 0] の時のみになってしまいます。つまり、確率 1/4 で要素が入れ替わって 3/4 で入れ替わらない ということになります。クイックソートのように不安定の場合でも、[0 0][1 1] の動作は確定的なので、結局 偏ってしまいます。
k をいくら大きくしても問題は解決されません。 うまくいくのであれば、最低 (k^n) は n! で割り切れなければなりません。なぜならば、n! の場合の数を、k^n に均等に分配してあげる必要があるからです。割り切れないと、いずれかの配列の並び方を重複して数えてしまいます。これはランダムではありません。一般に (k^n) % n! != 0 ですから、ランダムなシャッフルは実現できません。
確かにlibcのrand()は、0からRAND_MAX(たいていMAX_INT = 0x7fffffff)までの整数を返しますが、JavaScriptのMath.random()も含め、たいていのLL言語ではrand()やrandom()に相当する組み込み関数は0から1までの浮動小数点の値を返すようになっています。
浮動小数点だったら問題ないという指摘がありましたが，それは誤認です．たいていの乱数生成器(線形合同法やMT19937)は整数値を返すようになっています．浮動小数点を返すものは整数から適当に [0-1] にノーマライズしているだけです．つまり，たとえ浮動小数点であろうと，整数値と全射の関係にあります．
Ruby の rand は，MT19937 を2回つかって整数値から浮動小数点に変換しています．
/* generates a random number on [0,1) with 53-bit resolution*/
static double
genrand_real(void)
{
unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6;
return(a*67108864.0+b)*(1.0/9007199254740992.0);
}
かりに浮動小数点を返す乱数生成器があったとしても，浮動小数点の精度は有限なので，整数値に完全にマッピングできます．ソートベースの方法が完全性を持つには，浮動小数点の乱数で，その精度が無限にある状況のみです．
もっとも，RAND_MAX は十分大きいので，実用上はほとんど問題にならないと思います．大規模なシミュレーションをしても誤差は出ないと思います．