C++ 具有权重的随机非重复整数

Question

我想有效地生成一个(封闭)范围内的唯一(非重复)整数的随机样本 [0, rnd_max]，范围内的每个数字都可以选择，并且每个都与样本权重相关联(权重越大，选择该数字的可能性就越大，下一个被选择的概率恰好是 weight[i]/sum(weight[not_taken])如果它还没有被纳入样本)。

我看到 C++ 有 std::discrete_distribution 可以生成随机加权整数，但是如果我用它来生成随机整数并丢弃重复的整数，当要获取的样本相对于长度来说很大时在可能的范围内，将会有很多已经采集的失败样本，导致程序效率极低。我不清楚 Floyd 算法是否对样本权重 (https://math.stackexchange.com/questions/178690/whats-the-proof-of-correctness-for-robert-floyds-algorithm-for-selecting-a-sin) 的情况有一些扩展 - 我个人想不出一个。

也可以例如使用 std::discrete_distribution 将权重降为零，或执行部分加权洗牌，如以下答案:C++. Weighted std::shuffle - 但在该答案中，std::discrete_distribution 在每次迭代时重新生成，因此运行时间变为二次方(它需要循环遍历每次传递给它的权重)。

想知道 C++ 中唯一整数的有效加权随机样本是什么，它适用于不同的样本大小(例如，可用范围内的样本数的 1% 到 90%)。

#include <vector>
#include <random>
#include <algorithm>

int main()
{
    size_t rnd_max = 1e5;
    size_t ntake = 1e3;

    unsigned int seed = 12345;
    std::mt19937 rng(seed);
    std::gamma_distribution<double> rgamma(1.0, 1.0);
    std::vector<double> weights(rnd_max);
    for (double &w : weights) w = rgamma(rng);

    std::vector<int> chosen_sample(ntake);
    // sampler goes here...

    return 0;
}

Answer 1

使用扩充二叉搜索树可以很好地解决这个问题。它给出了一个时间复杂度为 O(k log n) 的随机采样 k 个元素的算法。

思路是这样的。假设您将所有元素按排序顺序存储在一个数组中，每个元素都标有其权重。然后，您可以按如下方式(低效地)解决此问题:

1. 生成一个介于 0 和所有元素的总权重之间的随机数。
2. 遍历数组，直到找到一个元素，使得随机数在该元素跨越的“范围”内。此处，“范围”表示从该元素开始到下一个元素开始的权重窗口。
3. 删除该元素并重复。

如果你按上面提到的方式实现它，每次选择一个随机元素的过程都将花费 O(n) 的时间:你必须遍历数组的所有元素，然后在你选择它之后从某处删除一个元素.那不是很好；整体运行时间为 O(kn)。

我们可以通过以下方式稍微改进这个想法。当存储数组中的所有元素时，让每个元素都存储其实际权重和所有在它之前的元素的组合权重。现在，要找到您要采样的元素，您不需要使用线性搜索。您可以改为对数组使用 二分搜索 以在时间 O(log n) 中定位您的元素。但是，这种方法的总体运行时间仍然是每次迭代的 O(n)，因为这是删除您选择的元素的成本，所以我们仍然处于 O(kn) 范围内。

但是，如果您不将元素存储在排序的数组中，其中每个元素存储它之前的所有元素的权重，而是在平衡二分查找中树，其中每个元素存储其左子树中所有元素的权重，您可以模拟上述算法(二分搜索被替换为遍历树)。此外，这样做的好处是可以在 O(log n) 时间内从树中删除一个元素，因为它是一个平衡的 BST。

(如果您好奇如何通过遍历找到您想要的元素，请快速搜索“order statistics tree”。这里的想法本质上是这个想法的概括。)

按照@dyukha 的建议，您可以通过在时间为 O(n) 的项目中构建一个完美平衡的树来获得每个操作的 O(log n) 时间(实际上不必为此对项目进行排序工作的技术 - 你知道为什么吗？)，然后每次你需要删除一些东西时使用标准的树删除算法。这给出了 O(k log n) 的整体解决方案运行时间。