我正在尝试设计一种(好的)方法,从可能的数字范围中选择一个随机数,其中该范围内的每个数字都具有权重。简单地说:给定数字范围(0,1,2),请选择一个数字,其中0的概率为80%,1的概率为10%,2的概率为10%。
自从我的大学统计课程上课以来已经有8年了,所以您可以想象一下,目前适合我的方法并不适合我。
这是我想出的“便宜又肮脏”的方法。此解决方案使用ColdFusion。您可以使用任何您想要的语言。我是一名程序员,我想我可以移植它。最终,我的解决方案需要使用Groovy- 我在ColdFusion中编写了此解决方案,因为它很容易在CF中快速进行编写/测试。
public function weightedRandom( Struct options ) { var tempArr = []; for( var o in arguments.options ) { var weight = arguments.options[ o ] * 10; for ( var i = 1; i<= weight; i++ ) { arrayAppend( tempArr, o ); } } return tempArr[ randRange( 1, arrayLen( tempArr ) ) ]; } // test it opts = { 0=.8, 1=.1, 2=.1 }; for( x = 1; x<=10; x++ ) { writeDump( weightedRandom( opts ) ); }
我正在寻找更好的解决方案,请提出改进建议或替代方案。
拒绝采样(例如在您的解决方案中)是想到的第一件事,即您要构建一个查找表,并用其权重分布填充元素,然后在表中选择一个随机位置并将其返回。作为一种实现选择,我将制作一个高阶函数,该函数接受一个规范并返回一个函数,该函数根据规范中的分布返回值,这样您就不必为每个调用构建表。缺点是,构建表的算法性能与项数成线性关系,并且对于大型规范(或具有很小或精确权重的成员,例如{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)然后对权重总和的权重规范进行迭代,如果随机数小于总和,则返回相关值。当然,这假定权重之和为1。该解决方案没有前期成本,但平均算法性能与规范中的条目数成线性关系。例如,在JavaScript中:
[0,1)
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...