C ++ 11 STL binomial_distribution extremely slow

Question

I generate binomially distributed random numbers using the STL 'random'. It becomes very slow when the range is large. For range 40, it takes 12 seconds to generate 100 numbers. For large ranges, time increases dramatically (I need ranges of about 10,000). It seems to be independent of 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)); } } 

Output:

 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 the normal approximation, but this is bad for extreme values ​​of the probability parameter.

Update:

With the option "-O3" the time becomes ~ 2 seconds. With g ++ 4.6.3, the problem completely disappears - there is practically no time dependence on the range, and the generation of 100 numbers takes 5 ms.

Answer 1

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

I would suggest checking the value of _GLIBCXX_USE_C99_MATH_TR1 and improving performance in later versions of g ++.

Answer 2

You should definitely enable optimization when performance matters.

You should also take a look at the available random number engines and make sure that you are using the one that meets your performance / size / quality requirements.

If the problem is that std::binomial_distribution::operator() not working properly, you may need to use another implementation of the standard library or an alternative implementation of std::binomial_distribution . boost should have an alternative implementation of <random> , which you can use without any problems, libC ++ also has an alternative implementation, but it will be more difficult to use, because you have to replace the entire implementation of the standard library.