in reply to 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

Replies are listed 'Best First'.
•Re: Re: Weighted random numbers generator
by merlyn (Sage) on Mar 13, 2003 at 18:17 UTC
[reply]

      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]
        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]

In Section Seekers of Perl Wisdom