按重量、先进水平返回随机项目

Question

有许多典型的问题，如返回随机list它的项目weight

想象一下更高级的问题。

您有N个对(item_id, weight)信息来源。我们叫他们碎片吧。碎片包含对的列表，(item_id, weight)。

你有中心节点，我们称之为中央节点。

问题是:在中央，从大列表中随机选择项目(该列表实际上与所有碎片上的所有列表合并)，根据它们的权重通过所有权重选择。

例如，我们有两个碎片：

+-------+---------+--------+
| shard | item_id | weight |
+-------+---------+--------+
|   1   |     1   |    7   |
|   1   |     2   |    4   |
|   1   |     3   |    2   |
|   2   |     4   |    5   |
|   2   |     5   |    1   |
+-------+---------+--------+

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

第一个问题：

如何随机选择item_id，但在所有的碎片中加权？即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

在问题1中，您不使用分割某个项所属的信息。这实际上是随机选择一个带有权重的项目。您可以在链接到的帖子中使用该方法。

对于问题2，我认为您可以反复应用问题1。首先您选择第一个项目，然后重新计算您的列表和权重。这可以巧妙地完成，例如，减去您首先从总权重中选择的项的权重。然后重复第二项.

更具体地说，假设您只应用了问题1一次，并且它随机地选择了4。然后您将再次将问题1应用于：

+---------+--------+

| item_id | weight |

+---------+--------+

|     1   |    7   |

|     2   |    4   |

|     3   |    2   |

|     5   |    1   |

+---------+--------+