Re: [FWP] Weighted sampling

[yanick1@sympatico.ca]

On Mon, Mar 19, 2001 at 10:14:35PM +0100, abigail@foad.org wrote:
> 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.

And 

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

would save one useless call of rand.

But wouldn't 

%sample       = ( a => 1, b => 0.5, c => 613 );
$sample_sum  += $sample{ $_ } foreach keys %sample;
@sample_index = sort { $sample{$b} <=> $sample{$a} } keys %sample;

sub draw
{
	my $count = rand $sample_sum;
	for( @sample_index )
	{
			$count -= $sample{ $_ };
			return $_ if $count <= 0;
	}
}

be much faster in average?


Joy,
Yanick

-- 
print map chr hex,
      '59657420616e6f74686572205065726c206861636b65722e' =~ /../g;

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