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@haskell.org http://www.haskell.org/mailman/listinfo/libraries