std::discrete_distribution接口背后的原因

Question

根据cppreference.com的说法，std::discrete_distribution接口要求库开发人员实现probabilities()和template<class Generator> result_type operator()(Generator& g, const param_type& params);。后者在cppreference.com上没有文档，但根据libc++ implementation的说法，它允许用户从给定权重序列的子序列中采样(并使用传递的生成器作为另一个生成器的熵源，但现在已经无关紧要)。我读过N3551 (关于std::discrete_distribution的唯一可搜索的提案)，它没有为std::discrete_distribution提供这样一个接口。

问题是，这样的接口只允许一个合理的实现，称为"roulette wheel selection" (需要一次调用随机数生成器和O(log(N))数组查找来进行二进制搜索)。另一种称为"alias method" (需要两次调用随机数生成器和一次数组查找)的算法不能用于实现此接口(如果我们将相应的概率存储在单独的数组中，则可以实现probabilities()，但这有点不公平和低效:)，因为如果我们需要从子序列中采样，则不能使用别名方法。

Answer 1

对于给定的随机分布，对构造参数对象的成本没有要求，对其内部表示的性质也没有要求。或者其他任何东西。具体地说，parameters对象不一定也不会仅仅是其构造参数的向量。构造参数对象必须执行任何必要的预计算/预处理，以使后续生成的分布更有效。(这不仅仅适用于discrete_distribution。有许多分布的自然参数需要非平凡成本的预计算步骤。)

为了实现“轮盘赌”算法，参数对象构造函数必须将参数转换为累积分布函数(CDF)。但是，参数对象没有什么用处，因为正如您所说，它预期每个调用的执行时间为O(log )，而标准要求分期为O(1)。可以使用另一种随机算法，它具有随机O(1)时间，我认为这是合格的；它还需要对参数执行O(n)个预处理步骤才能提取最大值。

别名方法在我看来是最优的，它需要更复杂的O(n)预处理步骤，但正如我前面所说的，对参数对象的构建成本没有要求。(计算的别名概率对象的大小也是O(n)；我使用的实现将n向上舍入为2的幂，因此其最坏情况下的大小小于32n字节。我还没有看过任何标准库实现。)

顺便说一句，别名方法不需要两个PRNG调用。用1来实现它是非常常见的:给定n个可能的结果，将PRNG的范围划分为n个离散的部分(这就是为什么我将n向上舍入为2的幂)；每个部分的阈值基于原始随机数。如果使用模运算符划分为离散的部分，则阈值与可能随机数的整个范围成比例；如果按范围划分，则阈值与盒子的大小成比例，并由盒子的原点偏移。无论哪种方式，都使用相同的随机数来选择一个框，然后选择两个别名中的一个，生成函数大致由以下部分组成：

auto r = prng();
size_t b = box_select(r);
return r > threshold[b] ? alias1[b] : alias2[b];

这不仅仅是摊销的O(1)；它是O(1)。所以它满足了所有的要求。