On Monday 24 Oct 2005 2:24 pm, Daan Leijen wrote:
It is amazing that lookup is faster on AVL trees -- this goes against all my intuition -- did you measure random lookups?
Yes, I've just run the benchmarks again (with ghc 6.4), results for maps of 500000 random Ints are (time in no particular units).. Data.IntMap AVL.IntMap Insert 214.0 227.0 Lookup 146.6 104.8 Delete 253.0 254.0 Union 66.0 96.0 Intersection 15.0 41.0 However, I seem to recall somebody finding a bug somewhere in Data.IntMap a while ago. I'm not sure if that's the case, but if so in may be influencing the timings, for better or worse. Can anybody enlighten me about that? (or refute this allegation :-) I can supply AVL.IntMap code and benchmark code if anybody's interested. Regards -- Adrian Hey