10

100 個までの数値のセットがあります。このセットで MC シミュレーションを実行したいのですが、基本的な考え方は、セットを完全にランダム化し、最初の 20 個までの値で比較/チェックを行い、結果を保存して繰り返すことです。

現在、実際の比較/チェック アルゴリズムは非常に高速で、実際には約 50 CPU サイクルで完了します。これを念頭に置いて、これらのシミュレーションを最適化するために、ランダム セットをできるだけ速く生成する必要があります。

現在、George Marsaglia による Multiply With Carry アルゴリズムを使用しています。これは、非常に高速な 17 CPU サイクルでランダムな整数を提供します。ただし、Fisher-Yates のシャッフル アルゴリズムを使用すると、100 個のランダムな整数、約 1700 の CPU サイクルを生成する必要があります。これは、私の比較時間をはるかに覆い隠しています。

私の質問は、このタイプの MC シミュレーションを実行するための他のよく知られている/堅牢な手法はありますか?

セットから 20 個の値をランダムに選択することも考えましたが、20 個の一意のエントリが選択されるように衝突チェックを行う必要があります。

アップデート：

回答ありがとうございます。投稿後に思いついた方法について、別の質問があります。問題は、これが真に堅牢な (RNG が良好であると仮定して) ランダムな出力を提供するかどうかです。基本的に私の方法は、入力配列と同じ長さの整数値の配列を設定し、すべての値をゼロに設定することです。次に、次のように、入力セットから 20 個の値をランダムに選択し始めます。

int pcfast[100];
memset(pcfast,0,sizeof(int)*100);
int nchosen = 0;
while (nchosen<20)
{
    int k = rand(100); //[0,100]
    if ( pcfast[k] == 0 )
    {
        pcfast[k] = 1;
        r[nchosen++] = s[k]; // r is the length 20 output, s the input set.
    }
}

基本的には上で述べたように、20 個の値をランダムに選択しますが、衝突を回避するための多少最適化された方法のように思えます。これは良いランダム出力を提供しますか? その非常に高速です。

4

2 に答える 2

5

ランダム化された配列の最初の 20 個の値のみを使用する場合、Fisher-Yates アルゴリズム (Knuth のバージョン) の 20 ステップを実行するだけで済みます。次に、アルゴリズムの残りの 80 ステップがそれらを移動しないことが保証されているという意味で、20 個の値がランダム化されています (実際には、通常の定式化では配列の先頭ではなく末尾にあります)。他の 80 のポジションは完全にシャッフルされていませんが、誰が気にしますか?

C++ コード (イテレータはランダム アクセスである必要があります):

using std::swap;

template <typename Iterator, typename Rand> // you didn't specify the type
void partial_shuffle(Iterator first, Iterator middle, Iterator last, Rand rnd) {
    size_t n = last - first;
    while (first != middle) {
        size_t k = rnd(n);   // random integer from 0 to n-1
        swap(*(first+k),*first);
        --n;
        ++first;
    }
}

戻ると、 から までの値firstがmiddle-1シャッフルされます。次のように使用します。

int arr[100];
for (int i = 0; i < 100; ++i) arr[i] = i;
while (need_more_samples()) {
    partial_shuffle(arr, arr+20, arr+100, my_prng);
    process_sample(arr, arr+20);
}
于 2009-08-07T21:52:59.670 に答える
4

ロスのシミュレーションの本は、次のようなことを示唆しています。


double return[10];
for(int i=0, n=100; i < 10; i++) {
  int x = rand(n);  //pseudocode - generate an integer on [0,n]
  return[i] = arr[x];
  arr[x] = arr[n];
  n--;
}

于 2009-08-07T21:54:09.883 に答える