Data.* collections maintenance
daan at cs.uu.nl
Mon Oct 24 09:24:43 EDT 2005
Adrian Hey wrote:
> IIRC lookup was about 30% faster, insertion and deletion were about
> 10% slower and union was about 70% slower.
> The union used the same divide and conquer algorithm as the proper
> AVL library. This might be a case where comparison is so cheap that
> the Hedge algorithm would be a net win. But as I felt disinclined
> to write the code needed to find out for sure that is just
> speculation :-)
Note that IntMap/IntSet use big-endian patricia trees and that therefore
union is very efficient (which is good for compilers that collect for
example free variables bottom up..). i.e. The IntMap/IntSet do not
use a "hedge" algorithm whatsoever but something completely different --
and it makes no sense to compare comparisons here.
It is amazing that lookup is faster on AVL trees -- this goes against
all my intuition -- did you measure random lookups?
All the best,
> Adrian Hey
> Libraries mailing list
> Libraries at haskell.org
More information about the Libraries