c++ - 从非常大的值集中快速加权随机选择

Question

我目前正在处理一个需要从集合中随机选择一个元素的问题。每个元素都有一个与之相关的权重(选择概率)。

我的问题是，对于元素数量较少的集合，比如 5-10，我所接受的解决方案的复杂性(运行时间)是可以接受的，但是随着元素数量的增加，比如 1K 或 10K 等，运行时间变得 Not Acceptable 。

我目前的策略是:

1. 选择范围为 [0,1) 的随机值 X
2. 迭代元素，对它们的权重求和，直到总和大于 X
3. 选择并返回导致总和超过 X 的元素

对于大集合和大量选择，这个过程开始表现出二次行为，简而言之，有没有更快的方法？也许是更好的算法？

Answer 1

您想使用 Walker 算法。有N个元素，就有一个设置O(N) 的成本。但是，采样成本为 O(1)。见

• A. J. Walker，一种有效的生成方法离散随机变量和一般分布，ACM TOMS 3, 253-256(1977 年)。
• Knuth，TAOCP，第 2 卷，第 3.4.1.A 节。

a RandomLib 的 RandomSelect 类实现了这个算法。