我想高效地生成一个随机的，（封闭的）范围内唯一（非重复）整数的样本，[0, rnd_max]该范围内的每个数字都可以选择，并且每个样本均与样本权重相关（权重越大，越可能应该是选择了这个数字，weight[i] / sum(weight[not_taken])如果样本中还没有被选择的话，那么接下来就应该精确选择该数字）。
我看到C ++ std::discrete_distribution可以生成随机加权整数，但是如果我使用C ++ 生成随机加权整数并丢弃重复的整数，则当所取样本相对于可能范围的长度而言较大时，将会有很多失败的样本已经被采用，导致程序效率极低。我不清楚弗洛伊德（Floyd）的算法是否对样本权重的情况进行了扩展（https://math.stackexchange.com/questions/178690/whats-the-proof-of-correctness-for-robert-floyds-algorithm-选择一个罪）-我个人无法想到一个。
例如，也可以使用std::discrete_distribution将权重降低到零，或执行部分加权随机播放，例如此答案：C ++。加权的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）中从树中删除元素。
（如果您好奇如何步行查找所需的元素，请快速搜索“ 订单统计树 ”。此处的想法本质上是该想法的概括。）
遵循@dyukha的建议，您可以通过根据时间O（n）的项目构建一个完美平衡的树来获得每次操作的O（log n）时间（实际上，该项目无需排序即可使用此技术） -您知道为什么吗？），然后在每次需要删除某些内容时使用标准的树删除算法。这给出了整体解决方案运行时间为O（k log n）。