从非常大的一组值进行快速加权随机选择 [英] Fast weighted random selection from very large set of values

问题描述

我目前正在处理一个问题，需要从一个集合中随机选择一个元素。每个元素都有一个与它相关联的权重（选择概率）。

I'm currently working on a problem that requires the random selection of an element from a set. Each of the elements has a weight(selection probability) associated with it.

我的问题是对于少量元素的集合说5-10，复杂性运行时间）是可以接受的，但是随着元素数量的增加，例如1K或10K等，运行时间变得不可接受。

My problem is that for sets with a small number of elements say 5-10, the complexity (running time) of the solution I was is acceptable, however as the number of elements increases say for 1K or 10K etc, the running time becomes unacceptable.

我当前的策略是：

1. 使用范围[0,1）选择随机值X


2. 迭代元素直到总和大于X


3. 选择并返回造成总和超过X的元素

对于大集合和大量的选择，这个过程开始显示二次行为，总之是有更快的方式吗？一个更好的算法可能？

For large sets and a large number of selections this process begins to exhibit quadratic behavior, in short is there a faster way? a better algorithm perhaps?

推荐答案

假设元素权重是固定的，你可以使用预先计算的和。这类似于直接使用累积概率函数，而不是直接使用累积概率函数。

Assuming that the element weights are fixed, you can work with precomputed sums. This is like working with the cumulative probability function directly, rather than the density function.

然后可以将查找实现为二进制搜索，

The lookup can then be implemented as a binary search, and hence be log(N) in the number of elements.

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

A binary search obviously requires random_access to the container of the weights.

，请使用 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;
}

这篇关于从非常大的一组值进行快速加权随机选择的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！