带你读《图解算法小抄》二十六、数据统计（1）https://developer.aliyun.com/article/1347724?groupCode=tech_library
更高效的方法如下：
- 准备每个项目的累积权重列表（即cumulativeWeights列表，该列表将与原始的weights列表具有相同数量的元素）。在我们的例子中，它将如下所示：cumulativeWeights = [3, 3 + 7, 3 + 7 + 1] = [3, 10, 11]。
- 生成从0到最大累积权重值的随机数randomNumber。在我们的例子中，随机数将在[0..11]的范围内。假设我们有randomNumber = 8。
- 从左到右遍历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]个数字];
以下是weightedRandom函数的实现示例：
/** * 根据权重选择随机项目。 * 权重较大的项目将被更频繁地选择（具有较高的概率）。 * * 例如： * - 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, }; } }}
4）实现
- 可以在weightedRandom.js文件中找到weightedRandom()函数的实现。
- 可以在test/weightedRandom.test.js文件中找到测试用例。
