hinekure.net が http://hspdev-wiki.net/ から自動クローリングした結果を表示しています。画像やリソースなどのリンクが切れています。予めご了承ください。
巡回乱数 - HSP開発wiki
トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS

巡回乱数

巡回乱数の生成方法を考え方(アルゴリズム)を交えて説明しますが乱数発生自体はシステムが提供しているものを使います。(HSPではrndに相当。)

巡回乱数って?

「巡回乱数」という言葉は聞き慣れないかも知れませんが、それもそのはずkz3が先ほど勝手に命名しました。
俗にいう「重複のない乱数」です。

rndで得られる乱数値は「一様乱数」と呼ばれる乱数ですが直前に得られた乱数値が続けて得られることもあります。
巡回乱数の"巡回"とは、rndで得られるある範囲内の一様乱数を(順不同で)巡回して得るということから来ています。


  • rndで得られる一様乱数が0〜9の時、1回目に0を得ると次回からは1〜9が得られます。
    2回目で9を得ると次回からは1〜8が得られます。
    そうやって全ての一様乱数を得る(巡回する)と次回は再び0〜9が得られます。

力ずく法

まず簡単な方法としては、得た乱数を記録しておき乱数を得るたびに過去にその乱数を得たかどうかを調べる方法が挙げられます。

A l g o r i t h m :

はじめに・・・
        rndで得られるこれまでに得た乱数の数を記録する変数を用意する。
        rndで得られる乱数の範囲に相当する記録用の配列を初期状態を未出(false)として用意する。

  1. rndで乱数を得る。
  2. 1で得られた値を配列のインデックスとして記録用配列の要素を調べる。
    1. 2で調べた結果がfalseの場合は未出であるから1で得られた値を巡回乱数の値とする。
      1. 1で得られた値をインデックスとして記録用配列の要素を既出(true)にする。
      2. これまでに得た乱数の数を1増やす。
    2. 2で調べた結果がtrueの場合は既出であるから1に戻ってやり直す
  3. これまでに得た乱数の数がrndで得られる乱数の最大個数に達したら一巡したので記録用配列の全要素を初期状態に戻す

この場合何度も既出の値を選んでしまい、特に最後の巡回乱数を得る時などは頻繁にやり直しが発生します。

追い出し法

はい、これがkz3が自力で閃いたアルゴリズムですが、実際には多くの方が同じような方法を思いついてるみたいです。
でも自分で閃いたので胸張って書きます。p(゚ー゚q

A l g o r i t h m :

はじめに・・・
         rndで得られる乱数の範囲に相当する配列(以下、テーブルと称す)を初期状態を「インデックス = 要素」として用意する。
         現在rndで得られる乱数の個数を記録する変数(以下、ランダムポイントと称す)を初期状態を最大個数として用意する。

  1. rndにランダムポイントを与えて乱数を得る。
  2. 1で得られた値をインデックスとするテーブルの要素を巡回乱数の値とする。
  3. ランダムポイントを1減らして生成される乱数範囲を狭める。
  4. 3でランダムポイントが0になった
    1. ランダムポイントをrndで得られる最大個数に再び初期化する。(この時、テーブルは初期化しなくても良い。)
  5. 3でランダムポイントが0でない
    1. 1で得られた値をインデックスとするテーブルの要素と、ランダムポイントをインデックスとするテーブルの要素を交換する。(乱数範囲外に追い出す。)

要素を交換するとき、乱数で得た要素とランダムポイントの要素と重なる場合がありますがアルゴリズムを単純にするために処理を省いています。 このアルゴリズムの巡回乱数を得る時間計算量はO(1)ですが、具体的にはシステム定義の乱数発生機の計算量に依存するということです。

シャッフル法

発生させる全ての乱数値を配列の要素に設定し、配列要素をシャッフルさせ、順番に配列の要素を取り出す方法。

力ずく法・追い出し法が乱数発生時に発生させるべき数値を決めているのに対し、この方法はシャッフルした時点で将来発生させる数値が決まっています。

この方法をここでは便宜的にシャッフル法と呼ぶことにします。

A l g o r i t h m :

はじめに・・・
         rndで得られる乱数の範囲に相当する配列(以下、テーブルと称す)を初期状態を「インデックス = 要素」として用意する

  1. テーブルをシャッフルする。カウンタを0にセットする。
  2. 乱数を発生させる。
    1. テーブルのカウンタ番目の要素を発生させる乱数とする。
    2. カウンタをインクリメントする。
    3. もしカウンタがテーブルの要素数と同じになったら、テーブルをシャッフルしてカウンタを0にセットする。

著者(eller)が独自に考えたアルゴリズムですが、簡単なため他の方のアイデアと重複しているかも知れません。

コメント

  • 乱数の性能は検定してみないとわからないと思いますが、、検定はしないの?
  • 旧「配列要素のシャッフル」を文書化中です。 -- kz3 2005-11-10 (木) 13:25:00
  • 追い出し法を考えていたときの様子は脱力さんが覚えているかもです。 -- kz3 2005-11-10 (木) 15:27:14
  • HSPの書籍に載ってる「スワップ法」はシャッフルであって巡回乱数とは関係ありませんでした。 -- kz3 2005-11-10 (木) 15:32:00
  • 文章のおかしいところがないかチェック。 -- kz3 2005-11-10 (木) 17:44:05
  • やっぱり実装例もないとアカンですよね?´ロ` -- kz3 2005-11-10 (木) 17:47:18
  • まぁ上の箇条書きをソースにするだけなんですが・・・ -- kz3 2005-11-10 (木) 17:50:31
  • ソースは小ワザとかModuleとかに書けばいいのでは?? -- Charlotte 2005-11-10 (木) 17:56:25
  • なるほど、小ワザでソース、アルゴリズムの解説はこっちでっと・・・。 -- kz3 2005-11-10 (木) 18:07:29
  • 実に1年以上ぶりの更新。実装例は後日追記いたします。 -- eller 2007-05-29 (火) 22:10:00
トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS
Last-modified: 2009-02-25 (水) 13:40:16 (1747d)