根据权重分布从列表中随机选择 N 个项目的最快算法是什么？

Question

我有一个很大的项目清单，每个项目都有一个重量。

我想随机选择N个项目而不替换，而重量越大的项目更有可能被选中。

我正在寻找最有效的想法。性能是最重要的。有任何想法吗？

Answer 1

如果您想在不更换的情况下对物品进行抽样，您有很多选择。

• 使用加权选择替换算法来选择随机索引。有很多这样的算法。其中一个是WeightedChoice，在本答案后面进行描述，另一个是拒绝采样，描述如下。假设权重最高，max并且存在n权重。要n使用拒绝采样在 [0, ) 中选择一个索引：

  1. i在 [0, n) 中选择一个统一的随机整数。
  2. 以概率weights[i]/max，返回i。否则，转到步骤 1。

  每次加权选择算法选择一个索引时，将所选索引的权重设置为 0 以防止它再次被选择。或者...

• 为每个索引分配一个指数分布的随机数（比率等于该索引的权重），制作一个对列表，将每个数字分配给一个索引，然后按这些数字对该列表进行排序。然后按升序从头到尾取每个项目。这种排序可以使用优先队列数据结构（一种导致加权水库采样的技术）在线完成。请注意，生成随机数 的朴素方法-ln(1-RNDU01())/weight，其中RNDU01()是 中的均匀随机数[0, 1]，但并不可靠（“非均匀分布索引”，“指数分布”下）。

• Tim Vieira在他的博客中提供了其他选项。

• 甲纸张通过的Bram范·德克伦德特各种算法进行比较。

编辑（8 月 19 日）：请注意，对于这些解决方案，权重表示给定项目首先出现在样本中的可能性。此权重不一定是给定的n 个项目样本将包含该项目的机会（即包含概率）。上面给出的方法不一定能确保给定的项目会以与其权重成正比的概率出现在随机样本中；为此，请参阅“具有相等或不等概率的采样算法”。

假设您想随机选择项目并替换，这里是实现这种选择的伪代码。给定一个权重列表，它返回一个随机索引（从 0 开始），选择的概率与其权重成正比。该算法是实现加权选择的直接方法。但如果它对您来说太慢，请参阅我的部分“带替换的加权选择”以了解其他算法。

METHOD WChoose(weights, value)
    // Choose the index according to the given value
    lastItem = size(weights) - 1
    runningValue = 0
    for i in 0...size(weights) - 1
       if weights[i] > 0
          newValue = runningValue + weights[i]
          lastItem = i
          // NOTE: Includes start, excludes end
          if value < newValue: break
          runningValue = newValue
       end
    end
    // If we didn't break above, this is a last
    // resort (might happen because rounding
    // error happened somehow)
    return lastItem
END METHOD

METHOD WeightedChoice(weights)
    return WChoose(weights, RNDINTEXC(Sum(weights)))
END METHOD