RSS

 

RSS


プ:乱数の使い方がダメ

  • いわいまさか
  • at 2008/7/11 19:03:54

 乱数の使い方がダメなプログラムを紹介。つまり、次の1も2も×。やりたいのは配列boxに0~99の数字をランダムにつめること。

1.箱が空いてなかったら抽選しなおすと・・・。

 Int32 box[100];

   // 最初に全部空(-1)にセット
   for(Int32 i=0;i<100;i++){
     box[i]= -1;
   }

   for(Int32 n=0;n<100;n++){
       // 数字n はどこに置こうか
   Retry: 
      Int32 pos =rand()%100;
       if(box[pos] == -1){
           box[pos]= n;
       }else{
           goto Retry;
       }
   }              

・箱に数字が埋まってきて後半になるとRetryばっかり多くなり効率悪し。
・rand()の出来が悪いと最後まで箱が埋まらずに無限に回り続けることになる、なんてことも。BAD!
・純粋な論理的な意味では次の2.よりもいいのだが。

2.調子いいけど、なんか粘り気が・・・

   for(Int32 n=0;n<100;n++){
       // 数字n はどこに置こうか
      Int32 pos =rand()%100;

      // 箱が空いてなかったら次の箱へ次の箱へと見ていって埋める
      for(;;){
         if(box[pos] == -1){
             box[pos]=n;
             break;
          }
          pos = (pos+1)%100;
     }
   }              

・この方法だとrand()をcallする回数は100回きっかりで終了。
・rand()の出来が悪くても最後までしっかり埋まる。

と一瞬良さげだが

・実は、並びに癖があって正しくない!!!!!

まず最初に0の位置が決まる。

***0***************

次の1の位置を決める場合。
上記のところだけ確率 2/100で他の場所*は1/100と差がある!!! 2以降決定の際にも同様な偏りが入る。

「0の次に1が来る場合がなんとなく多くない?」(平坦な口調で)、「並びかたに偏りがありますよ~~~」ということになる。

・わかりにくいけど、確実に悪い。

以上

 


  • コメント (9)
  • トラックバック (1)
トラックバックURL :
http://www.iwai-masaka.jp/tb.cgi/52288

コメント

こんなのは?

std::map<int, int> r;
for (int i = 0; i < 100; ) {
  if (r.insert(std::make_pair(rand(), i)).second) i++;
}
for (std::map<int, int>::const_iterator it = r.begin(); it != r.end(); it++) {
  printf("%d\n", it->second);
}

  • Posted by k16
  • at 2009/06/01 19:25:43

つっこめたらOK、そうでなかったら、やり直し。記事の1の場合の「後半になると効率悪し」「無限に回るかも」を改善したカタチ。事実上OKだとは思うが、箱の数がrand()の取りえる種類の範囲に比較できるくらい大きくなるとNG。rand()装置が壊れて同じ数字しか返さなくなったりすると無限ループ。

であってますでしょうか?

  • Posted by いわいまさか
  • at 2009/06/01 20:51:38

はい
rand()が優秀な 0以上1未満のdoubleを返すようなものだとGOODなんだけど、C標準のrand()はほぼ実用的でない
GUIDとか使う手もある

  • Posted by k16
  • at 2009/06/01 20:55:56

えーと、map使った手前ダブリチェックしてるだけなので、multimapとかにすれば問題なし
そもそも、そんな構造使わずに、100の配列に乱数詰めてsortすれば同じです
要は、シャフルするんじゃなくて、たった100の乱数だけで実現できるということです

  • Posted by k16
  • at 2009/06/01 23:01:46

乱数が同じ値を引いたときのsortでの扱いが、若い番号、優先だったりすると、99番がとる順位の期待値が悪くなると思います。
http://www.iwai-masaka.jp/52290.html?1215891648 の方法3はいかがでしょうか。

  • Posted by いわいまさか
  • at 2009/06/02 01:41:30

そんな腐った乱数生成器は捨てる

  • Posted by k16
  • at 2009/06/02 11:21:49

訂正
腐った乱数生成器でも、よい結果を得る手法は? というテーマなら、それはそれで面白いかも知れない
でも、乱数生成器は、物事の根源的なものなので、それの不完全性を仮定するプログラムには未来がない気がする

  • Posted by k16
  • at 2009/06/02 11:32:38

乱数器がまともでも、まわりを作りまちがえると「99番が不利」といった系になることがある。

「100個から1個選らんで
残りの99個から1個選んで
残りの98個から1個選んで・・・という"普通"のプロセスを踏めばいいんじゃないの?」ということです。

  • Posted by いわいまさか
  • at 2009/06/02 13:20:46

御意
# 何が普通かは置いといて

  • Posted by k16
  • at 2009/06/02 14:50:54

トラックバック

いわいまさかチャンネル - プ:乱数の使い方がダメ 乱数の使い方が駄目な例が紹介されている。 じゃあ、どうコードを書くのが正しいのかといわれると、なかなか良い方法を思いつかない。 思いついたのは、配…