[Haskell-cafe] trees and pointers
wren ng thornton
wren at freegeek.org
Fri Jul 16 10:05:22 EDT 2010
Jan-Willem Maessen wrote:
> As you observe, it's really down to constant factors. The reason
> IntMap (or any digital trie) is so interesting is that it is simple
> enough that the constant factors are quite good---in particular we
> don't waste a lot of time figuring out if we're going to need to
> rearrange the tree structure on the fly. That turns out to amortize
> quite a few extra level traversals in a lot of settings.
This simplicity of not rebalancing also allows for more sharing in a
persistent setting, which can be a big gain for programs with the right
kinds of data distributions.
> It also offers really elegant implementations of union and unions.
> Whether that means they're quickish I leave to the benchmarkers.
In my experience (NLP work), the performance of unions for tries is one
of their major selling points. In Okasaki's venerable benchmarks[1],
they vastly outperform all competitors for merging. Even in
imperative-land, that's one of the reasons tries are so common in NLP
and are often chosen over hashmaps for certain tasks.
[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452
--
Live well,
~wren
More information about the Haskell-Cafe
mailing list