[mplspm]: In a sorted list [better]

[John J. Trammell]

On Tue, Mar 26, 2002 at 10:16:27AM +1100, Ken Williams wrote:
> 
> Since you only care about the keys and not the values, it's generally 
> quicker to construct the hash like so:
> 
> my $hash = sub
> {
>      my ($x,$a) = @_;
>      my %h;
>      @h{@$a} = ();
>      return exists $h{$x};
> };
>

The results of the actual experiment (code below) surprised me.  Is
there something wrong in my test maybe?

#!/usr/bin/perl -w
use strict;
use Benchmark;

sub __map
{
        my ($a) = @_;
        my %h = map { $_, 0 } @$a;
        return \%h;
}

sub __slice
{  
        my ($a) = @_;
        my %h;
        @h{ @$a } = ();
        return \%h;
}

foreach my $size ( 10, 100, 1000, 10_000 )
{
        warn "$size-element array\n";
        my @x = ( 1 .. $size ); 
        timethese( 1_000_000, {
                map =>   q[__map(\@x)],
                slice => q[__slice(\@x)],
        });
}

__END__

10-element array
Benchmark: timing 1000000 iterations of map, slice...
       map:  3 wallclock secs ( 3.77 usr +  0.00 sys =  3.77 CPU) @ 265251.99/s (n=1000000)
     slice:  3 wallclock secs ( 3.94 usr +  0.00 sys =  3.94 CPU) @ 253807.11/s (n=1000000)
100-element array
Benchmark: timing 1000000 iterations of map, slice...
       map:  3 wallclock secs ( 3.81 usr +  0.00 sys =  3.81 CPU) @ 262467.19/s (n=1000000)
     slice:  3 wallclock secs ( 3.94 usr +  0.00 sys =  3.94 CPU) @ 253807.11/s (n=1000000)
1000-element array
Benchmark: timing 1000000 iterations of map, slice...
       map:  3 wallclock secs ( 3.87 usr +  0.00 sys =  3.87 CPU) @ 258397.93/s (n=1000000)
     slice:  3 wallclock secs ( 3.97 usr +  0.00 sys =  3.97 CPU) @ 251889.17/s (n=1000000)
10000-element array
Benchmark: timing 1000000 iterations of map, slice...
       map:  3 wallclock secs ( 3.89 usr +  0.00 sys =  3.89 CPU) @ 257069.41/s (n=1000000)
     slice:  3 wallclock secs ( 4.06 usr +  0.00 sys =  4.06 CPU) @ 246305.42/s (n=1000000)


> The real question is whether the original list would be better stored
> in a hash in the first place, avoiding that conversion each time.  The
> answer is usually yes.  In that case, it's *way* quicker.

Agreed.

-- 
I would like to see an anime where Love conquers all, then goes mad with the
power and sets up a repressive totalitarian regime that ruthlessly crushes
and oppresses all non-love.                        -- Frank Raymond Michaels


--------------------------------------------------
Minneapolis Perl Mongers mailing list

To unsubscribe, send mail to majordomo at pm.org
with "unsubscribe mpls" in the body of the message.