[Haskell-cafe] Pure hashtable library
jules at jellybean.co.uk
Wed Aug 27 11:59:55 EDT 2008
Bulat Ziganshin wrote:
> Hello Jules,
> Wednesday, August 27, 2008, 7:21:46 PM, you wrote:
>>> given these constraints, it should be just a 10-20 lines of code, and provide much better efficiency than any tree/trie implementations
>> Prove it.
>> To get "much better efficient" than a trie, the hash function has to be
>> so fast that it is faster than following (log n) pointers
> afaiu, trie search follows n pointers
"n" is the number of strings in my data set (dictionary).
If I have "n" strings the average string length is asymptotically, in
some sense, "log n". Of course for particular data sets it's may be more .
But "log n" is the length of the shortest unique coding, it's also the
number of characters you typically need to traverse before you have
reached a unique prefix, at which point your trie can short-circuit.
I appreciate that I didn't define my terminology ;) You might have a
I repeat my challenge "Prove it". I will be interested to see how much a
good immutable hash outperforms Data.Map.
I would then also be interested to see how much it outperforms a decent
Data.Map (such as your own AVL one) and a decent trie.
More information about the Haskell-Cafe