On Tue, Mar 18, 2014 at 1:55 PM, Marko Rauhamaa <ma...@pacujo.net> wrote: > Dan Stromberg <drsali...@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 -- https://mail.python.org/mailman/listinfo/python-list
