Hello Richard, Thursday, August 28, 2008, 5:28:46 AM, you wrote:
>>> trie: O(len)*O(width) >>> hashed trie: O(len) >>> hash: O(len) > If "width" here refers to the branching factor of the trie, > it's actually O(len.lg(width)), and the width that matters > is not the *possible* number of choices but the *actual* > number. i thought about using list to hold all variations at the trie node. with a (balanced) tree at each node we will have even more overheads > The great problem with hash tables is devising good hash > functions. There is a vast literature about hash tables, > but there is very little about how to design good hash > functions for anything other than numbers and maybe strings. 1. tries also work only for strings and other lists 2. i don't want to go into discussing well-known pluses and minuses of data structures. my point was just that we have great alternative to trees/tries which should be implemented many years ago. i've used a lots of assoclists in my program, sometimes this really degraded performance (although it's yet another question - why tree/trie structures doesn't provide simple List.lookup replacement function and why i'm so lazy to still not learning their APIs) -- Best regards, Bulat mailto:[EMAIL PROTECTED] _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe