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
No.
"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
different "n".
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.
Jules
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
