ランダムの偏り
こんばんは。
なんかふと思ったので、久しぶりにプログラミングの記事でも書こうかと思います。
といっても非常に初歩的で当たり前な話です。
ただ、初心者向けの書籍やネット資料などでよく見がちなので
初心者が陥りやすいランダムの罠だとは思います。
やりがちなランダムがこれ。
0〜n-1までの整数値のランダムを取得する関数です。
unsigned int RandA(unsigned int n) { return static_cast<unsigned int>(rand()) % n; }
randの結果の余りを計算する方法です。
よく見がちなコードですが、これは偏ります。
ランダム性を高めたコードはこれ。
※修正しました:2013/4/24
とおりすがりさん、ご指摘ありがとうございました!
unsigned int RandB(unsigned int n) { return static_cast<unsigned int>(rand() * n / (1.0f + RAND_MAX)); }
rand関数は[0〜RAND_MAX]までの値を返します。
その0〜RAND_MAXまでの値を[0〜n-1]までに一様に割り当てています。
(1.0f + RAND_MAX)で割っているのは割合を一様にするためです。
(1を加算せずに割るとn-1が出る確率が極端に低くなります)
結果ですが、例えばrand関数が以下のような値を返してきてくれたとき、
randが2987657600のとき
RandA(100) -> 0
RandB(100) -> 69randが1324759300のとき
RandA(100) -> 0
RandB(100) -> 30randが978436100のとき
RandA(100) -> 0
RandB(100) -> 22
すごく意地悪な結果を載せてみましたが、ようするに言いたいことはこういうことです。
rand関数などのランダム生成関数がせっかく生成してくれたランダムの数値ですが、
それをそのまま割合にせず余りを求める計算をすると、
どんなにrandで返された数値が遠いものだったとしても同じ値になってしまうことがあります。
できる限り、ランダム生成関数が生成したランダム性を殺さずに
ランダム関数を作るのが肝です。
P。S。
最後に、
色々コードを書きましたけど、このコードは一切実行してません!!(どどん!);;;
ランダム結果の計算も電卓でやりました。ごめんなさい。
なのでコピペして問題が出た!とかあっても動作保証はありませんので、あらかじめご了承ください。
修正コードがありましたらご連絡ください。
記事を修正します。
ちなみにランダムは「rand関数自体を変えてみる」など
他にもランダムの生成方法はあるので興味が沸いたら勉強してみるのも楽しいと思います。
逆にあえて偏りを作ってみたり、あえて予測できるランダムを作ってみたりすることもあるので、
必ずしも完全ランダムが正義というわけでもないと思います。
使う場面に合わせて使い分けるようにするとよいかと思います。