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

问题描述 投票:0回答:1

我知道对于静态权重,推荐的方法是 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;
  }
}
javascript probability weighted
1个回答
0
投票

这可能是一种过早优化的情况。虽然 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)。

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

最新问题
© www.soinside.com 2019 - 2025. All rights reserved.