Re^2: how to quickly tell if number is in an array

If his quickly means faster, let's compare those two solutions:

use Benchmark qw(timethese);
use strict;
use warnings;

my @array = (1 .. 100000);
timethese(100, {granfather => \&grandfather, usual => \&usual});

sub grandfather {
    return 1 if grep {$_ == 100000} @array;
}

sub usual {
    for my $a (@array) {
        return 1 if ($a == 100000);
    }
    return 0;
}
[download]

If the element we serach is at the end, grandfather's is a little bit faster:

Benchmark: timing 100 iterations of granfather, usual...
granfather:  4 wallclock secs ( 3.58 usr +  0.00 sys =  3.58 CPU) @ 27
+.95/s (n=1
00)
     usual:  4 wallclock secs ( 4.13 usr +  0.00 sys =  4.13 CPU) @ 24
+.24/s (n=1
00)
[download]

But if you change the above code to search for 3 (at the beginning of the array), then the usual way is much faster:

Benchmark: timing 100 iterations of granfather, usual...
granfather:  3 wallclock secs ( 3.58 usr +  0.00 sys =  3.58 CPU) @ 27
+.95/s (n=1
00)
     usual:  0 wallclock secs ( 0.00 usr +  0.00 sys =  0.00 CPU)
            (warning: too few iterations for a reliable count)
[download]

With something in the middle say 50000, the usual way is still close to 50% faster.

Benchmark: timing 100 iterations of granfather, usual...
granfather:  4 wallclock secs ( 3.69 usr +  0.03 sys =  3.72 CPU) @ 26
+.89/s (n=1
00)
     usual:  2 wallclock secs ( 2.08 usr +  0.00 sys =  2.08 CPU) @ 48
+.12/s (n=1
00)
[download]

Now you know which direction it is pointing to ;-)

Comment on Re^2: how to quickly tell if number is in an array Select or Download Code

Replies are listed 'Best First'.
Re^3: how to quickly tell if number is in an array by GrandFather (Saint) on Oct 12, 2005 at 01:27 UTC
A good reply pg, and valuable in pointing out that "simplest" is not always "best" for given values of simplest and best. (In fact simplest is often "worst".) OP did however ask about simplest and expressed interest in how `grep` could be used. Now if you could benchmark "simplest" that would be a neat trick. Perl is Huffman encoded by design.	[reply] [d/l]
Re^4: how to quickly tell if number is in an array by sauoq (Abbot) on Oct 12, 2005 at 02:15 UTC
Now if you could benchmark "simplest" that would be a neat trick. Well, one thing we might ask is which of two ways of doing something results in more work for the same result. In this case, pg's method produces less work because `grep` has to go through the entire list each time (and then, in scalar context, returns the number of times it found a match) whereas pg explicity returns when he finds the first occurrence. The are both linear, but `grep` will take about twice the time on average. For this particular problem, a `for` loop is probably the Right Way To Do It^&trade. Sure, `grep` can be used as could `map`, a C-style `for`, a `while` or `until`, or a couple well-placed `goto` statements with corresponding labels... but, that doesn't mean they should be. I do agree that, as the OP asked about it, the use of `grep` should be discussed and, ultimately, the reasons to avoid it should be explained. (An explanation goes a lot further than a benchmark.) But, I don't like showing him how to use `grep` with no explanation of why it isn't ideal because he's likely to be drawn to the simplicity of the idiom without considering its drawbacks. -sauoq "My two cents aren't worth a dime.";	[reply] [d/l] [select]