As easy it is to code in perl, you'd think someone might actually look and see what the answer really is:

#!/usr/bin/perl -w

use Benchmark;
use strict;

# Times array searches.  Assumes search element is in the
# dead center of the array

my $x;
my @array;

for (10, 50, 100, 500, 1000, 5000)
{
    @array = 1 .. $_;
    $x = $_ / 2;

    print "Array size is $_\n";

    timethese(5000, {
        'grep' => \&grep_test,
        hash => \&hash_test,
        manual => \&manual_test
    });
}

sub grep_test
{
    return 1 if grep { $x == $_ } @array;
}

sub hash_test
{
    my %hash;

    $hash{$_}++ for @array;

    return 1 if $hash{$x};
}

sub manual_test
{
    for (@array) { return 1 if $x == $_ }
}  

Array size is 10
Benchmark: timing 5000 iterations of grep, hash, manual...
      grep:  0 wallclock secs ( 0.19 usr +  0.00 sys =  0.19 CPU)
            (warning: too few iterations for a reliable count)
      hash:  0 wallclock secs ( 0.50 usr +  0.00 sys =  0.50 CPU)
    manual:  1 wallclock secs ( 0.17 usr +  0.00 sys =  0.17 CPU)
            (warning: too few iterations for a reliable count)
Array size is 50
Benchmark: timing 5000 iterations of grep, hash, manual...
      grep:  0 wallclock secs ( 0.68 usr +  0.00 sys =  0.68 CPU)
      hash:  0 wallclock secs ( 1.95 usr +  0.00 sys =  1.95 CPU)
    manual:  1 wallclock secs ( 0.53 usr +  0.00 sys =  0.53 CPU)
Array size is 100
Benchmark: timing 5000 iterations of grep, hash, manual...
      grep:  2 wallclock secs ( 1.36 usr +  0.00 sys =  1.36 CPU)
      hash:  4 wallclock secs ( 3.83 usr +  0.00 sys =  3.83 CPU)
    manual:  1 wallclock secs ( 1.00 usr +  0.00 sys =  1.00 CPU)
Array size is 500
Benchmark: timing 5000 iterations of grep, hash, manual...
      grep:  7 wallclock secs ( 6.41 usr +  0.00 sys =  6.41 CPU)
      hash: 20 wallclock secs (19.23 usr +  0.00 sys = 19.23 CPU)
    manual:  5 wallclock secs ( 4.48 usr +  0.00 sys =  4.48 CPU)
Array size is 1000
Benchmark: timing 5000 iterations of grep, hash, manual...
      grep: 13 wallclock secs (12.82 usr +  0.00 sys = 12.82 CPU)
      hash: 41 wallclock secs (38.71 usr +  0.00 sys = 38.71 CPU)
    manual:  9 wallclock secs ( 9.10 usr +  0.01 sys =  9.11 CPU)
Array size is 5000
Benchmark: timing 5000 iterations of grep, hash, manual...
      grep: 68 wallclock secs (64.70 usr +  0.00 sys = 64.70 CPU)
      hash: 243 wallclock secs (220.51 usr +  0.03 sys = 220.54 CPU)
    manual: 48 wallclock secs (45.48 usr +  0.00 sys = 45.48 CPU)
[download]

Based on these results:

1. grep is a little faster for short lists
2. a manual list traversal is faster for larger lists
3. don't use a hash unless you need to search for several items

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.