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