javascript - 什么是计算加权和的有效算法？

Question

我不确定这里的技术术语是什么，所以我将不胜感激。

假设一个 Angular 色有多个不同权重的决定。

Decision A: 1
Decision B: 3
Decision C: 5
Sum: 9

代码所做的是将它们相加，这样就有 1/9 的几率做出决定 A，3/9 做出决定 B，5/9 做出决定 C。

有一些因素可以从池中删除和添加某些决定。这些权重不是固定的(例如，对于更聪明的 Angular 色，B 可能为 2，或者根据各自的权重拆分为 B1 和 B2)。

现在我正在做的只是像下面这样的线性搜索(在 JavaScript 中):

let totalWeight = 0;
for (let i = array.length - 1; i >= 0; i--) {
    totalWeight += array[i].weight;
}

// this function rolls a random number from 1 to totalWeight
let r = roll(1, totalWeight); 
let search = 1;
for (let i = 0; i < array.length; i++) {
    let w = array[i].weight;
    if (r >= search && r < (search+w)){
        return array[i];
    }
    search += w;
}

但这似乎不是很有效。看起来这里可以有二进制搜索算法，但我似乎想不出一个。有什么想法吗？

Answer 1

如果权重每一轮都在变化，并且不同轮次之间既没有共性也没有不变性，我认为没有一种算法可以显着优于线性扫描。

Here是执行此任务的算法列表。