为了在C++中从泊松分布中抽取随机数，通常建议使用
RNG_type rng;
std::poisson_distribution<size_t> d(1e-6);
auto r = d(rng);
每次呼叫时std::poisson_distribution对象，整个随机位序列被消耗（例如 32 位标准::mt19937 http://www.cplusplus.com/reference/random/mt19937/, 64 位为std::mt19937_64 http://www.cplusplus.com/reference/random/mt19937_64/）。让我惊讶的是，如此低的平均值（mean = 1e-6），绝大多数时候，只需几个位就足以确定要返回的值为 0。然后可以缓存其他位以供以后使用。
假设设置为 true 的位序列与泊松分布的高返回值相关联，当使用以下平均值时1e-6，任何不以 19 个 true 开头的序列都必然返回零！的确，
1 - 1/2^19 < P(0, 1e-6) < 1 - 1/2^20
, where P(n, r)表示抽签的概率n来自均值的泊松分布r。不浪费位的算法将在一半的时间使用一位，四分之一的时间使用两位，八分之一的时间使用三位，......
是否有一种算法可以通过在绘制泊松数时消耗尽可能少的位来提高性能？与其他方法相比，是否有其他方法可以提高性能std::poisson_distribution当我们考虑低均值时？
回应@Jarod42 的评论，他说
想知道使用更少的位数是否不会破坏等概率......
我不认为这会破坏等概率。在一次模糊的测试中，我用简单的伯努利分布考虑了同样的问题。我以概率抽样真实1/2^4并以概率采样错误1 - 1/2^4。功能drawWithoutWastingBits一旦在缓存和函数中看到 true 就停止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
