Чтобы получить случайное число из распределения Пуассона в C ++, обычно рекомендуется использовать
RNG_type rng;
std::poisson_distribution<size_t> d(1e-6);
auto r = d(rng);
При каждом вызове объекта std::poisson_distribution потребляется вся последовательность случайных битов ( например, 32 бита с std :: mt19937 , 64 бита для std :: mt19937_64 ). Мне кажется, что при таком низком среднем значении (mean = 1e-6) в подавляющем большинстве случаев достаточно всего нескольких битов, чтобы определить, что возвращаемое значение равно 0. Остальные биты затем можно кэшировать для дальнейшего использования.
Предполагая, что последовательность битов, установленная в истину, связана с высоким значением, возвращаемым из распределения Пуассона, при использовании среднего значения 1e-6 любая последовательность, не начинающаяся с 19 истинных значений, обязательно возвращает ноль! Действительно,
1 - 1/2^19 < P(0, 1e-6) < 1 - 1/2^20
, где P(n, r) обозначает вероятность получения n из распределения Пуассона со средним r. Алгоритм, который не тратит впустую биты, будет использовать один бит в половине случаев, два бита в четверть случаев, три бита в восьмую часть времени, ....
Есть ли алгоритм что может улучшить производительность, потребляя как можно меньше бит при рисовании чисел Пуассона? Есть ли другой способ улучшить производительность по сравнению с std::poisson_distribution, когда мы рассматриваем низкое среднее значение?
В ответ на комментарий @ Jarod42, который сказал:
Интересно, если использование меньшего количества бит не нарушит равновероятность ...
Я не думаю, что это нарушит равновероятность. В смутной попытке проверить это, я рассматриваю тот же вопрос с простым распределением Бернулли. Я выбираю истину с вероятностью 1/2^4 и выборку ложь с вероятностью 1 - 1/2^4. Функция drawWithoutWastingBits останавливается, как только видит в кэше истинное значение, а функция drawWastingBits потребляет 4 бита, какими бы ни были эти биты.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
bool drawWithoutWastingBits(std::vector<bool>& cache, size_t& cache_index)
{
/*
Get a true with probability 1/2^4 (=1/16=0.0625) and a false otherwise
*/
size_t nbTrues = 0;
while (cache[cache_index])
{
++nbTrues;
++cache_index;
if (nbTrues == 4)
{
return true;
}
}
++cache_index;
return false;
}
bool drawWastingBits(std::vector<bool>& cache, size_t& cache_index)
{
/*
Get a true with probability 1/2^4 (=1/16=0.0625) and a false otherwise
*/
bool isAnyTrue = false;
for (size_t i = 0 ; i < 4; ++i)
{
if (cache[cache_index])
{
isAnyTrue = true;
}
++cache_index;
}
return !isAnyTrue;
}
int main()
{
/*
Just cache a lot of bits in advance in `cache`. The same sequence of bits will be used by both function.
I am just caching way enough bits to make sure they don't run out of bits below
I made sure to have the same number of zeros and ones so that any deviation is caused by the methodology and not by the RNG
*/
// Produce cache
std::vector<bool> cache;
size_t nbBitsToCache = 1e7;
cache.reserve(nbBitsToCache);
for (size_t i = 0 ; i < nbBitsToCache/2 ; ++i)
{
cache.push_back(false);
cache.push_back(true);
}
// Shuffle cache
{
std::mt19937 mt(std::random_device{}());
std::shuffle(cache.begin(), cache.end(), mt);
}
// Draw without wasting bits
{
size_t nbDraws = 1e6;
size_t cache_index = 0;
std::pair<size_t, size_t> outcomes = {0,0};
for (size_t r = 0 ; r < nbDraws ; ++r)
{
drawWithoutWastingBits(cache, cache_index) ? ++outcomes.first : ++outcomes.second;
assert(cache_index <= cache.size());
}
assert(outcomes.first + outcomes.second == nbDraws);
std::cout << "Draw Without Wasting Bits: prob true = " << (double)outcomes.first / nbDraws << "\n";
}
// Draw wasting bits
{
size_t nbDraws = 1e6;
size_t cache_index = 0;
std::pair<size_t, size_t> outcomes = {0,0};
for (size_t r = 0 ; r < nbDraws ; ++r)
{
drawWastingBits(cache, cache_index) ? ++outcomes.first : ++outcomes.second;
assert(cache_index <= cache.size());
}
assert(outcomes.first + outcomes.second == nbDraws);
std::cout << "Draw Wit Wasting Bits: prob true = " << (double)outcomes.first / nbDraws << "\n";
}
}
Возможный вывод
Draw Without Wasting Bits: prob true = 0.062832
Draw Wit Wasting Bits: prob true = 0.062363