Benchmarking (again:-)
Adrian Hey
ahey at iee.org
Sat Sep 11 10:04:57 EDT 2004
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
More information about the Libraries
mailing list