Quickly finding an element in an array

tomhukins has asked for the wisdom of the Perl Monks concerning the following question:

If I want to find out if an element is in an array I can use grep. If I want to find several elements, I can convert the array to a hash and use exists.

I can also use a foreach loop and iterate over the elements, calling last if the element is found. If the element it towards the start of the array, this makes more sense than iterating over the whole array, as the other two methods do.

I decided to benchmark these different techniques, matching the number 0 at the start, middle and end of the array. As I'd expected, foreach is best for arrays with 0 at the start because of the last call, but grep is best in general. Of course, if I were matching multiple elements, I'd create a hash.

So, now for my question: Is this any way I can combine the benefits of the grep and foreach methods by using last within a grep? I've tried doing this, but last doesn't work within grep. Any ideas?

For those who are interested, here is the benchmarking code I used and its results:

#!/usr/bin/perl -Tw

use strict;
use Benchmark;

my @array;
foreach (1..1000) {
    push @array, 1 + int rand 199;
}
my @start = (0, @array);
my @end = (@array, 0);
my @middle = @array;
splice(@middle, 500, 0, 0);

timethese(1000, {
    'grep_start' => sub {
        my $found = 0;
        my @list = grep(0, @start);
        $found = 1 if scalar @list;
    },
    'foreach_start' => sub {
        my $found = 0;
        foreach (@start) {
            $_ == 0 and $found = 1 and last;
        }
    },
    'hash_start' => sub {
        my $found = 0;
        my %hash = map { $_ => undef } @start;
        $found = 1 if exists $hash{0};
    },

    'grep_end' => sub {
        my $found = 0;
        my @list = grep(0, @end);
        $found = 1 if scalar @list;
    },
    'foreach_end' => sub {
        my $found = 0;
        foreach (@end) {
            $_ == 0 and $found = 1 and last;
        }
    },
    'hash_end' => sub {
        my $found = 0;
        my %hash = map { $_ => undef } @end;
        $found = 1 if exists $hash{0};
    },

    'grep_middle' => sub {
        my $found = 0;
        my @list = grep(0, @middle);
        $found = 1 if scalar @list;
    },
    'foreach_middle' => sub {
        my $found = 0;
        foreach (@middle) {
            $_ == 0 and $found = 1 and last;
        }
    },
    'hash_middle' => sub {
        my $found = 0;
        my %hash = map { $_ => undef } @middle;
        $found = 1 if exists $hash{0};
    }
});
[download]

The results were as follows:
Benchmark: timing 1000 iterations of foreach_end, foreach_middle, foreach_start, grep_end, grep_middle, grep_start, hash_end, hash_middle, hash_start...
foreach_end: 1 wallclock secs ( 1.03 usr + 0.01 sys = 1.04 CPU)
foreach_middle: 1 wallclock secs ( 0.52 usr + 0.00 sys = 0.52 CPU)
foreach_start: 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) (warning: too few iterations for a reliable count)
grep_end: 0 wallclock secs ( 0.47 usr + 0.00 sys = 0.47 CPU)
grep_middle: 1 wallclock secs ( 0.47 usr + 0.00 sys = 0.47 CPU)
grep_start: 1 wallclock secs ( 0.48 usr + 0.00 sys = 0.48 CPU)
hash_end: 15 wallclock secs (14.26 usr + 0.00 sys = 14.26 CPU)
hash_middle: 15 wallclock secs (14.25 usr + 0.00 sys = 14.25 CPU)
hash_start: 15 wallclock secs (14.09 usr + 0.03 sys = 14.12 CPU)

Edit Petruchio Thu Jan 10 11:47:48 UTC 2002 - Replaced tabs with spaces, at the author's request. Just say no to tabbed indentation!

Comment on Quickly finding an element in an array Select or Download Code

Replies are listed 'Best First'.
Re (tilly) 1: Quickly finding an element in an array by tilly (Archbishop) on Jan 08, 2002 at 02:37 UTC
Note that hashing will only work out as better if you need to find several elements. IIRC the tradeoff is around 7 elements or so, above that and building the hash works, less and you might as well grep. And if you want to create the hash, the fastest way I know of is: `my %is_there; undef(@is_there{@list});` [download]	[reply] [d/l]
Re: Quickly finding an element in an array by blakem (Monsignor) on Jan 08, 2002 at 01:22 UTC
How about something like this: `#!/usr/bin/perl -wT use strict; my @arr = 1..10; my $tofind = 5; my $found; { grep {$_ == $tofind and $found = 1 and last} @arr; # wont get here if element is found; } print $found ? "I found" : "I didn't find", " element $tofind\n";` [download] Update: changed `eq` to `==`. Thanks to dvergin for the catch. Update2: managed to munge my previous update... thanks to tomhukins for this catch. -Blake	[reply] [d/l] [select]
Re: Re: Quickly finding an element in an array by tomhukins (Curate) on Jan 08, 2002 at 01:48 UTC
Thanks, I've modified my code to use this, but surprisingly perl is dumping core (5.005_03 on FreeBSD and 5.6.1 on Solaris). This is a different problem, but I'm really surprised it's happening. Does anyone know why? Here's some code that reproduces the problem: #!/usr/bin/perl -Tw use strict; use Benchmark; my @array; foreach (1..1000) { push @array, 1 + int rand 199; } my @start = (0, @array); my @end = (@array, 0); my @middle = @array; splice(@middle, 500, 0, 0); timethese(1000, { 'grep_middle' => sub { my $found = 0; grep {$_ == 0 and $found = 1 and last} @middle; }, 'foreach_middle' => sub { my $found = 0; foreach (@middle) { $_ == 0 and $found = 1 and last; } }, 'hash_middle' => sub { my $found = 0; my %hash = map { $_ => undef } @middle; $found = 1 if exists $hash{0}; } }); [download]	[reply] [d/l]
Re: Re: Re: Quickly finding an element in an array by blakem (Monsignor) on Jan 08, 2002 at 01:56 UTC
The bare block around the grep is important... Change this line: `grep {$_ == 0 and $found = 1 and last} @middle;` [download] To: `{ grep {$_ == 0 and $found = 1 and last} @middle; }` [download] And I get: `Benchmark: timing 1000 iterations of foreach_middle, grep_middle, hash +_middle... foreach_middle: 1 wallclock secs ( 0.80 usr + 0.00 sys = 0.80 CPU) +@ 1250.00/s (n=1000) grep_middle: 3 wallclock secs ( 3.09 usr + 0.00 sys = 3.09 CPU) @ 3 +23.62/s (n=1000) hash_middle: 30 wallclock secs (26.40 usr + 0.02 sys = 26.42 CPU) @ 3 +7.85/s (n=1000)` [download] -Blake	[reply] [d/l] [select]
Re: Quickly finding an element in an array by robin (Chaplain) on Jan 08, 2002 at 01:37 UTC
The fastest way to do this is almost certainly to use the `first` routine from the List::Util module. `first` works just like `grep`, except that it stops as soon as it finds an element that matches the condition. It's written in C, and very fast. This module (and its friend Scalar::Util) will be bundled with Perl 5.8, so get used to them now! :-)	[reply]
Re: Quickly finding an element in an array by Juerd (Abbot) on Jan 08, 2002 at 13:49 UTC
`my %hash = map { $_ => undef } @start;` TIMTOWTDI, but building a hash of undef values can be done faster without map: `my %hash; @hash{@start} = ();` [download] `2;0 juerd@ouranos:~$ perl -e'undef christmas' Segmentation fault 2;139 juerd@ouranos:~$` [download]	[reply] [d/l] [select]