有很多典型的问题，例如https://softwareengineering.stackexchange.com/questions/150616/return-random-list-item-by-its-weight
想象一下更高级的问题。
您有N对(item_id, weight)信息来源。我们称它们为碎片。分片包含成对列表(item_id, weight)。
您有中央节点，我们称它为Central。
问题是：在Central上，要根据它们在所有权重中的权重，从“大列表”（该列表实际上是所有分片上的所有列表实际上合并而成）中选择一个随机项目。
例如，我们有两个分片：
+-------+---------+--------+ | 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 2/19，-4 /19，-2 /19等概率进行选择3。
第二个问题：
如何对所有分片中的所有项目进行随机排列，但对所有分片进行加权？
即理想的范围是：（1, 4, 2, 3, 5根据其重量），
但可能还有另一个范围，例如1, 2, 4, 3, 5，但频率比以前少一些，
...
最坏的情况5, 3, 2, 4, 1也可能出现，但是可能性很小。
为此，在计算机科学中是否存在普遍的问题？
我认为您的两个问题是独立的，应该是单独的问题。另外，我不确定我是否正确理解它们。但是，我们开始：
如果您对分片的引用与在多个网络主机上分布物料存储并尝试执行某种网络并行随机选择有关，那么您可以使用我在此答案结尾处概述的修改后的存储库样本算法。
该算法最初是为在冗余网络中使用而开发的，在冗余网络中，各种存储主机不一定可以直接从中央主机访问，并且连通性是图形而不是树。在这种情况下，您需要能够处理不响应的主机（这将偏向单个查询，但是如果网络故障很少且随机，则希望不会偏向一连串的查询）。还必须处理两次查询主机的可能性。在概述的算法中，我仅假设假设某个查询到达主机，则该响应很可能会返回到查询主机，从而忽略了第二个查询和后续查询。这可能是完全错误的，但是它使问题变得更加容易，并且再次由于足够多的查询而没有偏见。
如果没有复杂性，如果中央主机可以可靠地连接到每个存储主机，则该算法是简单明了的。中央主机并行查询所有存储主机，每个存储主机返回其存储的对象的总权重的元组，以及根据这些权重随机选择的一个对象。（它使用一些标准的加权随机选择算法来执行此操作。使用哪种算法将取决于对象和权重的更改频率。）
中央主机维护两个变量：total，已响应的服务器的权重之和（最初为0），以及candidate可能返回的随机对象（最初是一些指示“无对象”的标记）。
它一次以任何顺序（例如接收顺序）处理一个响应。对于每个响应<weight, object>，它执行以下操作：
total← total+weightr ←范围内的随机整数 [0, total)r< weight：candidate←object当确定所有远程服务器均已响应时，它返回candidate。
（至少，我认为您是在要求加权随机洗牌）。
我建议使用权重修改的标准Fisher-Yates算法，我认为它将产生您期望的采样行为。为此，请以任意顺序从对象开始，然后i从from1到to的每个值n：
j从对象开始i，从中选择一个（加权）随机元素的索引，然后交换对象i和j。为此，您需要维护连续较小的后缀的CDF，这可以通过将对象保留在二叉树中的方式在O（log N）中进行。（或者，如果N小，您可以在O（N）中更简单地执行此操作。）
但是，我在点击Post按钮之前对SO进行了快速搜索，并得出结论，这个绝妙的答案实际上更好，因为它无需任何复杂的数据结构即可达到O（N log N）：对于每个对象，您都会从中生成一个随机数速率为相应权重的指数分布。然后根据这些随机数对对象进行排序，结果是随机混洗。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句