[Haskell] Re: performance tuning Data.FiniteMap

[ajb at spamcop.net]

G'day all.

Quoting oleg at pobox.com:

> 	If indeed the read performance is at premium and updates are
> infrequent, by bother with ternary etc. trees -- why not to use just a
> single, one-level array. Given a reasonable hash function, the
> retrieval performance is O(1).

Ah, but key comparison and computing the hash function is _not_ an O(1)
operation for keys of non-fixed-size.  At the very least, it's O(k) where
k is the length of the key.  If you have a perfect hash function, and you
know that you are not searching for elements which are not in the set,
hash searching will take precisely one scan through the whole key.

Radix searching, on the other hand, only needs to scan through as much of
the key as is necessary to discriminate between them.  Plus, even if you
need to search for keys which are not in the set, it takes at most one
pass through the key, as opposed to at least two for hashing.

If constant factors matter, and your keys are appropriately decomposable,
I would recommend radix searching over hashing any day.

Cheers,
Andrew Bromage