java - 有没有更快的方法来搜索累积分布？

Question

我有一个 List<Double>包含对项目进行抽样的概率(权重)。例如，List包含 5 个值，如下所示。

0.1, 0.4, 0.2, 0.1, 0.2

每个第 i 个 Double value 是对另一个 List<Object> 的第 i 个项目进行采样的概率.

我如何构建一个算法来根据这些概率执行抽样？

我尝试过类似的方法，首先将概率列表制成累积形式。

0.1, 0.5, 0.7, 0.8, 1.0

那么我的做法如下。我生成一个随机 double ，并遍历列表以找到大于随机 double 的第一个项目，然后返回它的索引。

Random r = new Random();
double p = r.nextDouble();
int total = list.size();
for(int i=0; i < total; i++) {
 double d = list.get(i);
 if(d > p) {
  return i;
 }
}
return total-1;

这种方法很慢，因为我是按顺序爬行列表的。实际上，我的列表包含 800,000 个与我需要从中抽样的权重(概率)相关的项目。因此，不用说，这种顺序方法很慢。

我不确定二分查找有何帮助。假设我生成了 p = 0.01。然后，二进制搜索可以对列表使用递归，如下所示。

compare 0.01 to 0.7, repeat with L = 0.1, 0.5compare 0.01 to 0.1, stop compare 0.01 to 0.5, stop

0.01比0.7、0.5、0.1都小，但我明明只想要0.1。所以在使用二进制搜索时，停止标准对我来说仍然不清楚。

如果有一个图书馆可以帮助处理这类事情，我也会感兴趣。

Answer 1

以下是使用二分查找的方法，从累积概率开始:

public static void main (String[] args) {
    double[] cdf = {0.1, 0.5, 0.7, 0.8, 1.0};
    double random = 0.75;  // generate randomly between zero and one
    int el = Arrays.binarySearch(cdf, random);
    if (el < 0) {
        el = -(el + 1);
    }
    System.out.println(el);
}

附言当概率列表很短时，简单的线性扫描可能与二分查找一样有效。