On 29 Jan 2010, at 12:52, John Lato wrote:
There are minimal perfect hash functions; there are some libraries
mentioned here, though they are not in Haskell code:
http://en.wikipedia.org/wiki/Perfect_hash_function
This is suitable when you do a lot of lookups with few key updates.
An
alternative might be Data.Map, where lookups have time complexity
O(log n), n = size of map.
The minimal perfect hash function looks like the real algorithmic
solution, but I would just use Data.IntMap for this.
That looks interesting too. Yet another idea: use arrays
http://haskell.org/haskellwiki/Arrays
Then build a hash table, say just taking mod k n, and have values in
some lookup map. If n > set of keys, average time complexity is O(1),
and arrays should be very fast.
Hans
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
