Hello, I enclose a copy of some results I posted in a c.l.f thread FYI..

Adrian Hey wrote:

...

It would be nice to have some data for other tree types too, like red-black trees maybe.

Malcolm Wallace sent me some code for red-black and 234 trees which is used in nhc98 compiler. It contains no set operations, or even delete, but I thought it would be interesting to see how these compared with my own AVL implementation and DData.Set (weight balanced) for simple insert, lookup (and delete if available).

So here are my results for trees of 500000 Int elements (execution times and comparison counts) for ordered data and random data.

Ordered Data (times in mS) AVL DData.Set RedBlack 234 ------------------------------------------- Insert 150 366 217 255 Lookup 53 76 116 114 Delete 126 135 --- ---

Ordered Data (Comparisons) AVL DData.Set RedBlack 234 ---------------------------------------------- Insert 8975713 15689425 12668235 13167977 Lookup 8975732 9166555 9132570 9132601 Delete 6785282 6612512 --- ---

Random Data (times in mS) AVL DData.Set RedBlack 234 ------------------------------------------- Insert 763 1003 815 852 Lookup 153 181 224 215 Delete 803 ??? --- ---

Random Data (Comparisons) AVL DData.Set RedBlack 234 ---------------------------------------------- Insert 8953286 9155823 9104153 9106882 Lookup 9184653 9418309 9331310 9332922 Delete 8229843 8405601 --- ---

Notes: * These figures are for the entire test (not per element). The timing measurements are averaged over 10 runs (same test data each run). * The Insert test constructs a tree by inserting a list of Ints into an empty tree. * The Lookup test checks each Int in the original list is a member of the set (in the same order that they appear in the list). * The Delete test deletes each element from the set successively, resulting in an empty set (in the order they appear in the original list). * There are no results for deletion from RedBlack or 234 trees (because these functions don't exist :-) * There is no timing result for deletion of random data from DData.Set because the test segfaults???. But only with random data and only when I try to time it, not with ordered data and not if I just count comparisons. Ermm..

The actual execution times may be suspect (a lot will depend on implementation details, so they don't necessarily reflect on the algorithm).

But the comparison counts tell us something. DData.Set, RedBlack, and 234 all seem to be struggling with insertion of ordered data, but for AVL it makes virtually no difference. I think my earlier remark about the AVL algorithm being difficult to improve on is justified by these results.

So I still say AVL is a darned good algorithm that takes a lot of beating in practice. But I'd still be interested in being proven wrong :-)

Regards -- Adrian Hey