7

一貫してシードされた Random が与えられた場合:

Random r = new Random(0);

r.Next()一貫して呼び出すと、同じシリーズが生成されます。N回呼び出すことなく、そのシリーズのN番目の値をすばやく発見する方法はありますか?r.Next()

私のシナリオは、によって作成された値の膨大な配列ですr.Next()。アプリは、任意のインデックスで配列から値を読み取ることがあります。配列を削除し、代わりにオンデマンドで値を生成することにより、メモリ使用量を最適化したいと考えています。しかし、配列の 500 万番目のインデックスをシミュレートするために 500 万回総当たり攻撃r.Next()を行うと、配列を保存するよりもコストがかかります。N 番目の .Next() 値への道をショートカットすることは可能ですか?

4

4 に答える 4

7

BCL で使用されている PRNG の詳細はわかりませんが、シリーズのN番目の値の適切な閉じた形式のソリューションを見つけることは非常に困難/不可能であることがわかると思います。

この回避策はどうですか:

乱数ジェネレーターへのシードを目的のインデックスにしてから、最初に生成された数値を選択します。これは同様に「決定論的」であり、O(1) 空間で幅広い範囲で遊ぶことができます。

static int GetRandomNumber(int index)
{
    return new Random(index).Next();
}
于 2011-03-22T00:49:33.063 に答える
2

理論的には、正確なアルゴリズムと初期状態を知っていれば、シリーズを複製できますが、最終結果は r.next() を呼び出すのと同じになります。

乱数をどれだけ「良い」ものにする必要があるかに応じて、数値を生成するのが比較的簡単/高速な線形合同ジェネレーターに基づいて独自の PRNG を作成することを検討できます。「悪い」PRNGを使用できる場合は、目的に適した他のアルゴリズムが存在する可能性があります。r.next() から大量の数値の配列を格納するよりも、これが高速/優れているかどうかは別の問題です。

于 2011-03-22T00:59:06.667 に答える
1

いいえ、あるとは思いません。一部のRNGアルゴリズム（線形合同法ジェネレーターなど）では、原則として、nステップを繰り返さずにn番目の値を取得できますが、Randomクラスはそれを行う方法を提供しません。

使用するアルゴリズムが原則としてそれを可能にするかどうかはわかりません-それはクヌースの減算RNGの変形（詳細はドキュメントに開示されていません）であり、元のクヌースRNGはある種の多項式の算術と同等である必要があるようですn番目の値へのアクセスを許可するものですが、（1）実際にはチェックしていません。また、（2）Microsoftが行った微調整によって、それが機能しなくなる可能性があります。

十分な「スクランブリング」関数fがある場合は、f（0）、f（f）の代わりに、f（0）、f（1）、f（2）、...を乱数のシーケンスとして使用できます。 （0））、f（f（f（0）））など（後者はおおよそほとんどのRNGが行うことです）、そしてもちろん、好きなときにシーケンスを開始するのは簡単です。ただし、適切なfを選択する必要があり、標準のRNGよりも遅くなる可能性があります。

于 2011-03-22T00:54:36.347 に答える
-1

「インデックス」と「ランダム値」の独自のオンデマンド辞書を作成できます。これは、プログラムを実行するたびに常に同じ順序でインデックスを「要求」するか、プログラムを実行するたびに結果が同じであっても気にしないことを前提としています。

Random rnd = new Random(0);
Dictionary<int,int> randomNumbers = new Dictionary<int,int>();
int getRandomNumber(int index)
{
    if (!randomNumbers.ContainsKey(index))
        randomNumbers[index] = rnd.Next();
    return randomNumbers[index];
}
于 2011-03-22T01:10:56.007 に答える