javascript - 用于从每个条目具有不同权重的数组中选择项目的高效 javascript 算法

Question

基本上我在java脚本中有一个二维数组，以对象的形式，概率:

A,10 B,50 C,20 D,20

其中数字是从 100 个项目中选择的概率。

按照指定概率随机选择项目的最有效算法是什么？

(目前我从 1-100 中获得一个随机数，并根据前面各项的总和选择一项，因此 5 将获得 A、40 B、65 C 等)

谢谢!

中号

Answer 1

我们假设您的输入是在表单中

var probs = [['A' ,10], ['B', 50], ['C', 20], ['D', 20]];

计算累积概率:

var cur = 0;
var cumulative = probs.map(elt => cur += elt[1]);

这将创建一个数组

[10, 60, 80, 100]

编写一个函数来查找哪个元素对应于特定概率:

function get_element(prob) {
  for (var i = 0; i < cumulative.length; i++) {
    if (prob <= cumulative[i]) return i;
  }
}

现在就写

probs[get_element(Math.random() * 100)] [0]