拒绝抽样 http://en.wikipedia.org/wiki/Rejection_sampling(例如在您的解决方案中)是首先想到的,您可以构建一个查找表,其中的元素按其权重分布填充,然后在表中选择一个随机位置并将其返回。作为一种实现选择,我将创建一个高阶函数,它接受一个规范并返回一个函数,该函数根据规范中的分布返回值,这样您就不必为每个调用构建表。缺点是构建表的算法性能与项目数量成线性关系,并且大规格(或具有非常小或精确权重的成员的规格,例如 {0:0.99999, 1 :0.00001})。优点是选择值的时间恒定,如果性能至关重要,这可能是可取的。在 JavaScript 中:
function weightedRand(spec) {
var i, j, table=[];
for (i in spec) {
// The constant 10 below should be computed based on the
// weights in the spec for a correct and optimal table size.
// E.g. the spec {0:0.999, 1:0.001} will break this impl.
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});
rand012(); // random in distribution...
另一种策略是在其中选择一个随机数[0,1)
并迭代权重规范,对权重求和,如果随机数小于总和,则返回关联值。当然,这是假设权重之和为一。该解决方案没有前期成本,但平均算法性能与规范中的条目数量成线性关系。例如,在 JavaScript 中:
function weightedRand2(spec) {
var i, sum=0, r=Math.random();
for (i in spec) {
sum += spec[i];
if (r <= sum) return i;
}
}
weightedRand2({0:0.8, 1:0.1, 2:0.1}); // random in distribution...