AVL trees for Data.Map and Data.Set

[Adrian Hey]

On Wednesday 01 Mar 2006 2:13 pm, Christian Maeder wrote:
> Jean-Philippe Bernardy wrote:
> > On 2/27/06, Ross Paterson <ross at soi.city.ac.uk> wrote:
> >>> We are planning to move to AVL
> >>> trees for A. Hey, which do not provide a O(1) size function.
> >>
> >> What will be gain for this move?  And what will we lose, apart from
> >> O(1) size?
> >
> > The gains:
> > 1. Christian Maeder and others report a significant performance
> > improvement. This is the main motivating factor.
>
> Indeed, the gain is significant (at least 5% lookup speedup!). Adrian
> Hey simply proved to me that AVL trees (with his clever constructor
> choice without an explicit height) are a better data structure than
> Adam's "Efficient sets: a balancing act". And it's sort of regrettable
> that the old FiniteMap and the current Data.Map are based on the latter
> (until someone finds a speedup for Adam's sets)!

Well 5% is not so wonderful IMO :-) But I guess for Maps it ain't to
bad either considering the indirection handicap suffered by AVL
(until we get type specialisation :-)

What were your keys, btw?

I think the real problems the Adams trees are..
 1 - They don't do a very good job of balancing in pathological situations
     (sorted inserts), at least as currently implemented. Though I believe
     the algortithm does have a tweekable parameter, so maybe it could
     do better if it was tweeked.
 2 - The Hedge algorithm appears to suck badly, if number of comparisons
     needed to do union etc.. is the benchmark. Even with cheap comparisons
     (Ints), AVL+divide&conquer is much faster (for Sets at least).

Regards
--
Adrian Hey