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
    Perl never ceases to impress me. Also, shame on me for not doing my own benchmarks. I did know the if-approach would not scale well, but the OP seemed to be looking for a solution to a problem who's "search domain" was relatively small (3 elements in the example). But you have brought to light something I would never have expected.