algorithm - 按重量返回随机元素，高级

Question

像https://softwareengineering.stackexchange.com/questions/150616/return-random-list-item-by-its-weight这样的典型问题很多

想象更高级的问题。

你有 N 对 (item_id, weight) 信息来源。我们称它们为碎片。分片包含成对列表 (item_id, weight)。

你有一个中心节点，我们称它为Central。

问题是:在 Central 上，根据所有权重的权重，从 The Big List(该列表实际上是从所有分片上的所有列表中合并而成的列表)中随机选择项目。

例如，我们有两个分片:


+--------+----------+--------+
|分片 |项目编号 |重量 |
+--------+----------+--------+
| 1 | 1 | 7 |
| 1 | 2 | 4 |
| 1 | 3 | 2 |
| 2 | 4 | 5 |
| 2 | 5 | 1 |
+--------+----------+--------+


(让 item_id 在所有分片中都是唯一的。)

第一个问题:

如何随机选择 item_id 但对所有分片进行加权？IE。 total_weight == 7+4+2+5+1 == 19，所以 1 将以 7/19 的概率被选中，2 - 4/19，3 - 2/19 等等。

第二个问题:

如何随机排列所有分片中的所有项目，但通过所有分片加权？

即理想的范围是:1, 4, 2, 3, 5(根据它们的权重)，

但可能还有另一个范围，如 1, 2, 4, 3, 5，但频率比以前略低，

...

最坏情况 5, 3, 2, 4, 1 也可能出现，但概率非常小。

这在计算机科学中是否存在常见问题？

Answer 1

我认为您的两个问题是独立的，应该是单独的问题。我也不确定我是否正确理解了它们。但我们开始吧:

分片加权随机查询

如果您对分片的引用与在多个网络主机上分发项目存储并尝试进行某种网络并行随机选择有关，那么您可以使用修改后的 reservoir sample我在 this answer 末尾概述的算法.

该算法最初是为在冗余网络中使用而开发的，在该网络中，不一定可以从中央主机直接访问各种存储主机，并且连接是图形而不是树。在这种情况下，您需要能够处理不响应的主机(这将偏向于单个查询，但如果网络故障不常见且随机，则希望不会偏向一长串查询)。还需要处理主机被查询两次的可能性；在概述的算法中，我假设如果查询到达主机，则响应很可能返回到查询主机，因此我简单地忽略了第二个和后续查询。这可能是完全错误的，但它使问题变得容易得多，而且它可能在足够多的查询中没有偏见。

没有复杂性，如果中央主机可以可靠地连接到每个存储主机，算法就很简单了。中央主机并行查询所有存储主机，每个存储主机返回其存储的对象总权重的元组，并根据这些权重随机选择一个对象。 (它使用一些标准的加权随机选择算法来做到这一点。使用哪种算法将取决于对象和权重变化的频率。)

中央主机维护两个变量:total ，已响应的服务器的权重总和(最初为 0)，以及 candidate ，一个可能返回的随机对象(最初是一些指示“没有对象”的标记)。

它以任何顺序一次处理一个响应(例如它收到响应的顺序)。对于每个响应 <weight, object> ，它执行以下操作:

• total ← total + weight
• r ← [0, total) 范围内的随机整数
• 如果r < weight : candidate ← object

当它确定所有远程服务器都已响应时，它返回 candidate .

加权随机洗牌

(至少，我认为您要求的是加权随机洗牌)。

我打算建议使用标准 Fisher-Yates algorithm用权重修改，我认为这会产生您期望的采样行为。为此，您可以按任意顺序从对象开始，然后是 i 的每个值。来自 1至 n :

• 选择j ，从 i 开始的对象中的(加权)随机元素的索引, 并交换对象 i和 j .

为此，您需要维护连续较小的后缀的 CDF，您可以通过将对象保存在二叉树中来在 O(log N) 中完成此操作。 (或者如果 N 很小，您可以在 O(N) 中更简单地完成。)

但是，在点击“发布”按钮之前，我对 SO 进行了快速搜索，得出的结论是这个 brilliant answer实际上更好，因为它实现了 O(N log N) 而无需任何复杂的数据结构:对于每个对象，您从指数分布中生成一个随机数，其速率是相应的权重。然后根据这些随机数对对象进行排序，结果就是随机洗牌。