产生加权随机数 [英] Generate A Weighted Random Number

问题描述

我想设计一个（好）的方式来选择一个范围，其中范围内的每个数字都被赋予权重可能的数字的随机数。简单地说：给定的数字范围（0,1,2）中选择一个号码，其中0有被选中的80％的概率，1有10％的几率和2有10％的几率

I'm trying to devise a (good) way to choose a random number from a range of possible numbers where each number in the range is given a weight. To put it simply: given the range of numbers (0,1,2) choose a number where 0 has an 80% probability of being selected, 1 has a 10% chance and 2 has a 10% chance.

它已经因为我的大学数据类约8年，所以你可以想象正确的公式，这脱离了我的时刻。

It's been about 8 years since my college stats class, so you can imagine the proper formula for this escapes me at the moment.

下面是我想出了廉价和肮脏的方法。该解决方案使用的ColdFusion。你可以使用任何语言，你想。我是一个程序员，我觉得我能处理移植它。最终，我的解决方案需要在Groovy - 我的ColdFusion写这一个，因为它很容易快速编写/测试CF

Here's the 'cheap and dirty' method that I came up with. This solution uses ColdFusion. Yours may use whatever language you'd like. I'm a programmer, I think I can handle porting it. Ultimately my solution needs to be in Groovy - I wrote this one in ColdFusion because it's easy to quickly write/test in 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 ) );    
}

我在寻找更好的解决方案，请提出改进​​意见或替代方案。

I'm looking for better solutions, please suggest improvements or alternatives.

推荐答案

拒绝抽样（如您的解决方案）是想到，这样你建立一个查找表填充他们的重量分布要素的第一件事，然后选择一个随机位置的表并将其返回。作为一个实现选择，我会做一个高阶函数，它接受一个规范，并返回一个函数返回一个基于中规范分配值，这样一来，您就不必建表为每个调用。的缺点是，建立该表的算法的性能是线性通过的项目数和那么可能有很多用于大规格的内存使用情况（或那些成员具有非常小或precise权重，例如，{0： 0.99999，1：0.00001}）。有利的一面是，选择一个值具有一定的时间，这可能是可取的，如果性能是至关重要的。在JavaScript：

Rejection sampling (such as in your solution) is the first thing that comes to mind, whereby you build a lookup table with elements populated by their weight distribution, then pick a random location in the table and return it. As an implementation choice, I would make a higher order function which takes a spec and returns a function which returns values based on the distribution in the spec, this way you avoid having to build the table for each call. The downsides are that the algorithmic performance of building the table is linear by the number of items and there could potentially be a lot of memory usage for large specs (or those with members with very small or precise weights, e.g. {0:0.99999, 1:0.00001}). The upside is that picking a value has constant time, which might be desirable if performance is critical. In 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：

Another strategy is to pick a random number in [0,1) and iterate over the weight specification summing the weights, if the random number is less than the sum then return the associated value. Of course, this assumes that the weights sum to one. This solution has no up-front costs but has average algorithmic performance linear by the number of entries in the spec. For example, in 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...

这篇关于产生加权随机数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！