Быстрый, беспристрастный, целочисленный псевдослучайный генератор с произвольными границами

В данных обстоятельствах самый простой подход может работать лучше всего. Один чрезвычайно простой подход, который может сработать, если ваш PRNG достаточно быстрый, состоит в том, чтобы предварительно вычислить на единицу меньше, чем следующая большая степень 2, чем ваш N, чтобы использовать в качестве маски. Т.е., учитывая некоторое число, которое выглядит как 0001xxxxxxxx в двоичном формате (где x означает, что нам все равно, если это 1 или 0) мы хотим маску, как 000111111111,

Оттуда мы генерируем числа следующим образом:

1. Генерация числа
2. and это с вашей маской
3. если результат> n, переходите к 1

Точная эффективность этого будет зависеть от того, насколько N близко к степени 2. Каждая последующая степень 2 (очевидно, достаточно) удваивает свою предшественницу. Таким образом, в лучшем случае N ровно на единицу меньше, чем степень 2, и наш тест на шаге 3 всегда проходит. Мы добавили только маску и сравнение со временем, затраченным на сам PRNG.

В худшем случае N в точности равно степени 2. В этом случае мы ожидаем выбросить примерно половину сгенерированных нами чисел.

В среднем N оказывается примерно посередине между степенями 2. Это означает, что в среднем мы отбрасываем примерно один из четырех входов. Мы можем почти игнорировать маску и сами сравнения, поэтому наша потеря скорости по сравнению с «необработанным» генератором в основном равна количеству его выходов, которые мы отбрасываем, или 25% в среднем.

Libdivide или любые другие сложные способы оптимизации этого модуля просто излишни. В ситуации, как ваша, единственный разумный подход заключается в

1. убедитесь, что размер таблицы равен степени двух (добавьте отступы, если необходимо!)

2. замените операцию по модулю битовой маской. Как это:

   size_t tableSize = 1 << 16;
   size_t tableMask = tableSize - 1;
   
   ...
   
   histogram[prng() & tableMask]
   

Операция с битовой маской — это один цикл на любом процессоре, который стоит своих денег, вы не можете превзойти его скорость.

—

Замечания:
Я не знаю о качестве вашего генератора случайных чисел, но, возможно, не стоит использовать последние биты случайного числа. Некоторые RNG создают плохую случайность в последних битах и ​​лучшую случайность в старших битах. Если это так с вашим RNG, используйте сдвиг битов, чтобы получить наиболее значимые биты:

size_t bitCount = 16;

...

histogram[prng() >> (64 - bitCount)]

Это так же быстро, как битовая маска, но она использует разные биты.

Вы могли бы продлить histogram до «большой» степени двойки путем его циклического заполнения, заполняя конечные пробелы некоторой фиктивной величиной (гарантированно никогда не встречающейся в реальных данных). Например. с учетом гистограммы

[10, 5, 6]

растяните его на длину 16 примерно так (при условии -1 является подходящим стражем):

[10, 5, 6, 10, 5, 6, 10, 5, 6, 10, 5, 6, 10, 5, 6, -1]

Затем выборка может быть выполнена с помощью бинарной маски histogram[prng() & mask] где mask = (1 << new_length) - 1с проверкой дозорного значения для повторения, то есть

int value;
do {
value = histogram[prng() & mask];
} while (value == SENTINEL);

// use `value` here

Расширение является более длинным, чем необходимо, чтобы сделать повторные попытки маловероятными, гарантируя, что подавляющее большинство элементов являются действительными (например, в приведенном выше примере только 1/16 поисков «потерпят неудачу», и эта скорость может быть дополнительно уменьшена путем расширения ее, например, до 64 ). Вы могли бы даже использовать подсказку «предсказание ветвления» (например, __builtin_expect в GCC) на проверку, чтобы компилятор заказывал код как оптимальный для случая, когда value != SENTINEL, что, надеюсь, является общим случаем.

Это очень большой компромисс между памятью и скоростью.

Просто несколько идей, чтобы дополнить другие хорошие ответы:

1. Какой процент времени тратится на операцию по модулю, и как вы узнаете, что это за процент? Я спрашиваю только потому, что иногда люди говорят, что что-то ужасно медленное, хотя на самом деле это происходит менее чем в 10% случаев, и они думают, что это что-то большое, потому что они используют глупый профайлер, работающий только на время. (Мне трудно представить себе операцию по модулю, отнимающую много времени по сравнению с генератором случайных чисел.)

2. Когда станет известно количество ведер? Если это не меняется слишком часто, вы можете написать программу-генератор. Когда количество блоков меняется, автоматически распечатайте новую программу, скомпилируйте, создайте ссылку и используйте ее для массового выполнения.
   Таким образом, компилятор будет знать количество сегментов.

3. Рассматривали ли вы использование генератор квазислучайных чисел, в отличие от псевдослучайного генератора? Это может дать вам более высокую точность интеграции в гораздо меньшем количестве образцов.

4. Может ли быть уменьшено количество сегментов без чрезмерного снижения точности интеграции?

Неоднородность, о которой предупреждает dbaupp, может быть отклонена путем отклонения&перерисовка значений не менее M*(2^64/M) (прежде чем взять модуль).
Если M может быть представлен не более чем в 32 битах, вы можете получить более чем на одно значение меньше M повторным умножением (см. ответ Давида Эйзенстата) или divmod; в качестве альтернативы, вы можете использовать битовые операции, чтобы выделить битовые шаблоны достаточно долго для Mснова отклоняя значения не менее M,
(Я был бы удивлен тем, что модуль генерации случайных чисел не карликов по времени / циклу / потреблению энергии.)

Чтобы кормить ведро, вы можете использовать std::биномиальное распределение напрямую кормить каждое ведро вместо того, чтобы кормить одно ведро одним образцом:

Следующее может помочь:

int nrolls = 60; // number of experiments
const std::size_t N = 6;
unsigned int bucket[N] = {};

std::mt19937 generator(time(nullptr));

for (int i = 0; i != N; ++i) {
double proba = 1. / static_cast<double>(N - i);
std::binomial_distribution<int> distribution (nrolls, proba);
bucket[i] = distribution(generator);
nrolls -= bucket[i];
}

Живой пример

Вместо целочисленного деления вы можете использовать математику с фиксированной запятой, т.е. целочисленное умножение & Bitshift. Скажем, если ваш prng () возвращает значения в диапазоне 0-65535, и вы хотите, чтобы это квантовалось в диапазоне 0-99, тогда вы делаете (prng () * 100) >> 16. Просто убедитесь, что умножение не переполняет ваш целочисленный тип, поэтому вам, возможно, придется сдвинуть результат prng () вправо. Обратите внимание, что это отображение лучше, чем по модулю, поскольку оно сохраняет равномерное распределение.