如何在编程中生成加权随机数：拒绝采样与迭代搜索？

在编程中生成加权随机数

加权随机数适用于各种场景，其中某个范围内的特定值被选择的概率不同。在本文中，我们探索了两种有效的方法来实现这一目标：

第一种方法由原始提问者提出，涉及拒绝采样。此方法创建一个查找表，其中填充了范围内的元素，其中每个元素出现的次数与其权重成正比。随后，从查找表中选择随机索引来检索随机数。这里的权衡在于构建查找表的线性时间复杂度和大权重规范的潜在内存消耗。

或者，迭代搜索方法迭代计算权重总和同时遍历重量规格。它将这个总和与随机生成的 0 到 1 之间的数字进行比较。如果总和超过随机数，则将相应的值作为随机数返回。与拒绝采样不同，这种方法不会产生前期成本，但平均时间复杂度与权重规范中的条目数量成线性关系。

要在 JavaScript 中演示这两种方法：

// Rejection Sampling
function weightedRand(spec) {
  var i, j, table = [];
  for (i in spec) for (j = 0; j < spec[i] * 10; j++) table.push(i);
  return function() { return table[Math.floor(Math.random() * table.length)]; };
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});

// Iterative Search
function weightedRand2(spec) {
  var i, sum = 0, r = Math.random();
  for (i in spec) { sum += spec[i]; if (r <= sum) return i; }
}

方法的选择取决于特定的应用程序需求，平衡时间复杂度、内存使用和确定性行为。拒绝采样以预先表构建为代价提供恒定时间查找，而迭代搜索提供更简单的实现和线性时间性能。通过利用这些技术，程序员可以有效地生成加权随机数以满足他们的各种编程需求。

以上是如何在编程中生成加权随机数：拒绝采样与迭代搜索？的详细内容。更多信息请关注PHP中文网其他相关文章！