如何优化加权随机数生成的效率？

生成加权随机数

加权随机数生成涉及从一个范围中选择一个随机数，其中每个数字的概率由重量。此任务出现在各种应用中，例如模拟和游戏。

初始解决方案

常见的方法是拒绝采样，如提供了 ColdFusion 代码。此方法涉及创建一个查找表，其中元素根据权重分布。但是，这种方法有局限性，例如构建表的线性开销和潜在的内存消耗问题。

替代策略

• 线性求和： 另一种策略涉及对权重进行迭代求和，直到总和超过 [0,1) 范围内随机生成的数字。然后返回关联的值。这种方法没有前期成本，但具有线性时间复杂度。
• 储层采样：此方法涉及从元素流中选择随机样本。当遇到每个元素时，它会以与其重量成比例的概率添加到储存器中。存储库大小保持固定，确保恒定的时间复杂度。
• 别名采样：此技术利用预先计算的表从加权分布中选择随机数。它保证了恒定的时间复杂度，并且对于大的或高度倾斜的权重分布通常比其他方法更有效。

实现

加权随机的实现使用别名采样在 JavaScript 中生成数字：

function weightedRand(weights) {
  // Build the alias table
  let table = [];
  let totalWeight = 0;
  for (let i = 0; i < weights.length; i++) {
    totalWeight += weights[i];
  }
  for (let i = 0; i < weights.length; i++) {
    let prob = weights[i] / totalWeight;
    let alias = i;
    table.push({ prob: prob, alias: alias });
  }
  
  // Generate a random number
  return function() {
    let r = Math.random() * totalWeight;
    let i = 0;
    let alias = -1;
    while (i < table.length && alias === -1) {
      if (r < table[i].prob) {
        alias = i;
      } else {
        r -= table[i].prob;
        i = table[i].alias;
      }
    }
    return alias;
  }
}

以上是如何优化加权随机数生成的效率？的详细内容。更多信息请关注PHP中文网其他相关文章！