理解加权随机算法

想象一下，你有一组物品，每件物品都有不同的“权重”，或者说被选中的概率。加权随机算法是一种根据物品权重从这组物品中选择物品的方法，本质上就是赋予权重较高的物品更大的被选中概率。在本文中，我将探讨这种算法的工作原理。

应用

加权随机算法可应用于计算机科学和数据处理领域。以下列举一些常见应用场景：

• 随机选择：使用此算法选择具有不同概率的项目，例如选择要在在线广告中显示的广告，其中点击率不同的广告权重也不同。

• 游戏开发：在游戏中，你可以应用此算法来创建随机事件或为不同的结果分配概率，例如角色/物品掉落或敌人行为。

• 负载均衡：在负载均衡场景中，当需要将请求分配到多个服务器时，可以使用加权随机选择，根据不同服务器的容量或性能，将更多或更少的请求分配给它们。

• 推荐系统：推荐引擎采用加权随机算法，根据用户偏好和内容相关性对内容进行优先级排序和呈现。
  内容变体的相关性得分越高，其向用户展示的次数就越多。

概念

为了理解加权随机算法，我们可以将其想象成一个空间，其中每个区域代表一个元素的权重。这个空间类似于一条线，线上每段的长度都对应着一个元素的权重。如果你向这个空间中扔一块石头，石头落在特定区域的概率与该区域的长度成正比，而与区域的顺序无关。

加权随机算法的实现

function randomByWeight(values: string[], weights: number[]): string {
  let total = 0

  // Sum total of weights
  weights.forEach(weight => {
    total += weight
  })

  // Random a number between [1, total]
  const random = Math.random() * total // [0,total]

  // Seek cursor to find which area the random is in
  let cursor = 0
  for (let i = 0; i < weights.length; i++) {
    cursor += weights[i]
    if (cursor >= random) {
      return values[i]
    }
  }
  return "never go here"
}

解释该算法

1. 计算总重量

加权随机算法的第一步是确定总权重。这可以通过将集合中所有元素的权重相加来实现。在我们的例子中，总权重为 20 + 30 + 50 = 100。

let total = 0

weights.forEach(weight => {
  total += weight
})

2. 生成随机数

接下来，我们生成一个介于 1 到总重量之间的随机数([1,total])。这个随机数就是我们的“光标”，它决定了石头在我们空间中的落点。

const random = Math.ceil(Math.random() * total) // [1,total]

3. 走过这个空间

然后，我们遍历这个空间，将光标从左向右移动，每次移动的步长都乘以一个元素的权重。目标是当光标的移动步长超过或等于之前生成的随机数时停止。

let cursor = 0
for (let i = 0; i < weights.length; i++) {
    cursor += weights[i]
    if (cursor >= random) {
      return values[i]
    }
}

简单解释

这Weighted random algorithm可以比作一个，space其中每个都area对应于weight of an element。

该算法的实现包括在该空间内选择一个随机点，并确定该点所在的具体区域。