Re: Weighted random selection

There's a much more efficient way if you know the total weight in advance (or calculate it):

use List::Util qw(sum);
my $total = sum values %$group;
my $picked;
for (keys %$group){
    if (rand() < $group->{$_} / $total){
        $picked = $_;
        last;
    }
    # update: I forgot this line:
    $total -= $group->{$_};
    # without this line items later in the hash are chosen
    # too seldom, and you might chose none at all. Very bad.
}
[download]

I somehow think it's not entirely fair, but I can't get a straight thought on stochastic at this time (0:30 AM here), maybe I can think of a prove (or disprove) tomorrow.

Comment on Re: Weighted random selection Download Code

Replies are listed 'Best First'.
Re^2: Weighted random selection by cosmicperl (Chaplain) on Jul 29, 2008 at 00:02 UTC
Hmmm... Not totally sure this'll give me the right weighting. But it has inspired me to write:- `use List::Util qw(sum); my $total = sum values %$group; my $rnd = rand( $total ); my $runningtot = 0; foreach ( keys %$group ) { if ( $rnd > $runningtot && $rnd <= ( $runningtot + $group->{$_} ) +) { $picked = $_; last; }#if $runningtot += $group->{$_}; }#foreach` [download] rand() is only called once. No array is made. Straight forward if and a last to drop out once found. Haven't tested for efficiency but I'm guessing it's pretty good. Lyle	[reply] [d/l]
Re^2: Weighted random selection by jethro (Monsignor) on Jul 28, 2008 at 23:31 UTC
Now (after the correction) later items are chosen too often (just try the test case, ad1 gets picked very very seldom). Which shows that one shouldn't post answers when dead tired. ;-)	[reply]