bulat.ziganshin: > 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) >
Seems like you can make a pure hashtable by unsafePerformIO on the impure one, and exporting only 'lookup'.. -- Don _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
