C++11 STL的二项式分布函数非常慢

Question

我正在使用STL的“random”生成二项分布的随机数。当范围很大时，它变得非常缓慢。对于范围为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毫秒。

- user1672572

---

你的问题是什么？ - alestanis

Answer 1

对于大范围的数字，libstdc++将使用高效的拒绝算法（基于Devroye, L. Non-Uniform Random Variates Generation），但仅当C99 TR1 math可用时（_GLIBCXX_USE_C99_MATH_TR1）。否则，它将回退到简单的等待时间方法，其性能与范围成线性关系。

建议检查_GLIBCXX_USE_C99_MATH_TR1的值，并检查在更高版本的g++上是否可以提高性能。

- ecatmur

Answer 2

当性能很重要时，您应该确保启用优化。

此外，您应该查看可用的随机数引擎，并确保使用符合您性能/大小/质量要求的引擎。

如果问题确实是因为 std::binomial_distribution::operator() 的性能不足，您可能需要使用不同的标准库实现或 std::binomial_distribution 的替代实现。boost 应该有一个 <random> 的替代实现，您应该能够轻松使用，libc++ 也有一个替代实现，但它将更难使用，因为您必须替换整个标准库实现。

- bames53