Solve a Debate

[Grant Edwards]

On 2008-02-15, Ivan Van Laningham <ivanlan9 at gmail.com> wrote:

> Lookup tables are always significantly faster than a bunch of
> ifs.

Mostly always.  It depends on what you mean by "lookup table",
and it depends on how the language implements things.  If you
by "lookup table" you mean a linearly indexed array, then an
array lookup is O(1), and a series of if/then/elses is O(n).
The indexing operation is going to be faster for all practical
examples I can think of.

If by "lookup table" you mean an arbitrary mapping (e.g. a
"dict" in Python), then it depends on the hashing/searching
used to implement the lookup operation. It's possible for small
mappings using some types of keys that a series of compares
could be faster than the hashing operation.

In the general case, if the key being used consists of a lot of
bits, you might have to hash all of the bits before you can
start looking up the result. When doing compares, you can quite
after the first bit doesn't match.  IOW, you might be able to
do a lot of failed key compares in the time it takes to hash
the key.

-- 
Grant Edwards                   grante             Yow! Can you MAIL a BEAN
                                  at               CAKE?
                               visi.com