Re^4: Fastest way to lookup a point in a set (updated)

[marioroy]

Update: Regarding performance, stringification "@$p" reaches join(':',@$p) in Perl 5.22 and onwards. See this post.

Hi LanX,

Added lan_hash and lan_look, based on str_hash and str_look respectively. The stringification is a nice catch. Surprisingly, I didn't expect for it to run slower compared to join(':', @$p) and thought as fast or faster.

sub lan_hash {
   # print "LanX_hash---------------\n";
   my %cells;
   # insert the points into the hash
   for my $p (@points) {
      my $h = $p->[0] . ' ' . $p->[1];
      my ( $x, $y ) = split ' ', $h;
      # print "x='$p->[0]' y='$p->[1]' h='$h' (x='$x' y='$y')\n";
      if ($x != $p->[0]) { die; }
      if ($y != $p->[1]) { die; }
      $cells{$h} = undef;
      # ++$cells{$h};
   }
   scalar(keys %cells) == $npoints or die;
   # lookup each points in the hash
   for my $p (@points) {
      my $h = $p->[0] . ' ' . $p->[1];
      exists $cells{$h} or die;
   }
   exists $cells{'notfound'} and die;
   exists $cells{'notfound2'} and die;
   exists $cells{'notfound3'} and die;
   return \%cells;
}

sub lan_look {
   my $cells = shift;
   for my $p (@points) {
      exists $cells->{ "@$p" } or die;
   }
   exists $cells->{'notfound'} and die;
   exists $cells->{'notfound2'} and die;
   exists $cells->{'notfound3'} and die;
}

my $big_ref = big_hash();
my $lan_ref = lan_hash();
my $mat_ref = mat_hash();
my $pak_ref = pak_hash();
my $st2_ref = str_hash();
my $st3_ref = str_hash();
my $str_ref = str_hash();

timethese 200000, {
   Big => sub { big_look($big_ref) }, # $cells->{ ($p->[1] << 32) | ($
+p->[0] & 0xFFFFFFFF) }
   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 from CentOS 7.3 VM running Perl 5.16.3.

Benchmark: timing 200000 iterations of Big, Lan, Mat, Pak, St2, St3, S
+tr...
 Big: 5 wallclock secs ( 6.14 usr + 0.01 sys = 6.15 CPU) @ 32520.33/s 
+(n=200000)
 Lan: 3 wallclock secs ( 4.47 usr + 0.00 sys = 4.47 CPU) @ 44742.73/s 
+(n=200000)
 Mat: 4 wallclock secs ( 4.67 usr + 0.00 sys = 4.67 CPU) @ 42826.55/s 
+(n=200000)
 Pak: 5 wallclock secs ( 5.36 usr + 0.00 sys = 5.36 CPU) @ 37313.43/s 
+(n=200000)
 St2: 4 wallclock secs ( 4.08 usr + 0.00 sys = 4.08 CPU) @ 49019.61/s 
+(n=200000)
 St3: 2 wallclock secs ( 2.09 usr + 0.00 sys = 2.09 CPU) @ 95693.78/s 
+(n=200000)
 Str: 5 wallclock secs ( 4.91 usr + 0.00 sys = 4.91 CPU) @ 40733.20/s 
+(n=200000)

Benchmark: timing 200000 iterations of Big, Lan, Mat, Pak, St2, St3, S
+tr...
 Big: 6 wallclock secs ( 6.28 usr + 0.00 sys = 6.28 CPU) @ 31847.13/s 
+(n=200000)
 Lan: 4 wallclock secs ( 4.53 usr + 0.00 sys = 4.53 CPU) @ 44150.11/s 
+(n=200000)
 Mat: 5 wallclock secs ( 4.76 usr + 0.00 sys = 4.76 CPU) @ 42016.81/s 
+(n=200000)
 Pak: 5 wallclock secs ( 5.39 usr + 0.00 sys = 5.39 CPU) @ 37105.75/s 
+(n=200000)
 St2: 4 wallclock secs ( 4.13 usr + 0.00 sys = 4.13 CPU) @ 48426.15/s 
+(n=200000)
 St3: 2 wallclock secs ( 2.15 usr + 0.00 sys = 2.15 CPU) @ 93023.26/s 
+(n=200000)
 Str: 5 wallclock secs ( 4.98 usr + 0.00 sys = 4.98 CPU) @ 40160.64/s 
+(n=200000)

Benchmark: timing 200000 iterations of Big, Lan, Mat, Pak, St2, St3, S
+tr...
 Big: 6 wallclock secs ( 6.57 usr + 0.00 sys = 6.57 CPU) @ 30441.40/s 
+(n=200000)
 Lan: 5 wallclock secs ( 5.04 usr + 0.00 sys = 5.04 CPU) @ 39682.54/s 
+(n=200000)
 Mat: 5 wallclock secs ( 5.33 usr + 0.00 sys = 5.33 CPU) @ 37523.45/s 
+(n=200000)
 Pak: 9 wallclock secs ( 5.46 usr + 0.00 sys = 5.46 CPU) @ 36630.04/s 
+(n=200000)
 St2: 4 wallclock secs ( 4.10 usr + 0.00 sys = 4.10 CPU) @ 48780.49/s 
+(n=200000)
 St3: 2 wallclock secs ( 2.11 usr + 0.00 sys = 2.11 CPU) @ 94786.73/s 
+(n=200000)
 Str: 6 wallclock secs ( 5.11 usr + 0.00 sys = 5.11 CPU) @ 39138.94/s 
+(n=200000)

Regards, Mario