python - 加权随机选择，有无替换

最近，我需要从列表中对元素进行加权随机选择，无论是否替换。尽管有众所周知的，很好的非加权选择算法，还有一些不替换的加权选择算法(例如对resevoir算法的修改)，但我找不到用于替换加权选择的任何好的算法。我还想避免使用resevoir方法，因为我选择了列表的很大一部分，该列表足够小以容纳在内存中。

在这种情况下，有人对最佳方法有什么建议吗？我有自己的解决方案，但我希望找到更有效，更简单的方法，或兼而有之。

最佳答案

别名方法是从不变的 list 中提取大量替代 sample 的最快方法之一。核心直觉是，我们可以为加权列表创建一组大小相等的bin，可以通过位操作非常有效地建立索引，从而避免了二进制搜索。事实证明，正确完成后，我们只需要在每个bin中存储原始列表中的两个项目，因此可以用一个百分比表示拆分。

让我们以五个相等加权的选项(a:1, b:1, c:1, d:1, e:1)为例

要创建别名查找:

对权重进行归一化，以使其总和为1.0。 (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2)这是选择每个权重的概率。

找到大于或等于变量数量的最小2的幂，并创建此数量的分区|p|。每个分区代表1/|p|的概率质量。在这种情况下，我们创建8分区，每个分区都可以包含0.125。

取重量最小的变量，并将其尽可能多的质量放置在一个空分区中。在此示例中，我们看到a填充了第一个分区。带(p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8)的(a:0.075, b:0.2 c:0.2 d:0.2 e:0.2)

如果未填充分区，请获取权重最大的变量，然后使用该变量填充分区。

重复步骤3和4，直到没有原始分区的权重需要分配给列表。

例如，如果我们运行3和4的另一个迭代，我们将看到

剩下的(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8)的(a:0, b:0.15 c:0.2 d:0.2 e:0.2)
在运行时:

获取一个U(0,1)随机数，例如二进制0.001100000

将其移位lg2(p)，找到索引分区。因此，我们将其移位3，产生001.1或位置1，从而分区2。

如果分割了分区，则使用移位后的随机数的小数部分确定分割。在这种情况下，该值为0.5和0.5 < 0.6，因此返回a。

Here is some code and another explanation，但不幸的是它没有使用移位技术，也没有实际验证过它。

关于python - 加权随机选择，有无替换，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/352670/