跳至主要內容

加权随机

linwu大约 4 分钟

加权随机

Weighted Random
Weighted Random

什么是"加权随机"

假设你有一个项目列表。项目可以是任何东西。例如,我们可能有一个喜欢吃的水果和蔬菜列表:[ '🍌', '🍎', '🥕' ]

权重列表表示每个项目的权重(或概率、重要性)。权重是数字。例如,权重列表 [3, 7, 1] 可以表示:

  • 你更喜欢吃🍎苹果7次中的3次+7次+1次中的11次),
  • 然后你不太喜欢吃香蕉🍌(只有11次中的3次),
  • 而你真的不喜欢胡萝卜🥕(只想吃11次中的1次)。

如果我们以概率为基础来讲,那么权重列表可能是一个总和为1的浮点数数组(例如[0.1, 0.5, 0.2, 0.2])。

加权随机是一个函数,它会根据每个项目的权重随机返回列表中的一个项目,使得权重较大的项目更容易被选中。

函数的示例接口:

const items =   [ '🍌', '🍎', '🥕' ];
const weights = [  3,    7,    1  ];

function weightedRandom(items, weights) {
  // 实现代码在这里...
}

const nextSnackToEat = weightedRandom(items, weights); // 可能是 '🍎'

加权随机的应用

算法

直接的方法如下:

  1. 根据权重重复列表中的每个项目。
  2. 从列表中随机选择一个项目。

例如,在水果和蔬菜的情况下,我们可以生成大小为3 + 7 + 1 = 11的以下列表:

const items =   [ '🍌', '🍎', '🥕' ];
const weights = [  3,    7,    1  ];

// 根据权重重复项目。
const weightedItems = [
  '🍌', '🍌', '🍌',
  '🍎', '🍎', '🍎', '🍎', '🍎', '🍎', '🍎',
  '🥕',
];

// 现在只需从weightedItems数组中随机选择项目。

然而,正如你所看到的,这种方法可能需要大量的内存,特别是当我们需要在weightedItems列表中重复很多项目时。想象一下,如果你需要将一个字符串如"some-random-string"18个字节)重复十亿次。你将需要额外分配大约180Mb的内存空间来存储这个数组。

更高效的方法如下:

  1. 准备每个项目的累积权重列表(即cumulativeWeights列表,该列表将与原始的weights列表具有相同数量的元素)。在我们的例子中,它将如下所示:cumulativeWeights = [3, 3 + 7, 3 + 7 + 1] = [3, 10, 11]
  2. 生成从0到最大累积权重值的随机数randomNumber。在我们的例子中,随机数将在[0..11]的范围内。假设我们有randomNumber = 8
  3. 从左到右遍历cumulativeWeights列表,并选择第一个大于或等于randomNumber的元素。我们将使用这个元素的索引从items数组中选择项目。

这种方法的思想是,较高的权重将占据更多的数值空间。因此,随机数落入"较高权重数字桶"的可能性更高。

const weights =           [3, 7,  1 ];
const cumulativeWeights = [3, 10, 11];

// 以伪代码的方式,我们可以这样考虑cumulativeWeights数组。
const pseudoCumulativeWeights = [
  1, 2, 3,               // <-- [3]个数字
  4, 5, 6, 7, 8, 9, 10,  // <-- [7]个数字
  11,                    // <-- [1]个数字
];

例:

/**
 * 根据权重选择随机项目。
 * 权重较大的项目将被更频繁地选择(具有较高的概率)。
 *
 * 例如:
 * - items = ['banana', 'orange', 'apple']
 * - weights = [0, 0.2, 0.8]
 * - weightedRandom(items, weights) 在80%的情况下返回'apple',
 *   在20%的情况下返回'orange',它永远不会返回'banana'(因为选择香蕉的概率为0%)
 *
 * @param {any[]} items
 * @param {number[]} weights
 * @returns {{item: any, index: number}}
 */
export default function weightedRandom(items, weights) {
  if (items.length !== weights.length) {
    throw new Error('Items and weights must be of the same size');
  }

  if (!items.length) {
    throw new Error('Items must not be empty');
  }

  // 准备累积权重数组。
  // 例如:
  // - weights = [1, 4, 3]
  // - cumulativeWeights = [1, 5, 8]
  const cumulativeWeights = [];
  for (let i = 0; i < weights.length; i += 1) {
    cumulativeWeights[i] = weights[i] + (cumulativeWeights[i - 1] || 0);
  }

  // 在范围[0...sum(weights)]内获取随机数
  // 例如:
  // - weights = [1, 4, 3]
  // - maxCumulativeWeight = 8
  // - 随机数的范围是[0...8]
  const maxCumulativeWeight = cumulativeWeights[cumulativeWeights.length - 1];
  const randomNumber = maxCumulativeWeight * Math.random();

  // 根据权重选择随机项目。
  // 权重较大的项目将被更频繁地选择。
  for (let itemIndex = 0; itemIndex < items.length; itemIndex += 1) {
    if (cumulativeWeights[itemIndex] >= randomNumber) {
      return {
        item: items[itemIndex],
        index: itemIndex,
      };
    }
  }
}

实现

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群