c ++ 11 binomial_distribution STL очень медленно
Я генерирую биномиально распределенные случайные числа, используя STL ‘random’. Это становится чрезвычайно медленным, когда диапазон большой. Для диапазона 40 требуется 12 секунд, чтобы сгенерировать 100 чисел. Для больших диапазонов время резко увеличивается (мне нужны диапазоны около 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 мс.
Решение
Для больших диапазонов libstdc ++ будет использовать эффективный алгоритм отклонения (после Devroye, L. Неравномерная генерация случайных величин), но только если доступна математика C99 TR1 (_GLIBCXX_USE_C99_MATH_TR1). В противном случае он обратится к простому методу времени ожидания, который будет иметь линейную производительность в диапазоне.
Я бы посоветовал проверить значение _GLIBCXX_USE_C99_MATH_TR1 и улучшается ли производительность на более поздних версиях g ++.
Другие решения
Вы должны обязательно включить оптимизацию, когда производительность имеет значение.
Также вам следует взглянуть на доступные механизмы случайных чисел и убедиться, что вы используете тот, который отвечает вашим требованиям к производительности / размеру / качеству.
Если проблема действительно в том, что std::binomial_distribution::operator() не работает должным образом, возможно, вам придется использовать другую реализацию стандартной библиотеки, или альтернативную реализацию std::binomial_distribution, Boost должен иметь альтернативную реализацию <random> которую вы сможете использовать без особых проблем, libc ++ также имеет альтернативную реализацию, но ее будет сложнее использовать, поскольку вам придется заменить всю реализацию стандартной библиотеки.