Я работаю над моделированием случайных движений частиц, движущихся в решетке. По этой причине я должен создать огромное количество случайных чисел, около 10 ^ 12 и выше. В настоящее время я использую возможности, предоставляемые С++ 11 с помощью <random>. При профилировании моей программы я вижу, что в <random> проводится большое количество времени. Подавляющее большинство этих чисел составляет от 0 до 1, равномерно распределенных. Здесь a тогда мне нужно число из биномиального распределения. Но основное внимание уделяется номерам 0..1.
Вопрос: что я могу сделать, чтобы сократить время процессора, необходимое для генерации этих чисел, и каково влияние на их качество?
Как вы можете видеть, я пробовал разные двигатели, но это не оказало большого влияния на процессорное время. Далее, в чем разница между моими uniform01(gen) и generate_canonical<double,numeric_limits<double>::digits>(gen)?
Изменить: Прочитав ответы, я пришел к выводу, что для моей проблемы нет идеального решения. Таким образом, я решил сначала сделать свою программу многопоточными и запустить несколько RNG в разных потоках (засеянных одним номером random_device + индивидуальным приращением потока). В настоящее время эти швы являются наиболее неизбежным шагом (в любом случае потребуется многопоточность). В качестве еще одного шага, ожидающего рассмотрения точных требований, я перехожу к предлагаемому Intel RNG или Thrust. Это означает, что моя реализация RNG не должна быть сложной, и в настоящее время это не так. Но сейчас мне нравится фокусироваться на физической корректности моей модели, а не на программировании, это происходит, как только выход моей программы физически корректен. Thrust Относительно Intel RNG
Вот что я делаю сейчас:
class Generator {
public:
Generator();
virtual ~Generator();
double rand01(); //random number [0,1)
int binomial(int n, double p); //binomial distribution with n samples with probability p
private:
std::random_device randev; //seed
/*Engines*/
std::mt19937_64 gen;
//std::mt19937 gen;
//std::default_random_engine gen;
/*Distributions*/
std::uniform_real_distribution<double> uniform01;
std::binomial_distribution<> binomialdist;
};
Generator::Generator() : randev(), gen(randev()), uniform01(0.,1.), binomial(1,1.) {
}
Generator::~Generator() { }
double Generator::rand01() {
//return uniform01(gen);
return generate_canonical<double,numeric_limits<double>::digits>(gen);
}
int Generator::binomialdist(int n, double p) {
binomial.param(binomial_distribution<>::param_type(n,p));
return binomial(gen);
}
Вы можете предварительно обработать случайные числа и использовать их, когда вам нужно.
Если вам нужны истинные случайные числа, я предлагаю вам использовать такую услугу, как http://www.random.org/, которая обеспечивает случайные числа, вычисляемые окружающей средой, а не некоторый алгоритм.
И, говоря о случайных числах, вы также должны это проверить:
Если вам нужно огромное количество случайных чисел, и я имею в виду MASSIVE, сделайте тщательный поиск в Интернете для генератора случайных чисел с плавающей запятой IBM, опубликованного, возможно, десять лет назад. Вам придется покупать либо машину PowerPC, либо новую машину Intel с плавным многократным добавлением. Они достигли случайных чисел со скоростью один за цикл на ядро. Поэтому, если вы купили новый Mac Pro, вы могли бы достичь, вероятно, 50 миллиардов случайных чисел в секунду.
Возможно, вместо использования процессора вы можете использовать графический процессор для генерации множества чисел одновременно?
http://http.developer.nvidia.com/GPUGems3/gpugems3_ch37.html
На моем i3 следующая программа запускается примерно через пять секунд:
#include <random>
std::mt19937_64 foo;
double drand() {
union {
double d;
long long l;
} x;
x.d = 1.0;
x.l |= foo() & (1LL<<53)-1;
return x.d-1;
}
int main() {
double d;
for (int i = 0; i < 1e9; i++)
d += drand();
printf("%g\n", d);
}
в то время как замена вызова drand() осуществляется с помощью следующих результатов в программе, которая работает примерно через десять секунд:
double drand2() {
return std::generate_canonical<double,
std::numeric_limits<double>::digits>(foo);
}
Использование следующего вместо drand() также приводит к программе, которая работает примерно через десять секунд:
std::uniform_real_distribution<double> uni;
double drand3() {
return uni(foo);
}
Возможно, хакерский drand() выше подходит для ваших целей лучше, чем стандартные решения.
OP запрашивает ответ для
1. Скорость генерации - предполагая, что набор 10E+012 случайных чисел будет "массивным"
и
2. Качество генератора - со слабым предположением, что числа, равномерно распределенные по некоторому диапазону значений, также являются случайными
Тем не менее, есть больше кардинальных аспектов, которые необходимо решить и успешно решить для реальной системы:
A. Определите, должна ли ваша симуляция системы обеспечивать гарантию повторяемости последовательности случайных чисел для будущих повторных экспериментов.
Если это не так, повторные эксперименты с симулированным экспериментом будут давать в основном разные результаты, тогда процесс рандомизатора (или рандомизатор и рандомизированный селектор) не должен беспокоиться об их повторении -entrant, state-full mode of operation и будет намного проще реализовать.
B. Определите, на каком уровне вам нужно доказать качество случайности генерируемых случайных чисел (или должны быть созданы сгенерированные множества случайных чисел к некоторому конкретному закону статистической теории (некоторые известные синтетические распределения или по-настоящему случайные с предельной колмогоровской сложностью полученного набора случайных чисел)). Не нужно быть экспертом NSA, чтобы заявить, что числовые генераторы истинно-случайных последовательностей являются очень сложной проблемой и имеют вычислительные затраты, связанные с производством продуктов с высокой степенью хаотичности.
Гипер-хаотические и истинно-случайные последовательности являются вычислительно дорогостоящими. Использование генераторов с низкой или плохой случайностью не является вариантом для приложений, чувствительных к качеству случайности (независимо от того, что может сказать маркетинговая бумага, никакая система с MIL-STD или NSA никогда не будет пытаться использовать это скомпрометированное качество в окружающей среде, где результаты действительно имеют значение, так почему бы не согласиться на меньшее в научных симуляциях? Возможно, это не проблема, если вы не против пропустить так много "невидимых" состояний имитируемых явлений).
C. Проверьте, сколько случайных чисел ваша система моделирования должна "потреблять по [usec]" и является ли этот параметр требования к дизайну постоянным или может быть увеличен, потоковая, векторная, распределенная вычислительная инфраструктура на основе Grid/Cloud.
D. Требуется ли вашей симуляционной системе поддерживать глобальное или per-thread или perGrid/CloudNode индивидуальное управление доступом к пулам рандомизированных чисел в случае векторизации или Grid/Cloud основанную на вычислительной стратегии.
Самый быстрый [1] и лучший [2] решение с [A] и [B], а опции для [D] - предварительная генерация максимальной случайности (и оплачивать приемлемую стоимость [C] и [D] для контроля доступа и управления доступом для повторного чтения из пула, а не для повторного генерации).