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 - i.e. every char in string forms a new trie level. add to this that every search need to scan a list of all possible chars - or you need to use the same hashing. so, we have the following lookup times: trie: O(len)*O(width) hashed trie: O(len) hash: O(len) where len is length of string searched and width is average amount of chars at each trie level -- Best regards, Bulat mailto:[EMAIL PROTECTED] _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
