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

Question

我有一个很大的项目 list ，每个项目都有一个重量。
我想随机选择N个项目而不替换，而重量越大的项目更有可能被选中。
我正在寻找最有效的想法。性能是最重要的。有任何想法吗？

Answer 1

如果您想 sample items without replacement ，你有很多选择。

使用加权选择替换算法来选择随机索引。有many algorithms like this .其中之一是WeightedChoice ，在这个答案后面描述，另一个是拒绝采样，描述如下。假设最高权重是max还有n重量。在 [0, n 中选择一个索引) 使用拒绝抽样:

选择一个统一的随机整数 i在 [0, n )。

概率weights[i]/max , 返回 i .否则，转到步骤 1。

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

为每个索引分配一个指数分布的随机数(比率等于该索引的权重)，制作一个对列表，将每个数字分配给一个索引，然后按这些数字对该列表进行排序。然后按升序从头到尾取每个项目。这种排序可以使用优先队列数据结构(一种导致 weighted reservoir sampling 的技术)在线完成。请注意生成随机数的简单方法，-ln(1-RNDU01())/weight ，其中 RNDU01()是 [0, 1] 中的均匀随机数, 然而并不稳健(“Index of Non-Uniform Distributions ”，在“指数分布”下)。

蒂姆·维埃拉 (Tim Vieira) 给 additional options在他的博客中。

paper Bram van de Klundert 比较了各种算法。

编辑(8 月 19 日):请注意，对于这些解决方案，权重表示给定项目首先出现在样本中的可能性。此权重不一定是给定的 n 个项目样本将包含该项目的机会(即包含概率)。上面给出的方法不一定能确保给定的项目会以与其权重成正比的概率出现在随机样本中；为此，请参见“ Algorithms of sampling with equal or unequal probabilities”。

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

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