Re: AVL trees for Data.Map and Data.Set

On Wednesday 01 Mar 2006 2:13 pm, Christian Maeder wrote:

Jean-Philippe Bernardy wrote:

...

On 2/27/06, Ross Paterson 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