in reply to Re: Fastest way to test membership in a constant set
in thread Fastest way to test membership in a constant set
This is fine if you have just a few keys. However, this approach is O(n) (i.e. execution time increases linearly with the number of items in the set), whereas a hash has approximately constant lookup time — or O(1).
Even for only 10 items, a hash is considerably faster:
#!/usr/bin/perl -w my $nkeys = 10; my @keys; our $key; # (keep last key for lookup below) for (1..$nkeys) { # generate random keys consisting of 3..10 chars $key = join "", map chr(97+int(rand(26))), (1..3+int(rand(8))); push @keys, $key; } # setup 'if'-code my $code = "sub isMember_if {\n" . join("", map "return 1 if \$_[0] eq '$_';\n", @keys) . "return 0;}"; #print "$code\n"; eval $code; # setup hash my %hash = map { $_ => 1 } @keys; sub isMember_hash { return $hash{$_[0]} }; use Benchmark 'cmpthese'; cmpthese( -1, { 'if' => 'isMember_if($key)', 'hash' => 'isMember_hash($key)' });
On my machine, this prints (results vary slightly, depending on random keys being used)
Rate if hash if 628278/s -- -68% hash 1946613/s 210% --
Update: Actually, Perl's hashes are blazingly fast: even for just one key/comparison ($nkeys = 1), the if-approach still doesn't outperform the hash; and with key lengths of more than about 3 chars, the hash lookup is even noticeably faster (which seems to indicate that comparing two identical strings is slower than computing the hashed value of that string...).
|
|---|
| Replies are listed 'Best First'. | |
|---|---|
|
Re^3: Fastest way to test membership in a constant set
by Cabrion (Friar) on Jul 28, 2007 at 10:29 UTC |