Получить значения из нескольких распределений с одним генератором - PullRequest
Новая
       24

Получить значения из нескольких распределений с одним генератором

0 голосов
/ 25 августа 2018

Я пытаюсь реализовать метод Alias ​​, также описанный здесь . Это алгоритм, который позволяет делать выборки из взвешенных N-сторонних кубиков в O (1).

Алгоритм требует генерации двух значений:

  • Равномерно распределенное целое число i в [0, N]
  • Равномерно распределенное действительное y в [0, 1)

В документе указывается, что эти два числа могут быть получены одним действительным числом x между [0, N). Затем из x можно получить два значения:

  • i = floor(x)
  • y = x - i

Теперь другие реализации, которые я видел, требуют генератора случайных чисел два раза, один для генерации i и один для генерации y. Учитывая, что я использую довольно дорогой генератор (std::mt19937) и что мне нужно многократно выполнять выборку, мне стало интересно, существует ли лучший подход с точки зрения производительности при сохранении качества результата.

Я не уверен, имеет ли смысл использование uniform_real_distribution для генерации x, как если бы N было большим, тогда распределение y станет более разреженным, поскольку double не распределены равномерно. Может быть, есть способ вызвать двигатель, получить случайные биты, а затем сгенерировать i и y из них напрямую?

Ответы [ 2 ]

0 голосов
/ 26 августа 2018

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

  1. Я не использовал 32-битный ГСЧ. В принципе, нет 32-битной платформы и программного обеспечения для заботы. Поэтому я использовал std :: mt19937_64 в качестве базового генератора. Один 64-битный неподписанный int на вызов. Позже я попытался использовать один из 64-битных RNG PCG, в целом быстрее хороший результат.

  2. Верхние N биты, которые будут использоваться непосредственно для выбора из таблицы (игра в кости в вашем случае). Вы можете страдать от смещения по модулю, поэтому мне удалось расширить таблицу до точной степени 2 (2 10 в моем случае, 10 бит для выборки индекса)

  3. Оставшиеся 54 бита были использованы для получения равномерного двойного случайного числа по предложению С. Винья.

  4. Если вам нужно более 11 битов для индексации, вы можете либо жить с уменьшенной случайностью в мантиссе, либо заменить double y на тщательно составленное целочисленное сравнение.

Вдоль строк псевдокод (не проверено!) 

uint64_t mask = (1ULL << 53ULL) - 1ULL;

auto seed{ 98765432101ULL };
auto rng = std::mt19937_64{seed};

for (int k = 0; k != 1000; ++k) {
    auto rv = rng();
    auto idx = rv >> uint64_t(64 - 10); // needed only 10 bits for index
    double y = (rv & mask) * (1. / (1ULL << 53ULL)); // 53 bits used for mantissa
    std::cout << idx << "," << y << '\n';
}

Ссылка на целочисленное2 двойное преобразование С. Винья для ГСЧ: http://xoshiro.di.unimi.it/, в самом конце страницы

0 голосов
/ 25 августа 2018

Вы правы, с их методом распределение y будет становиться все менее и менее равномерным с увеличением N.

Фактически, для N выше 2 ^ 52 y будет ровно 0, так как все числа выше этого значения являются целыми числами для двойной точности. 2 ^ 52 составляет 4 503 599 627 370 496 (4,5 квадриллиона).

Это не имеет значения для разумных значений N. С вами все будет в порядке, если ваш N меньше 2 ^ 26 (67 миллионов), интуитивно. У твоего кубика нет астрономического числа сторон?

...