c ++ 11 STL的二项分布极慢 [英] c++11 STL's binomial_distribution extremely slow

问题描述

我使用STL的'random'生成二进制分布的随机数。当范围很大时，它变得极慢。对于范围40，需要12秒来生成100个数字。对于更大的范围时间急剧增加（我需要范围大约10000）。它似乎不依赖于概率参数。我使用g ++ 4.5.0。

I am generating binomially distributed random numbers using STL's 'random'. It becomes extremely slow when the range is big. For the range 40 it takes 12 seconds to generate 100 numbers. For bigger ranges time increases dramatically (I need ranges around 10000). It does not seem to depend on the probability parameter. I am using 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/>

我可以使用正态近似，但它对概率参数的极值是不利的。

I could use Normal approximation, but it is bad for extreme values of probability parameter.

使用-O3选项时间变为〜2秒。使用g ++ 4.6.3，问题完全消失了 - 几乎没有时间对范围的依赖，100个数字的生成需要5ms。

With '-O3' option time becomes ~2 seconds. With g++ 4.6.3 the problem disappears entirely -- there is hardly any dependence of time on the range, and generation of 100 numbers takes 5ms.

推荐答案

对于大范围，libstdc ++将使用高效的拒绝算法（在Devroye，L. 非一致随机变量生成之后），但是只有当C99 TR1数学可用c> _GLIBCXX_USE_C99_MATH_TR1 ）。否则，它将回到一个简单的等待时间方法，这将具有范围内的性能线性。

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.

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

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

这篇关于c ++ 11 STL的二项分布极慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！