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

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

我的问题是，对于元素数量较少的集合(例如5-10)，解决方案I的复杂度(运行时间)是可以接受的，但是随着元素数量的增加(例如1K或10K等)，运行时间变得 Not Acceptable 。

我目前的策略是:

选择范围为[0,1)的随机值X

迭代元素的权重，直到总和大于X

选择导致总和超过X的元素并返回

对于大集合和大量选择，此过程开始表现出二次行为，总之有更快的方法吗？更好的算法？

最佳答案

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

然后可以将查找实现为二进制搜索，因此查找数量为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;
}