8

私は現在、乱数ジェネレーター ( gslまたはboost ) を使用している C/C++ プロジェクトに取り組んでいます。アイデア全体は、シードを受け取って結果を返す非自明な確率プロセスに単純化できます。プロセスのさまざまな実現の平均を計算しています。

したがって、シードは重要です。プロセスは異なるシードを使用する必要があります。そうしないと、平均に偏りが生じます。

これまでのところ、私はtime(NULL)種を与えるために使用しています。ただし、2 つのプロセスが同じ秒に開始された場合、シードは同じです。これは、( openMPを使用して)並列化を使用しているために発生します。

だから、私の質問は: 独立したシードを与える C/C++ で「シード ギバー」を実装する方法は?

たとえば、私はスレッド番号 ( thread_num)を使用していますseed = time(NULL)*thread_num。ただし、これはシードが相関していることを意味します。シードは相互に倍数です。それは「疑似ランダム」に問題を引き起こしますか、それともシーケンシャルシードと同じくらい良いですか?

要件は、Mac OS (私の pc) と OS Cent (クラスター) に似た Linux ディストリビューションの両方で動作する必要があることです (そして、独立した実現を自然に提供します)。

4

8 に答える 8

7

このために一般的に使用されるスキームは、各プロセス固有のRNGのシードを生成するために使用される「マスター」RNGを使用することです。

このようなスキームの利点は、計算全体が1つのシードによってのみ決定されることです。シードはどこかに記録して、シミュレーションを再生できます（これは厄介なバグのデバッグに役立つ場合があります）。

于 2012-10-08T12:41:18.673 に答える
5

Beowulf コンピューティング グリッドで同様の問題に遭遇しました。使用した解決策は、次のようにプロセスの pid を RNG シードに組み込むことでした。

time(NULL)*thread_num*getpid()

もちろん、/dev/urandom または /dev/random から整数に読み取ることもできます。

于 2012-10-08T10:04:17.107 に答える
3

この問題に直面したとき、私はよくseed_rngBoost.Uuid を使用します。time、clockおよびランダム データを使用し/dev/urandomてシードを計算します。次のように使用できます

#include <boost/uuid/seed_rng.hpp>
#include <iostream>

int main() {
  int seed = boost::uuids::detail::seed_rng()();
  std::cout << seed << std::endl;
}

は名前空間にseed_rng由来するため、予告なく削除される可能性があることに注意してください。detailその場合、に基づいて独自の実装を作成するseed_rngことはそれほど難しくありません。

于 2012-10-08T10:13:25.763 に答える
1

x86を使用していて、コードを移植不可能にすることを気にしない場合は、CPU（最大）クロックレート（約3 GHz）でインクリメントする64ビットカウンターであるタイムスタンプカウンター（TSC）を読み取ることができます。それをシードとして使用します。

#include <stdint.h>
static inline uint64_t rdtsc()
{
    uint64_t tsc;
    asm volatile
    ( 
        "rdtsc\n\t"
        "shl\t$32,%%rdx\n\t"       // rdx = TSC[ 63 : 32 ] : 0x00000000
        "add\t%%rdx,%%rax\n\t"     // rax = TSC[ 63 :  0 ]
        : "=a" (tsc) : : "%rdx"
    );
    return tsc;
}
于 2012-10-08T10:16:23.593 に答える
1

たぶん、C++11 から std::chrono 高解像度クロックを試すことができます:

クラス std::chrono::high_resolution_clock は、システムで利用可能な最小ティック周期のクロックを表します。std::chrono::system_clock または std::chrono::steady_clock のエイリアス、または 3 番目の独立したクロックの場合があります。

http://en.cppreference.com/w/cpp/chrono/high_resolution_clock

しかし、srand(0); に何か問題があるかどうかはわかりません。srand(1), srand(2)....しかし、rand に関する私の知識は非常に基本的なものです。:/

クレイジーな安全のために、これを考慮してください：

以下で説明するすべての疑似乱数ジェネレーターは、CopyConstructible および Assignable であることに注意してください。ジェネレーターをコピーまたは割り当てると、その内部状態がすべてコピーされるため、元のジェネレーターとコピーしたジェネレーターは同一の乱数シーケンスを生成します。

http://www.boost.org/doc/libs/1_51_0/doc/html/boost_random/reference.html#boost_random.reference.generators

ほとんどのジェネレーターには非常に長いサイクルがあるため、1 つ生成し、最初のジェネレーターとしてコピーし、オリジナルで X 数を生成し、2 番目としてコピーし、オリジナルで X 数を生成し、3 番目としてコピーすることができます。 X 時間未満のジェネレーターは、オーバーラップしません。

于 2012-10-08T13:28:55.933 に答える
1

同じ疑似乱数ジェネレーターで異なるシードを使用して生成された 2 つの無限時間シーケンスを比較すると、時間タウだけ同じように遅延していることがわかります。通常、この時間スケールは、2 つのランダム ウォークが無相関であることを確認するために、問題よりもはるかに大きくなります。

あなたの確率過程が高次元の位相空間にある場合、1 つの良い提案は次のようになると思います。

seed = MAXIMUM_INTEGER/NUMBER_OF_PARALLEL_RW*thread_num + time(NULL)

スキームを使用すると、時間タウが大きいことを保証できないことに注意してください!!

システムの時間スケールについてある程度の知識がある場合は、乱数ジェネレーターを何回か呼び出して、一定の時間間隔で等距離にあるシードを生成できます。

于 2012-10-08T10:33:12.420 に答える
1

Mac OSもUnixなので多分/dev/random. もしそうなら、それが種子を得るための最良の解決策です. それ以外の場合、ジェネレーターが良好であれば、time( NULL )一度取得してから、各ジェネレーターのシードに対してそれをインクリメントすると、かなり良い結果が得られます。

于 2012-10-08T10:08:49.337 に答える
1

私があなたの質問を理解している方法では、同じ疑似乱数生成アルゴリズムを使用する複数のプロセスがあり、(各プロセスの)乱数の各「ストリーム」を互いに独立させたいと考えています。私は正しいですか？

その場合、異なる (相関する) シードを与えても、rng アルゴリズムがそう言わない限り、何も保証しないと疑うのは正しいことです。基本的に 2 つの解決策があります。

シンプルバージョン

単一のシードを持つ単一の乱数ソースを使用します。次に、乱数をラウンドロビン方式で各プロセスに供給します。

この解決策は遅いですが、プロセスに与えた数が問題ないという保証を提供します。

同じことを行うことができますが、必要なすべての乱数を一度に生成してから、このセットをプロセスと同じ数のスライスに分割します。

そのために設計された RNG を使用する

論文や Web で、単一の初期状態から乱数の独立したストリームを提供するように特別に設計されたいくつかのアルゴリズムを見つけることができます。それらは複雑ですが、ほとんどがソース コードを提供します。一般に、RNG 空間 (初期状態から取得できる値) を上記のようにさまざまなチャンクに「分割」するという考え方です。使用されるアルゴリズムにより、指定された数の値をスキップした場合に RNG の状態がどのようになるかを簡単に計算できるため、それらはより高速です。

これらの発生器は、一般に「並列乱数発生器」と呼ばれます。最も人気のあるものは、おそらく次の 2 つです。

彼らのマニュアルをチェックして、彼らが何をするのか、どのようにそれを行うのか、そしてそれが本当に必要なものであるかどうかを完全に理解してください.

于 2012-10-11T06:20:41.657 に答える