> From: Hans Aberg <[email protected]> > > On 28 Jan 2010, at 20:07, Steve Schafer wrote: > >> The data are currently in a large lookup table. To save space, I'd >> like >> to convert that into a sort of hash function: >> >> hash :: key -> value >> >> My question is this: Is there any kind of generic approach that can >> make >> use of the knowledge about the internal redundancy of the keys to come >> up with an efficient function? > > 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. Cheers, John _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
