Balanced trees

[Dan Stromberg]

On Tue, Mar 18, 2014 at 1:55 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
> Dan Stromberg <drsalists at gmail.com>:
>
>> The results are at
>> http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/2014-03/
>
> Unfortunately I'm having a hard time understanding the results.
>
> The 50/50 get/set ratio is most interesting to me.
>
> I'm seeing (under cpython-3.3):
>
>
>     Size: 1048576, duration:  75.3, dictionary type: dict
>     [...]
>     Size:  262144, duration:  66.1, dictionary type: AVL_tree
>     [...]
>     Size:   65536, duration:  77.3, dictionary type: blist.sorteddict
>
>
> What does it mean?

dict was able to do 1048576 operations on a dictionary before taking
more than 120 seconds to complete - it took 75.3 seconds to do 1048576
operations.

AVL_tree was able to do 262144 operations on a dictionary before
taking more than 120 seconds to complete - it took 66.1 seconds to do
262144 operations.

blist.sorteddict was able to do 65536 operations on a dictionary
before taking more than 120 seconds to complete  - it took 77.3
seconds to do 65536 operations.

For the 50/50 workload; the "operations" were half adding key, value
pairs; and half lookups of values by keys we know are in the
dictionary.

I used to run all the dictionaries for as long as it took to do 4
million operations, but for (EG) unbalanced binary trees, that would
take far too long in the ordered tests, so I changed the code to try a
given tree type until the time for an operation became prohibitive.

If you look at the graphs (I have to admit they've become a little
cluttered), you can see the slower trees "escaping" rapidly (exceeding
the 120 second threshold), while the better performing trees grow more
slowly and are allowed to continue proving themselves longer.
Inspecting these graphs may help in developing an intuition for how
the tests were conducted.

The code implementing this method of testing is in
http://stromberg.dnsalias.org/svn/python-tree-and-heap-comparison/trunk/tester

HTH