6

STLの「ランダム」を使用して、二項分布の乱数を生成しています。範囲が大きいと極端に遅くなります。範囲が 40 の場合、100 個の数値を生成するのに 12 秒かかります。より大きな範囲では、時間が劇的に増加します (約 10000 の範囲が必要です)。確率パラメータには依存していないようです。g++ 4.5.0 を使用しています。

#include <iostream>
#include <random>

using namespace std;

vector<int> v;

default_random_engine gen(123);
binomial_distribution<int> rbin(40,0.7);

int main(){
  v.reserve(2000);
  for(int i=0; i<100;++i){
    v.push_back(rbin(gen));
   }
}

出力：

50.~/.../fs/> g++ -std=c++0x q.cpp 
51.~/.../fs/> time ./a.out 
real    0m12.102s
user    0m12.094s
sys     0m0.002s
52.~/.../fs/>

正規近似を使用できますが、確率パラメーターの極端な値には適していません。

アップデート：

「-O3」オプションを使用すると、時間は最大 2 秒になります。g++ 4.6.3 では、この問題は完全に解消されました。範囲に対する時間の依存性はほとんどなく、100 個の数値の生成には 5 ミリ秒かかります。

4

2 に答える 2

7

範囲が広い場合、libstdc++ は効率的な棄却アルゴリズムを使用します (Devroye、L. Non-Uniform Random Variates Generation の後) が、C99 TR1 数学が利用可能な場合に限ります ( _GLIBCXX_USE_C99_MATH_TR1)。それ以外の場合は、範囲内でパフォーマンスが線形になる単純な待機時間メソッドにフォールバックします。

_GLIBCXX_USE_C99_MATH_TR1値を確認し、 g++ の最近のバージョンでパフォーマンスが向上するかどうかを確認することをお勧めします。

于 2012-10-31T17:46:00.697 に答える
1

パフォーマンスが重要な場合は、必ず最適化を有効にする必要があります。

また、利用可能な乱数エンジンを調べて、パフォーマンス/サイズ/品質の要件を満たすものを使用していることを確認する必要があります。

問題が本当にstd::binomial_distribution::operator()適切に実行されていないことである場合は、別の標準ライブラリ実装、またはの代替実装を使用する必要がある場合がありますstd::binomial_distribution。boostには、<random>あまり問題なく使用できる代替実装が必要です。libc++にも代替実装がありますが、標準ライブラリの実装全体を置き換える必要があるため、使用がより困難になります。

于 2012-10-31T17:24:08.610 に答える