Re: [FWP] Weighted sampling

[abigail@foad.org]

On Mon, Mar 19, 2001 at 03:31:13PM -0500, Bernie Cosell wrote:
> This is probably pretty trivial stuff, but I was surprised at how easy it 
> turned out to be [and the 'surprise' counted as fun for me].
> 
> The problem: I have a weighted distribution that I need to sample from.  
> I have an array of the 'weights' associated with each sample.  So I did:
> 
> my @dist ;
> foreach my $i (0 .. $#weights)
> {   push @dist, ($i) x $weights[$i] ; }
> 
> sub sample
> {   return $dist[rand(@dist)] ; }


That wouldn't work if @weights contains non-integers, or when the
sum of the weights is huge.

    sub sample {
        my ($count, $sample);
        for (my $i  = 0; $i < @weights; $i ++) {
            $count += $weights [$i];
            $sample = $i if rand $count < $weights [$i];
        }
        $sample;
    }


This uses O (1) additional memory, and only requires @weights to contain
non-negative numbers.



Abigail

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe