Re: Weighted random numbers generator

You can swap memory for time to do this in O(1). Populate an array with your values in the distribution you want, and select a random index.

Your example, ( 1, 1.25, 3.6, 2), is ( 20/20, 25/20, 72/20, 40/20), so:

{
    my @dist = (
                 (0) x 20,
                 (1) x 25,
                 (2) x 72,
                 (3) x 40
               );
    sub choose_weighted {
        $dist[ rand(@dist)];
    }
}
[download]

If time is not an issue, your method is fine, except that < is probably better than <= in the comparisons. That is because rand() returns a number less than one.

After Compline,
Zaxo

Comment on Re: Weighted random numbers generator Download Code

Replies are listed 'Best First'.
•Re: Re: Weighted random numbers generator by merlyn (Sage) on Mar 13, 2003 at 18:17 UTC
I challenge the notion that this is O(1). Certainly, it takes O(n) time to set up the array. -- Randal L. Schwartz, Perl hacker Be sure to read my standard disclaimer if this is a reply.	[reply]
Re: •Re: Re: Weighted random numbers generator by Zaxo (Archbishop) on Mar 13, 2003 at 18:28 UTC
But it's only set up once. That's why the closure. Overhead is not charged in scaling arguments, and array indexing is certainly O(1) for positional representations - up until you need bigints for the indexes. After Compline, Zaxo	[reply]
Re: Re: •Re: Re: Weighted random numbers generator by no_slogan (Deacon) on Mar 13, 2003 at 18:48 UTC
But it's only set up once. In merlyn's article, the weights change every time a random value is chosen. It's reasonable that one might want to do that. It seems like it should be possible to set up some kind of search tree that will work in O(log n) time in that situation, but that's making my brain hurt. Update: Couldn't let this go. Use a balanced binary tree. Each node knows its own weight, and the total weight of its subtree. Let `$val = rand($tree->{total_weight})` and then `sub search { my ($tree, $val) = @_; return $tree if $val < $tree->{weight}; $val -= $tree->{weight}; return search($tree->{left}, $val) if $val < $tree->{left}->{total_w +eght}; $val -= $tree->{left}->{total_weight}; return search($tree->{right}, $val); }` [download] Insertions, deletions, and weight changes must recalculate up to log(n) weights. Now where's the brain specialist... ...up until you need bigints for the indexes. Where are you going to store an array that big?	[reply] [d/l]


Syntactic Confectionery Delight
	PerlMonks