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

Question

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

假设一个角色有多个不同权重的决策。

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

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

有一些因素可以从池中删除和添加某些决策。这些权重不是固定的(例如，对于更智能的角色，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是执行此任务的算法列表。

Answer 2

在我查看了您输入的代码后，我认为技术/算法rejection sampling就是您要找的。要使用拒绝采样获得相同的代码输出，请执行以下操作：

var sample = []; 
for (let i = array.length - 1; i >= 0; i--) {
    for(let j = array[i].weight-1;j>=0;j--) {
        sample.push(i);
    }
}
// this function rolls a random number from 0 to sample.length-1
// which sample.length should be equivalent to your total weight 
let r = roll(0, sample.length-1);
return array[sample[r]];

上面的代码降低了时间复杂度，但增加了空间复杂度。

如果您尝试在没有rejection sampling的情况下在算法中实现binary search，请尝试以下代码：

let totalWeight = 0;
//add one property into your array, call it accumulative_weight or aw

for (let i = array.length - 1; i >= 0; i--) {
    totalWeight += array[i].weight;
    //assign the accumulative_weight property 
    array.aw = totalWeight;
}

// this function rolls a random number from 1 to totalWeight
let r = roll(1, totalWeight); 
let start = 0;
let end = array.length;
let position = "not found";
while(start!=end)
{
    let target = parseInt((end-start)/2);
    if( array[target].aw > r )
        end = target;
    else if ( array[target].aw - array[target].weight < r )
        start = target;
    else
    {
        let position = target;
        break; 
    }
}
return position;

请注意，必须对数组进行排序。希望能有所帮助。