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 个数字需要 5 毫秒。

Answer 1

对于大范围，libstdc++ 将使用高效的拒绝算法(在 Devroye、L. 非均匀随机变量生成 之后)，但前提是 C99 TR1 数学可用(_GLIBCXX_USE_C99_MATH_TR1)。否则，它将退回到简单的等待时间方法，其性能在范围内呈线性。

我建议检查 _GLIBCXX_USE_C99_MATH_TR1 的值，以及性能是否在最新版本的 g++ 上有所提高。