Re^2: The most efficient way for searching for an element in an array?

You’re right, using a hash is, in general, a better approach than using an array, because a hash is, by its nature, optimised for lookup.

There’s a useful discussion of the various options in perlfaq4#How-can-I-tell-whether-a-certain-element-is-contained-in-a-list-or-array?

Athanasius <°(((>< contra mundum Iustus alius egestas vitae, eros Piratica,

Comment on Re^2: The most efficient way for searching for an element in an array?

Replies are listed 'Best First'.
Re^3: The most efficient way for searching for an element in an array? winner is ~~ smart match by Discipulus (Canon) on Jan 07, 2016 at 10:16 UTC
In fact the usefull discussion suggested by Athanasius tell us to use the smart match operator `~~` My benchmarks (tell if i'm wrong) tell us the same: the smart match operator is the fastest. use strict; use warnings; use Benchmark qw(cmpthese timethese); use 5.010; use List::Util qw(any); my $search = $ARGV[0]\|\|'perlaceo'; my $file = $ARGV[1]\|\|'enwiktionary-latest-all-titles-in-ns0'; die unless $file; my @lines; open my $fh,'<',$file or die "Unable to open $file"; @lines = <$fh>; print "\nFILE: $file\nARRAY ELEMENTS: ", scalar @lines," (read in ",(time - $^T), " seconds).\n\n"; my $iterations = -3; ###################################################################### +########## my $name1 = "Plain array lookup"; # my $code1 = <<'END_CODE1'; for(@lines){ last if $_ eq $search } END_CODE1 ###################################################################### +########## my $name2 = "List::Util any "; # my $code2 = <<'END_CODE2'; any { $_ eq $search } @lines; END_CODE2 ###################################################################### +########## my $name3 = "smart match ~~ "; # my $code3 = <<'END_CODE3'; $search ~~ @lines; END_CODE3 ###################################################################### +########## my $results = timethese($iterations, { $name1 => $code1, $name2 => $code2, $name3 => $code3 } ) ; print "\n\n"; cmpthese( $results ); [download] here my results: FILE: cat.txt ARRAY ELEMENTS: 3 (read in 0 seconds). Rate List::Util any Plain array lookup sma +rt match ~~ List::Util any 2548237/s -- -38% + -62% Plain array lookup 4105378/s 61% -- + -38% smart match ~~ 6655789/s 161% 62% + -- FILE: HOSTS-zero-tollerance.txt ARRAY ELEMENTS: 10605 (read in 0 seconds). Rate List::Util any Plain array lookup sma +rt match ~~ List::Util any 2599992/s -- -41% + -62% Plain array lookup 4437049/s 71% -- + -36% smart match ~~ 6879527/s 165% 55% + -- FILE: 02packages.details.txt ARRAY ELEMENTS: 165584 (read in 2 seconds). Rate List::Util any Plain array lookup sma +rt match ~~ List::Util any 2481882/s -- -46% + -61% Plain array lookup 4556540/s 84% -- + -28% smart match ~~ 6362283/s 156% 40% + -- FILE: enwiktionary-latest-all-titles-in-ns0 ARRAY ELEMENTS: 4316483 (read in 91 seconds). Rate List::Util any Plain array lookup sma +rt match ~~ List::Util any 2565579/s -- -44% + -63% Plain array lookup 4621251/s 80% -- + -34% smart match ~~ 6972221/s 172% 51% + -- [download] L* There are no rules, there are no thumbs.. Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: The most efficient way for searching for an element in an array? winner is ~~ smart match
by Discipulus (Canon) on Jan 07, 2016 at 10:16 UTC

Athanasius

~~

use strict;
use warnings;
use Benchmark qw(cmpthese timethese);
use 5.010;
use List::Util qw(any);

my $search = $ARGV[0]||'perlaceo';
my $file = $ARGV[1]||'enwiktionary-latest-all-titles-in-ns0';
die unless $file;
my @lines;
open my $fh,'<',$file or die "Unable to open $file";
@lines = <$fh>;
print "\nFILE: $file\nARRAY ELEMENTS: ",
      scalar @lines," (read in ",(time - $^T),
      " seconds).\n\n";

my $iterations = -3;
######################################################################
+##########
my $name1 = "Plain array lookup"; #
my $code1 = <<'END_CODE1';
     for(@lines){ last if $_ eq $search }
END_CODE1
######################################################################
+##########
my $name2 = "List::Util any    "; #
my $code2 = <<'END_CODE2';
     any { $_ eq $search } @lines;
END_CODE2
######################################################################
+##########
my $name3 = "smart match ~~    "; #
my $code3 = <<'END_CODE3';
   $search ~~ @lines;
END_CODE3
######################################################################
+##########
my $results = timethese($iterations, {  $name1 => $code1,
                                        $name2 => $code2,
                                        $name3 => $code3
                                      } ) ;
print "\n\n";
cmpthese( $results );
[download]

FILE: cat.txt
ARRAY ELEMENTS: 3 (read in 0 seconds).
                        Rate List::Util any     Plain array lookup sma
+rt match ~~
List::Util any     2548237/s                 --               -38%    
+           -62%
Plain array lookup 4105378/s                61%                 --    
+           -38%
smart match ~~     6655789/s               161%                62%    
+             --



FILE: HOSTS-zero-tollerance.txt
ARRAY ELEMENTS: 10605 (read in 0 seconds).
                        Rate List::Util any     Plain array lookup sma
+rt match ~~
List::Util any     2599992/s                 --               -41%    
+           -62%
Plain array lookup 4437049/s                71%                 --    
+           -36%
smart match ~~     6879527/s               165%                55%    
+             --



FILE: 02packages.details.txt
ARRAY ELEMENTS: 165584 (read in 2 seconds).
                        Rate List::Util any     Plain array lookup sma
+rt match ~~
List::Util any     2481882/s                 --               -46%    
+           -61%
Plain array lookup 4556540/s                84%                 --    
+           -28%
smart match ~~     6362283/s               156%                40%    
+             --



FILE: enwiktionary-latest-all-titles-in-ns0
ARRAY ELEMENTS: 4316483 (read in 91 seconds).
                        Rate List::Util any     Plain array lookup sma
+rt match ~~
List::Util any     2565579/s                 --               -44%    
+           -63%
Plain array lookup 4621251/s                80%                 --    
+           -34%
smart match ~~     6972221/s               172%                51%    
+             --
[download]

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

[reply]
[d/l]
[select]