Data.* collections maintenance

[Daan Leijen]

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,
-- Daan.

> 
> Regards
> --
> Adrian Hey
> 
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries