wren: > Alex Mason wrote: >> TernaryTrees is a package that extends Data.Set ad Data.Map with some >> ternary tree structures, based on the article >> [http://www.pcplus.co.uk/node/3074/] . > > For the string (or rather ByteString) version: > > http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bytestring-trie > > Which has a number of other significant performance improvements (e.g. > node fusion, ByteString instead of String) and a highly expressive > interface. Because it uses ByteStrings it can trie any type which can be > serialized into a vector of bits[1], albeit indirectly. > > The real trick with tries is not in just having them[2], it's in having > the right interface to make use of what they're good at. For example, if > I have multiple tries, I'd like to merge them without doing it element > by element[3]. Or if I know I'm going to be making a number of similar > queries, it'd be nice if I could cache my position in the trie[4] to > avoid repeating the work for the prefixes of all my queries[5]. Using > tricks like these leads to significant improvements over using them like > hashtables; tries aren't hashtables just like lists aren't arrays. > >
Do you have benchmarks? _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
