动态权重 - 增加特定项目相对概率的有效方法

Question

我知道对于静态权重，推荐的方法是 Walker Alias 方法，因为它的采样复杂度为 O(1)。

但是我有一个情况，我需要能够临时动态调整特定项目的概率。

假设我有一张带有各自权重的键映射：

A = 5, B = 10, C = 15, D = 20

我正在尝试找出最有效的方法，将 A 发生的相对几率提高 20%，将 C 发生的相对几率提高 15%。 所以现在 A 和 C 的机会分别是 10% 和 30%。他们应该变成 12% 和 34.5%。

最明显的方法似乎是：

将更改应用于权重：

a = 5
c = 15
newA = a * 1.2 = 6
newC = c * 1.15 = 17.25
difference = (newA - a) + (newC - c) = (6 - 5) + (17.5 - 15) = 1 + 2.25 = 3.25

使用差异按比例减少其他权重（b 和 d），以确保 总重量保持不变：

b = 10
d = 20
bAndD = b + d = 30
newB = b - (b / bAndD) * difference = 10 - 1.083333333333333 = 8.916666666666667
newD = d - (d / bAndD) * difference = 20 - 2.166666666666667 = 17.83333333333333

所得重量：

a = 6
b = 8.916666666666667
c = 17.25
d = 17.83333333333333
totalWeight = remains 50

所以现在的机会是：

chanceA = 12% (20% increase)
chanceB = ~17.83% (~10.83% decrease)
chanceC = 34.5% (15% increase)
chanceD = ~35.66% (~10.83% decrease)

这很棒，而且非常理想，如果可能的话，我想将所有这些插入到一些有效的结构中。动态 Walker 别名或 Fenwick 树或线段树。在这种情况下，如果我理解正确的话，我可能不想每次需要临时调整机会时都更新每个权重。

是否有更好的替代方案，我可以只修改 A 和 C 权重？ 或者这是最好的方法？ 如果是，是否意味着所有有效的结构和树木都被排除在外，而我必须使用标准的“累积权重/权重总和”方法来选择条目？

const totalWeight = weights.reduce(
  (sum, weight) => sum + weight,
  0,
);
const randomWeight = Math.random() * totalWeight;
let cumulativeWeight = 0;
for (let index = 0; i < weights.length; index++) {
  cumulativeWeight += weights[index];
  if (randomWeight < cumulativeWeight) {
    return index;
  }
}

Answer 1

这可能是一种过早优化的情况。虽然 O(1) 很好，但 O(n) 甚至 O(n log n) 的扩展也相当好。 O(n^2) 和 O(n^n) 是麻烦制造者。但是，您不必超过 O(n) 复杂度。

Walker Alias 方法所需的表需要 O(n) 时间来生成，其中 n 是项目数。您有数百万或数十亿的物品吗？在达到数万亿或千万亿的项目之前，您可能不会看到任何性能问题。或者平台的功率非常低。

接下来，你需要多久临时调整一次特定物品的概率？如果每秒少于多次，您可能仍然不需要优化任何内容。

---

首先，我会尝试按照您在问题中所述调整权重。我认为这个操作最多需要 O(n) 时间。仅更改 A 和 C 的权重可能是可能的，但可能不会带来任何显着的性能提升（除非您有“很多”项目和/或不断更改权重）。即使您只是更改一项的权重，Walker alias 仍然必须预先计算整个表。 （我不确定是否会优化重用上一张表...） 然后将新权重插入您选择的算法中，例如 Walker Alias。我猜查找是更常用的操作，它仍然只需要 O(1) 常数时间。

即使每次查找都必须更新表，运行时间复杂度仍然最多为 O(n)。

如果新权重只是临时的，您可以缓存原始权重。