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:Bulat.Ziganshin@gmail.com