Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re^2: Fastest way to lookup a point in a set

by marioroy (Prior)
on Aug 06, 2017 at 19:12 UTC ( [id://1196858]=note: print w/replies, xml ) Need Help??


in reply to Re: Fastest way to lookup a point in a set
in thread Fastest way to lookup a point in a set

Update: Reran and posted results from matching Perl versions: perl-5.24.2 and cperl-5.24.2c.

Update: Added results from Perl 5.26.0 for comparison.

Hi karlgoethebier,

With little change, the code can run just as fast.

use strict; use warnings; use Data::Dump qw(pp); use feature qw(say); my @points = map { pp($_) } ( [ 0, 0 ], [ -1, -2 ], [ 1, 2 ], [ -1, 2 ], [ 1, -2 ], [ 0, 1 ], [ 1, 0 ], [ -1, 0 ], [ 0, -1 ], [ 2147483647, 2147483647 ], [ 2147483647, -2147483647 ], [ -2147483647, 2147483647 ], [ -2147483647, -2147483647 ], ); kgb_str_look( kgb_str_hash() ); sub kgb_str_hash { my %cells = map { $_ => undef } @points; \%cells; } sub kgb_str_look { my $cells = shift; for (@points) { ( exists $cells->{$_} ) ? say $_ : die; } }

In the spirit of fun, added kgb to the test script. The mat_hash was updated to safeguard from auto-vivification. See this post.

use Data::Dump qw(pp); sub kgb_hash { my %cells = map { pp($_) => undef } @points; \%cells; } { my @points_str; sub kgb_look { my $cells = shift; unless (@points_str) { for my $p (@points) { push @points_str, pp($p); } } for my $p (@points_str) { exists $cells->{$p} or die; } exists $cells->{'notfound'} and die; exists $cells->{'notfound2'} and die; exists $cells->{'notfound3'} and die; } } my $kgb_ref = kgb_hash(); ... timethese 200000, { Big => sub { big_look($big_ref) }, # $cells->{ ($p->[1] << 32) | ($ +p->[0] & 0xFFFFFFFF) } Kgb => sub { kgb_look($kgb_ref) }, # $cells->{ $str } # optimized Lan => sub { lan_look($lan_ref) }, # $cells->{ "@$p" } Mat => sub { mat_look($mat_ref) }, # $cells->{ $_->[0] }{ $_->[1] } Pak => sub { pak_look($pak_ref) }, # $cells->{ pack "ii", $p->[0], +$p->[1] } St2 => sub { st2_look($st2_ref) }, # $cells->{ join(':', @$p) } St3 => sub { st3_look($st3_ref) }, # $cells->{ $str } # optimized Str => sub { str_look($str_ref) }, # $cells->{ $p->[0] .':'. $p->[1 +] } };

Results obtained from a Mac laptop running at 2.6 GHz, comparing perl-5.24.2 against cperl-5.24.2c.

$ /opt/perl-5.24.2/bin/perl test.pl Benchmark: timing 200000 iterations of Big, Kgb, Lan, Mat, Pak, St2, S +t3, Str... Big: 6 wallclock secs ( 5.90 usr + 0.00 sys = 5.90 CPU) @ 33898.31/s +(n=200000) Kgb: 2 wallclock secs ( 2.48 usr + 0.00 sys = 2.48 CPU) @ 80645.16/s +(n=200000) Lan: 5 wallclock secs ( 4.58 usr + 0.00 sys = 4.58 CPU) @ 43668.12/s +(n=200000) Mat: 7 wallclock secs ( 6.80 usr + 0.00 sys = 6.80 CPU) @ 29411.76/s +(n=200000) Pak: 5 wallclock secs ( 5.24 usr + 0.00 sys = 5.24 CPU) @ 38167.94/s +(n=200000) St2: 5 wallclock secs ( 4.54 usr + 0.00 sys = 4.54 CPU) @ 44052.86/s +(n=200000) St3: 2 wallclock secs ( 2.31 usr + 0.00 sys = 2.31 CPU) @ 86580.09/s +(n=200000) Str: 5 wallclock secs ( 4.77 usr + 0.01 sys = 4.78 CPU) @ 41841.00/s +(n=200000) $ /opt/cperl-5.24.2c/bin/cperl test.pl Benchmark: timing 200000 iterations of Big, Kgb, Lan, Mat, Pak, St2, S +t3, Str... Big: 6 wallclock secs ( 5.71 usr + 0.00 sys = 5.71 CPU) @ 35026.27/s +(n=200000) Kgb: 2 wallclock secs ( 2.22 usr + 0.00 sys = 2.22 CPU) @ 90090.09/s +(n=200000) Lan: 5 wallclock secs ( 4.49 usr + 0.00 sys = 4.49 CPU) @ 44543.43/s +(n=200000) Mat: 6 wallclock secs ( 5.88 usr + 0.00 sys = 5.88 CPU) @ 34013.61/s +(n=200000) Pak: 5 wallclock secs ( 5.42 usr + 0.00 sys = 5.42 CPU) @ 36900.37/s +(n=200000) St2: 5 wallclock secs ( 4.44 usr + 0.01 sys = 4.45 CPU) @ 44943.82/s +(n=200000) St3: 2 wallclock secs ( 2.03 usr + 0.00 sys = 2.03 CPU) @ 98522.17/s +(n=200000) Str: 4 wallclock secs ( 4.51 usr + 0.00 sys = 4.51 CPU) @ 44345.90/s +(n=200000)

Results from Perl 5.26.0 for comparison.

Benchmark: timing 200000 iterations of Big, Kgb, Lan, Mat, Pak, St2, S +t3, Str... Big: 6 wallclock secs ( 5.69 usr + 0.00 sys = 5.69 CPU) @ 35149.38/s +(n=200000) Kgb: 2 wallclock secs ( 2.21 usr + 0.00 sys = 2.21 CPU) @ 90497.74/s +(n=200000) Lan: 4 wallclock secs ( 4.33 usr + 0.00 sys = 4.33 CPU) @ 46189.38/s +(n=200000) Mat: 7 wallclock secs ( 6.88 usr + 0.01 sys = 6.89 CPU) @ 29027.58/s +(n=200000) Pak: 5 wallclock secs ( 5.32 usr + 0.00 sys = 5.32 CPU) @ 37593.98/s +(n=200000) St2: 5 wallclock secs ( 4.32 usr + 0.00 sys = 4.32 CPU) @ 46296.30/s +(n=200000) St3: 2 wallclock secs ( 2.13 usr + 0.00 sys = 2.13 CPU) @ 93896.71/s +(n=200000) Str: 5 wallclock secs ( 4.58 usr + 0.00 sys = 4.58 CPU) @ 43668.12/s +(n=200000)

For some reason, the state feature doesn't support initialization in list context.

sub kgb_look { my $cells = shift; state @points_str = map { pp($_) } @points; ... } Initialization of state variables in list context currently forbidden +at test.pl line 341, near "@points;" Execution of test.pl aborted due to compilation errors.

Alrighty, state initialization works fine for an anonymous array.

use feature qw(state); sub kgb_look { my $cells = shift; state $points_str = [ map { pp($_) } @points ]; for my $p (@{ $points_str }) { exists $cells->{$p} or die; } exists $cells->{'notfound'} and die; exists $cells->{'notfound2'} and die; exists $cells->{'notfound3'} and die; }

Regards, Mario

Replies are listed 'Best First'.
Re^3: Fastest way to lookup a point in a set
by karlgoethebier (Abbot) on Aug 06, 2017 at 19:48 UTC
    "...little change..."

    Ouch! Yes, sure - just calling it once. My fault. Very nice. See also. Thank you very much Mario and best regards, Karl

    «The Crux of the Biscuit is the Apostrophe»

    This signature has been bowdlerized because of a special request.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1196858]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others examining the Monastery: (5)
As of 2024-03-29 12:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found