There's an algorithm in the cookbook that deals with this problem, and that's already quoted here.

But, if you are willing to spend the memory, then you might be able to to do it faster. The following algorithm assumes that @freq contains non-negative integers (the algorithm can trivially be extended to non-negative rational numbers). It also assumes you have enough memory for an array of size $N, where $N = do {my $s = 0; $s += $_ for @freq; $s}, and that the frequency doesn't change.

After preproccessing, the sampling can be done in constant time.

    my @set = map {($_) x $freq $_} 0 .. $#freq;
 
    # Draw a weighted random number.
    sub draw {$set rand @set}  # Now, where did the brackets go???????

-- Abigail