Re: [FWP] Weighted sampling

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

Um I don't think this would be very good for large weights (which is
not uncommon).  Its probably better for those cases to use a
cummalative weights table inspite of the fact that its now runs in
linear time.  Btrees anyone?

@cweight = map { $sums += $_ } @weights;

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

"Bernie Cosell" <bernie@fantasyfarm.com> writes:

> 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)] ; }
> 
>   /Bernie\
> -- 
> Bernie Cosell                     Fantasy Farm Fibers
> mailto:bernie@fantasyfarm.com     Pearisburg, VA
>     -->  Too many people, too few sheep  <--          
> 
> ==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
> ==== Send email to <fwp-request@technofile.org> with message _body_
> ====   unsubscribe

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