Adrian Hey ahey at iee.org
Mon May 17 10:39:25 EDT 2004

On Monday 17 May 2004 6:14 am, ajb at spamcop.net wrote:
> G'day all.
> Quoting Adrian Hey <ahey at iee.org>:
> > I've just been trying some simple benchmarks of my AVL implementation vs.
> > current FiniteMap implementation and using AVL trees seems to about twice
> > as fast for insertion. On my machine building an AVL tree of 1000000
> > (key,value) pairs takes about 5 seconds, whereas the same takes about 10
> > seconds with FiniteMap (the keys are Ints for this test).
> Just curious: Have you timed deletions?

I've just tried that yesterday. Here are the results for 2 tests..

Test1: Build a tree/finitemap of 1000000 pairs.
Test2: As Test1, followed by deletion of all 1000000 pairs.

Pairs are inserted/deleted in numerical order [1,2..1000000]
Times are in seconds. There seems to be some variability in
timing measusrements (about +/- 5%), so the following figures
are averages over a few runs. 

		AVL	FiniteMap
Test1:		5.2	 9.5
Test2:		8.3	13.4
Test2-Test1:	3.1	 3.9

Not so much difference for deletion. Strangely, for both AVL and FiniteMap,
deletion seems to be faster than insertion. I'm not sure what's going on here.

Anyway, I'll try to post my AVL library (and the code for the above tests)
as it currently stands somewhere today (it's not finished though).

Adrian Hey

More information about the Libraries mailing list