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

Question

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

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

我目前的策略是:

1. 选择范围为[0,1)的随机值X
2. 迭代元素求和它们的权重,直到总和大于X.
3. 选择并返回导致总和超过X的元素

对于大型集合和大量选择,此过程开始表现出二次行为,简而言之,是否有更快的方法？或许更好的算法？

Answer 1

您想使用Walker算法.对于N个元素,设置成本为O(N).但是,采样成本是O(1).看到

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

RandomLib的RandomSelect类 实现此算法.

Answer 2

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

然后,查找可以实现为二进制搜索,因此是元素数量的log(N).

二进制搜索显然需要random_access到权重的容器.

或者,使用a 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;
}