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

Reply via email to