The hash test seems a little unfair. It is the
only one where you construct the data structure
before testing it.
If you construct the hash before testing the results
are somewhat different
I used the following, a slight change from your program
Assuming that you can use a hash table elsewhere in the program
(and why not?) hash tables appear to make more sense when looked at this way.
I cannot see any use for dynamically creating a hash table
just for one search and, if you are going to search a hash you may
as well structure your data into a hash.
Of course there are exceptions to this, there are exceptions
to everything in the perl world (TIMTOWTDI)
anyway, the data:
use Benchmark;
use strict;
# Times array searches. Assumes search element is in the
# dead center of the array
my $x;
my @array;
my %hash;
for (10, 50, 100, 500, 1000, 5000)
{
@array = 1 .. $_;
$x = $_ / 2;
$hash{$_}++ for @array;
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
{
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.03 usr + 0.00 sys = 0.03 CPU)
(warning: too few iterations for a reliable count)
hash: 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU)
(warning: too few iterations for a reliable count)
manual: 0 wallclock secs ( 0.04 usr + 0.00 sys = 0.04 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.15 usr + 0.00 sys = 0.15 CPU)
(warning: too few iterations for a reliable count)
hash: 0 wallclock secs ( 0.01 usr + 0.00 sys = 0.01 CPU)
(warning: too few iterations for a reliable count)
manual: 0 wallclock secs ( 0.11 usr + 0.00 sys = 0.11 CPU)
(warning: too few iterations for a reliable count)
Array size is 100
Benchmark: timing 5000 iterations of grep, hash, manual...
grep: 0 wallclock secs ( 0.27 usr + 0.00 sys = 0.27 CPU)
(warning: too few iterations for a reliable count)
hash: 0 wallclock secs ( 0.02 usr + 0.00 sys = 0.02 CPU)
(warning: too few iterations for a reliable count)
manual: 1 wallclock secs ( 0.20 usr + 0.00 sys = 0.20 CPU)
(warning: too few iterations for a reliable count)
Array size is 500
Benchmark: timing 5000 iterations of grep, hash, manual...
grep: 1 wallclock secs ( 1.39 usr + 0.00 sys = 1.39 CPU)
hash: 0 wallclock secs (-0.00 usr + 0.00 sys = -0.00 CPU)
(warning: too few iterations for a reliable count)
manual: 1 wallclock secs ( 0.90 usr + 0.00 sys = 0.90 CPU)
Array size is 1000
Benchmark: timing 5000 iterations of grep, hash, manual...
grep: 3 wallclock secs ( 2.79 usr + 0.00 sys = 2.79 CPU)
hash: 0 wallclock secs ( 0.02 usr + 0.00 sys = 0.02 CPU)
(warning: too few iterations for a reliable count)
manual: 2 wallclock secs ( 1.77 usr + 0.00 sys = 1.77 CPU)
Array size is 5000
Benchmark: timing 5000 iterations of grep, hash, manual...
grep: 15 wallclock secs (15.39 usr + 0.00 sys = 15.39 CPU)
hash: 0 wallclock secs ( 0.01 usr + 0.00 sys = 0.01 CPU)
(warning: too few iterations for a reliable count)
manual: 10 wallclock secs ( 9.03 usr + 0.05 sys = 9.08 CPU)
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.