algorithm - std::discrete_distribution 接口(interface)背后的原因

Question

根据 cppreference.com std::discrete_distribution接口(interface)需要库开发人员实现 probabilities()和 template<class Generator> result_type operator()(Generator& g, const param_type& params); .后者未记录在 cppreference.com 上，但根据 libc++ implementation它允许用户从给定权重序列的子序列中采样(并使用传递的生成器作为另一个生成器的熵源，但它现在不相关)。我读过 N3551 (关于 std::discrete_distribution 的唯一 googleable 提案)并且它没有为 std::discrete_distribution 提供这样一个接口(interface)的任何理由。 .

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

Answer 1

对于为给定随机分布构造参数对象的成本及其内部表示的性质没有要求。或其他任何东西。特别是，parameters 对象不必而且通常不会只是其构造参数的向量。构造参数对象必须执行任何必要的预计算/预处理，以使以后的分布生成高效。 (这不仅适用于 discrete_distribution。有许多分布的自然参数需要非平凡成本的预计算步骤。)

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

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

顺便说一句，别名方法不需要两次 PRNG 调用。用一个来实现它是很常见的:给定 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)。所以它满足所有要求。