从非常大的一组值中快速加权随机选择

Question

我目前正在研究一个需要从集合中随机选择元素的问题。每个元素都有一个与其相关的权重(选择概率)。

我的问题是，对于具有少量元素(比如5-10 )的集合，解决方案的复杂性(运行时间)是可以接受的，但是随着元素数量的增加，比如1K或10K等，运行时间就变得不可接受了。

我目前的策略是：

1. 选择具有范围[0，1)
2. 迭代元素的随机值X，将它们的权重相加直到和大于X
3. ，选择导致和超过X的元素并返回

对于大的集合和大量的选择，这个过程开始表现出二次型行为，简而言之，有更快的方法吗？一个更好的算法？

Answer 1

假设元素权重是固定的，则可以使用预先计算的和。这就像直接处理累积概率函数，而不是密度函数。

然后，查找可以实现为二进制搜索，因此在元素数中是log(N)。

二进制搜索显然需要对权重容器进行random_access。

或者，使用std::map<>和upper_bound()方法。

#include <iostream>
#include <map>
#include <stdlib.h>

int main ()
{
  std::map<double, char> cumulative;
  typedef std::map<double, char>::iterator It;

  cumulative[.20]='a';
  cumulative[.30]='b';
  cumulative[.40]='c';
  cumulative[.80]='d';
  cumulative[1.00]='e';

  const int numTests = 10;
  for(int i = 0;
      i != numTests;
      ++i)
  {
      double linear = rand()*1.0/RAND_MAX;  
      std::cout << linear << "\t" << cumulative.upper_bound(linear)->second << std::endl;
  }

  return 0;
}

Answer 2

你想要使用Walker算法。对于N个元素，设置成本为O(N)。但采样成本为O(1)。看见

• A. J. Walker，一种生成离散随机变量和广义分布的有效方法，ACM TOMS 3,253-256 (1977).
• Knuth，TAOCP，Vol.2，Sec 3.4.1.A.

RandomSelect类a RandomLib实现了该算法。

Answer 3

如果您有足够快的方法来均匀地采样一个随机元素，您可以使用拒绝抽样；您所需要知道的就是最大权重。它的工作原理如下:假设最大权重M，在0,1中均匀选择一个数字X。反复采样元素，直到找到一个权重至少为M*X的元素；选择这个元素。

或者，近似解:随机选择100个元素，在这个集合中选择一个与权重成比例的元素。