AVL trees for Data.Map and Data.Set
ahey at iee.org
Wed Mar 1 10:46:50 EST 2006
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).
More information about the Libraries