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

For large ranges, libstdc++ will use an efficient rejection algorithm (after Devroye, L. Non-Uniform Random Variates Generation), but only if C99 TR1 math is available (_GLIBCXX_USE_C99_MATH_TR1). Otherwise, it will fall back to a simple waiting time method, which will have performance linear in the range.

I'd suggest checking the value of _GLIBCXX_USE_C99_MATH_TR1 and whether performance improves on more recent versions of g++.

于 2012-10-31T17:46:00.697 回答
1

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

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

如果问题确实是std::binomial_distribution::operator()性能不佳，您可能必须使用不同的标准库实现，或std::binomial_distribution. boost 应该有一个替代实现<random>，您应该可以毫不费力地使用它，libc++ 也有一个替代实现，但它会更难使用，因为您必须替换整个标准库实现。

于 2012-10-31T17:24:08.610 回答