Balanced trees

Marko Rauhamaa marko at pacujo.net
Wed Mar 19 00:11:33 CET 2014


Dan Stromberg <drsalists at gmail.com>:

> On Tue, Mar 18, 2014 at 3:03 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
>> Dan Stromberg <drsalists at gmail.com>:
>> For a proper comparison, I'd like a fixed, identical dataset and set
>> of operations run against each data structure.
>>
>> How about this test program:
>
> I used to do essentially this, but it was time-prohibitive and
> produced harder-to-read graphs - harder to read because the enormous
> values of the bad trees were dwarfing the values of the good trees.
>
> Imagine doing 100000000 operation tests for the unbalanced binary
> tree. For a series of random keys, it would do quite well (probably
> second only to dict), but for a series of sequential keys it would
> take longer than anyone would reasonably want to wait because it's
> basically a storage-inefficient linked list.
>
> Rather than throw out unbalanced binary tree altogether, it makes more
> sense to run it until it gets "too slow".

I disagree strongly. You should throw out unbalanced binary trees and
linked lists and the like and concentrate on solid contenders.

But it's your test. You do as you like.

Anyway, even a well-thought-out test is subject to all kinds of
criticisms due to the CPU architecture, the distribution of the key
values, the quality of the data structure implementation etc etc.


Marko



More information about the Python-list mailing list