[Python-Dev] Dictionary sparseness

[Agthorr]

On Sun, May 11, 2003 at 09:47:33PM -0400, Tim Peters wrote:
> Possibly, but it's fraught with difficulties.  For example, Python dicts can
> be indexed by lots of things besides 8-bit strings, and you generally need
> to know a great deal about the internal structure of a key type to generate
> a sensible hash function.  

> A more fundamental problem is that minimality can be harmful when
> failing lookups are frequent: a sparse table has a good chance of
> hitting a null entry immediately then, but a minimal table never
> does.  In the former case full-blown key comparison can be skipped
> when a null entry is hit, in the latter case full-blown key
> comparison is always needed on a failing lookup.

Both good observations.

> For symbol table apps, Bentley & Sedgewick rehabilitated the idea of ternary
> search trees a few years ago, and I think you'd enjoy reading their papers:
> 
>     http://www.cs.princeton.edu/~rs/strings/
> 
> In particular, they're faster than hashing in the failing-lookup case.

hhmmm.. yes, those are interesting.  Thanks :-) A few months ago I
implemented suffix trees for fun and practice.  Suffix trees are based
on tries, and I used a binary-tree for each node to keep track of its
children (which the papers point out is an equivalent way of doing
ternary trees).

(Suffix trees let you input a set of strings of total length n.  This
has a cost of O(n) time and O(n) memory.  Then, you can look to see if
a string of length m is a substring of any of the strings in the set
in O(m) time; this is impressive since the number and size of the set
of strings only matters for the setup operation; it has no effect on
the lookup speed whatsoever.)

Ternary search trees seem like a good approach for string-only
dictionaries.  These seem like an inelegant optimization that might
yield performance improvements for places where non-string keys are
syntactically disallowed anyway (such as the members of a class or
module).

-- Agthorr