Am Mittwoch, 27. August 2008 17:36 schrieb Bulat Ziganshin: > 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)
Wouldn't the hashtable have lookup time O(len+bucketsize)? > > where len is length of string searched and width is average amount of > chars at each trie level _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
