Эффективная генерация случайных чисел с С++ 11 <random>

Я пытаюсь понять, как предполагается использовать функции генерации случайных чисел С++ 11. Меня беспокоит производительность.

Предположим, что нам нужно создать ряд случайных чисел между 0..k, но k изменяется на каждом шаге. Каков наилучший способ продолжения?

Пример:

for (int i=0; i < n; ++i) {
    int k = i; // of course this is more complicated in practice
    std::uniform_int_distribution<> dist(0, k);
    int random_number = dist(engine);
    // do something with random number
}

Распределения, которые предоставляет заголовок <random>, очень удобны. Но они непрозрачны для пользователя, поэтому я не могу легко предсказать, как они будут работать. Не ясно, например, сколько (если таковые имеются) служебных данных времени выполнения будут вызваны конструкцией dist выше.

Вместо этого я мог бы использовать что-то вроде

std::uniform_real_distribution<> dist(0.0, 1.0);
for (int i=0; i < n; ++i) {
    int k = i; // of course this is more complicated in practice
    int random_number = std::floor( (k+1)*dist(engine) );
    // do something with random number
}

который позволяет избежать создания нового объекта на каждой итерации.

Случайные числа часто используются в численных симуляциях, где важна производительность. Каков наилучший способ использования <random> в этих ситуациях?

Пожалуйста, не отвечайте "profile it". Профилирование является частью эффективной оптимизации, но это хорошее понимание того, как предполагается использовать библиотеку и характеристики производительности этой библиотеки. Если ответ заключается в том, что он зависит от стандартной реализации библиотеки или что единственный способ узнать, это профилировать его, то я бы предпочел не использовать дистрибутивы из <random> вообще. Вместо этого я могу использовать свою собственную реализацию, которая будет прозрачной для меня и намного легче оптимизировать, если при необходимости.

Ответ 1

Одна вещь, которую вы можете сделать, - иметь постоянный объект распространения, чтобы каждый раз создавать объект param_type следующим образом:

template<typename Integral>
Integral randint(Integral min, Integral max)
{
    using param_type =
        typename std::uniform_int_distribution<Integral>::param_type;

    // only create these once (per thread)
    thread_local static std::mt19937 eng {std::random_device{}()};
    thread_local static std::uniform_int_distribution<Integral> dist;

    // presumably a param_type is cheaper than a uniform_int_distribution
    return dist(eng, param_type{min, max});
}

Ответ 2

Для максимальной производительности, прежде всего, рассмотрим разные PRNG, такие как xorshift128 +. Сообщается, что он более чем в два раза быстрее, чем mt19937 для 64-битных случайных чисел; см. http://xorshift.di.unimi.it/. И он может быть реализован с несколькими строками кода.

Кроме того, если вам не нужно "идеально сбалансированное" равномерное распределение, а ваш k намного меньше 2^64 (что, вероятно, так), я бы предложил написать просто что-то вроде:

uint64_t temp = engine_64(); // generates 0 <= temp < 2^64
int random_number = temp % (k + 1); // crop temp to 0,...,k

Обратите внимание, однако, что операции с целым делением/модулем не являются дешевыми. Например, на процессоре Intel Haswell они принимают 39-103 процессорных цикла для 64-битных чисел, что, вероятно, намного дольше, чем вызов MT19937 или xorshift + engine.