[Haskell-cafe] ANN: TernaryTrees-0.1.1.1 - An efficient
ternary tree implementation of Sets and Maps
dons at galois.com
Thu Jul 2 19:45:47 EDT 2009
> 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:
> 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, albeit indirectly.
> The real trick with tries is not in just having them, 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. 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 to
> avoid repeating the work for the prefixes of all my queries. 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?
More information about the Haskell-Cafe