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

Question

有许多典型的问题，如https://softwareengineering.stackexchange.com/questions/150616/return-random-list-item-by-its-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在所有碎片中都是唯一的。)

First problem：

如何随机选择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

我认为你的两个问题是独立的，应该是单独的问题。而且，我也不确定我是否正确地理解了它们。但现在我们开始：

共享加权随机查询

如果您对切分的引用与在多个网络主机上分发项目存储并尝试执行某种网络并行随机选择有关，那么您可以使用我在这个答案末尾概述的修改后的这个答案算法。

该算法最初是为了在冗余网络中使用而开发的，在冗余网络中，各种存储主机不一定可以直接从中央主机到达，并且连接性是一个图，而不是树。在这种情况下，您需要能够处理没有响应的主机(这会使单个查询产生偏差，但如果网络故障不频繁，并且希望随机不会偏袒一系列查询)。还需要处理一个主机被查询两次的可能性；在概述的算法中，我只是忽略第二个和随后的查询，前提是如果一个查询到达一个主机，那么响应可能会返回到查询主机。这可能是完全错误的，但它使问题变得容易得多，而且它可能对足够多的查询没有偏见。

在没有复杂情况下，如果中央主机能够可靠地连接到每个存储主机，则该算法是直接向前的。中央主机并行查询所有存储主机，每个存储主机返回其存储的对象的总权重的元组，并根据这些权重随机选择一个对象。(它使用一些标准的加权随机选择算法来实现。使用哪种算法将取决于对象和权重变化的频率。)

中央主机维护两个变量：total (响应服务器的权重之和(最初为0) )和candidate (可能返回的随机对象)(最初是表示“无对象”的哨兵)。

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

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

当它决定所有远程服务器都已响应时，它将返回candidate。

加权随机混叠

(至少，我认为你是在要求一次加权随机洗牌)。

我打算建议使用带有权重的标准Fisher-Yates算法，我认为这将产生您期望的抽样行为。为此，您可以从任意顺序的对象开始，然后对i的每个值(从1到n )进行处理。

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

为此，您需要维护连续较小后缀的CDF，通过将对象保存在二叉树中，可以在O(log )中这样做。(或者你可以在O(N)中做得更简单，如果N是小的。)

然而，在点击Post按钮之前，我对此进行了快速搜索，并得出结论，这个精彩的回答实际上更好，因为它实现了O( whose )，没有任何复杂的数据结构:对于每个对象，您从指数分布生成一个随机数，其速率是相应的权重。然后根据这些随机数对对象进行排序，结果是随机的洗牌。

Answer 2

对于您的第一个问题，您可以执行以下操作

// Your pairs (item_id, weight).
ArrayList<Pair> theBigList;
// The total weight of your data. Get it updated.
int totalWeight;

public int weightedSearch() {
    // Local copy of the value.
    int total = totalWeight;
    Random r = new Random();
    // Random integer in the interval [1 - total]
    int random = r.nextInt(total) + 1;
    for (int i = 0; true; i++) {
        if (theBigList.get(i).weigth < total)
            total -= theBigList.get(i).weigth;
        else
            return theBigLits.get(i).itemId;
    }
}

随机搜索，但加权，是由随机整数生成。在您的示例中，如果random介于1到7之间(7/19 prob.)，则将返回第一个元素；如果它在8至11之间(4/19 prob.)，则返回第二个元素，等等。

提示:在开始时获取您的重物，所以您有更大的可能性返回更快的加权搜索(您的循环结束之前)。