我想在(封闭的)范围[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;
}
最佳答案
有一种使用增强型二叉搜索树解决此问题的好方法。它给出了O(k log n)-时间算法，用于随机采样k个元素。
这个想法是这样的。假设您将所有元素按排序顺序存储在数组中，并且每个元素都标有其权重。然后，您可以按如下方式(有效地)解决此问题:
如果您如上所述实现此方法，则选择随机元素的每个过程都将花费时间O(n):您必须遍历数组的所有元素，然后在选择某个元素后将其删除。那不是很好；总体运行时间为O(kn)。
我们可以通过以下方式稍微改进一下这个想法。将所有元素存储在数组中时，请让每个元素同时存储其实际权重和之前所有元素的合并权重。现在，无需查找要采样的元素，就无需使用线性搜索。您可以改为在数组上使用二进制搜索在时间O(log n)中定位元素。但是，此方法的总运行时间每次迭代仍为O(n)，因为这是删除您选择的元素的成本，因此我们仍处于O(kn)范围内。
但是，如果不将元素存储在排序数组中(每个元素存储所有元素的权重)，而是存储在平衡的二进制搜索树中，其中每个元素将所有元素的权重存储在其左子树中，则可以模拟上述内容算法(二进制搜索被遍历树所取代)。而且，这样做的好处是，由于它是平衡的BST，因此可以在时间O(log n)中从树中删除元素。
(如果您好奇如何步行查找所需的元素，请快速搜索“order statistics tree”。这里的想法本质上是该想法的概括。)
遵循@dyukha的建议，您可以通过从时间O(n)的项目中构建一个完美平衡的树来获得每次操作的O(log n)时间(实际上，该项目无需排序即可使用该技术) -您知道为什么吗？)，然后在每次需要删除某些内容时使用标准的树删除算法。这给出了整体解决方案运行时间为O(k log n)。