Solve a Debate

[greg]

Wolfgang Draxinger wrote:

> Somehow you seem to think, that a lookup table will require more
> resources (memory I guess you thought) than a sequence of
> comparisons. However you didn't take into account, that the
> program code itself requires memory, too (for the operation
> codes).

In Python, there's the additional twist that for
lookup tables based on a mutable type, such as a
dictionary, you need to execute code to build the
dictionary. So you end up using very roughly twice
the memory -- for the code to build the dictionary,
and the dictionary itself.

If the dictionary isn't too huge, and it's looked
up many times during each run of the program, the
extra speed of the dict lookup is probably worth
the overhead of creating it.

If the dict is very large, and is consulted
relatively few times in a given run, then it might
well be faster and not use too much more memory to
use a tree (NOT a linear sequence!) of if-else
statements in the code.

You could also consider loading the dict from some
other form, such as a pickle, instead of creating
it using code. This would use less memory, although
probably would take roughly the same time to set
up the table.

For extremely large infrequently-used tables, it's
probably better to look at not loading the whole
table into memory at all, and keeping it in some
kind of external indexed structure such as a b-tree,
relational database, etc.

In other languages, the tradeoffs will be completely
different. E.g. in C, if you can describe the table
entirely with static data, it'll be very fast to
load and incur no overhead for code to create it at
all. Also, with demand-paging out of the executable
file, and infrequent lookups, only parts of the
table will actually get loaded anyway.

-- 
Greg