[Haskell-cafe] lookup tables & style guidelines
ahey at iee.org
Thu Apr 24 11:33:55 EDT 2008
Ketil Malde wrote:
> Don Stewart <dons at galois.com> writes:
>>> 1) what is the most performant lookup table/hashtable/dictionary solution
>>> for Haskell?
>> Data.IntMap is awfully good.
> Is it benchmarked anywhere? Compared to the Judy bindings, or Adrian
> Hey's AVL trees, or Data.Hashtable?
I must get around to putting the AVL clones of Data.Map/Set in Hackage
sometime. Meanwhile anyone wanting to roll their own maps with an API
of their chosing could do a lot worse than the raw AVL lib..
Also, if you're likely to be using union/intersection a lot you should
know that Data.Map/Set are very slow for this because they use the
not efficient hedge algorithm :-)
There's a really cool demo I found from wikipedia that shows why it is
that AVL trees perform so well in the "pathological" situation of sorted
If you try it you can see that after 2^n-1 sorted insertions you always
get a perfectly balanced tree. This explains these benchmark results..
DData is what became Data.Map/Set and it would appear to be the worst
performing of the four tree types tested there :-(
Don is right about Data.IntMap/IntSet. For Ints it will be much faster
than Data.Map/Set or even (polymorphic) AVL tree. But an AVL tree of
unboxed Ints gives faster lookup than IntMap/Set and about the same
Union and Intersection times for AVL aren't so great, but I think
I know what to do about that (especially intersection).
But the real way ahead has to be Tries for non-trivial keys and (I
suspect) AVL trees of unboxed Ints for simple keys (serialisable
as 1 machine word). This is what that GSoC project is all about.
At the moment we have the exact opposite, Tries for Ints and balanced
trees for non-trivial keys. Oh well..
More information about the Haskell-Cafe