c ++ 11 STL的binomial_distribution非常慢

Question

我使用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个数字的生成需要5ms.

Answer 1

对于大范围,libstdc ++将使用有效的拒绝算法(在Devroye,L.非均匀随机变量生成之后),但仅当C99 TR1数学可用时(_GLIBCXX_USE_C99_MATH_TR1).否则,它将回退到一个简单的等待时间方法,该方法将具有该范围内的线性性能.

我建议检查_GLIBCXX_USE_C99_MATH_TR1更新版本的g ++的性能和性能是否有所提高.