Re: [FWP] Weighted sampling

[Jasvir Nagra <jas@cs.auckland.ac.nz>]

abigail@foad.org writes:

> 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

Ah, the perils of coding straight into an email...I should know better
than that.  Stray $i in previous code.

My apologies to anyone who pushed that snippet into production. ;-)

#!/usr/bin/perl

@weights = (1,0,2);
@cweight = map { $sums += $_ } @weights;

print &sample;

sub sample {  
  $rand = rand $cweight[-1];  
  for (0..$#cweight) {    
     return $_ if $rand < $cweight[$_];  
  }
}


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