in reply to Fastest way to test membership in a constant set

Bear with me because this is going to seem silly at first. What about a completely hard coded approach? From the original post, the goal seems to be speed in addtion to being constant. Why bother using hashes at all? The following subroutine should be quite a bit faster than what you have, thought I admit I haven't compared the two. 
sub IsMemeber {
  if $_[0] eq 'age' return 1;
  if $_[0] eq 'old' return 1;
  if $_[0] eq 'years' return 1; 
  return 0;
}

[download]
You could probably speed up the code even more by in-lining the if statements instead of enduring the overhead of a function call.

Replies are listed 'Best First'.
Re^2: Fastest way to test membership in a constant set
by almut (Canon) on Jul 27, 2007 at 14:44 UTC

    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)'
});

    [download]

    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%   --

    [download]

    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...).

[reply]
[d/l]
[select]
      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.
[reply]

In Section Seekers of Perl Wisdom