O(1) 带移除的加权随机选择算法

Question

我正在寻找与 alias method 具有相似特征的加权随机选择算法，除非项目在选择后被删除。

例如，我有一个袋子可以生产:

• 70% 的时间是红色弹珠。
• 10% 的时间是绿色弹珠。
• 还有 20% 的时间是蓝色弹珠。

我对袋子进行了取样，得到了一个红色弹珠。红色现在被移除，所以我想袋子现在会产生:

• 33% 的时间是绿色弹珠。
• 66% 的时间是蓝色弹珠。

我相信您可以预先计算每个可能的概率表的树，这样样本仍然是 O(1)。有没有更聪明的算法来进行恒定时间加权的移除选择？

Answer 1

实际上，我好像看错了问题。我不知道别名方法，下面的答案不是类似的算法。我会在这里留下我的答案，因为它仍然提供信息。

---

我不知道 O(1) 算法，但在 log(N)² 搜索和 log(N) 更新中很容易做到。这可能会通过更具体的算法得到改进。

将你的元素放在 Fenwick tree 中，以它们的概率作为它们的值。此外，在更改元素时跟踪总累积概率。

现在我们可以做得比仅仅删除元素更好!我们可以任意改变item的概率，但是把一个item的概率设置为0就相当于去掉它。然后可以在 log(N) 中查询第 n 个元素的累积概率。这在逻辑上扩展到累积概率大于 p 的第一个元素的 log(N)² 二进制搜索。

现在，为了进行加权随机选择，我们生成一个介于 0 和 P 之间的数字 p，其中 P 是总累积概率。然后我们进行上述二分查找，找到并选择第一个累积概率大于p的元素。

---

我已经改进了上面的内容，因为使用 Fenwick 树很容易对累积概率大于或等于 p 的第一个元素进行 log(N) 搜索。我强烈建议阅读 this explanation of Fenwick trees .

简单地说，要找到该元素，请像在任何其他树上一样在 Fenwick 树上进行常规二分搜索，但要保留当前累积和(从 0 开始)。每当您在二分搜索中选择右手 child 时，将当前累积和增加当前节点的值。然后，当比较当前节点的值与我们正在寻找的累积总和时，在比较之前将当前节点的值添加到到目前为止的总和。