[Python-Dev] collections.sortedtree

Dan Stromberg drsalists at gmail.com
Mon Mar 31 23:46:04 CEST 2014


vne
On Mon, Mar 31, 2014 at 2:01 PM, Daniel Stutzbach <stutzbach at google.com> wrote:
> On Fri, Mar 28, 2014 at 6:45 PM, Dan Stromberg <drsalists at gmail.com> wrote:
>>
>> In my testing blist.sorteddict was dead last for random keys, and
>> wasn't last but was still significantly underperforming for sequential
>> keys (outperforming only binary tree and scapegoat tree, behind all
>> others):
>>
>>
>> http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/2014-03-18/
>
>
> Could you post the source code for your test tools, so that I can reproduce
> them locally and understand the results better?
>
> I think I'm confused about what you're trying to measure.  It looks like the
> tests perform get and set operations, neither of which required a sorted
> dict.  Wouldn't a good comparison of sorted dict types include at least one
> operation that relies on the sorted property?  Possibly I've misunderstood
> how your tests work.

The code is at http://stromberg.dnsalias.org/svn/python-tree-and-heap-comparison/trunk/

You're right, I'm not comparing find_min, find_max, generate_in_order
or generate_reverse_order.  The first two tend to be the same as
find_arbitrary.

I've been thinking about trying to import some C extension module
trees, and just ignoring them if they fail to import.  But I haven't.

Trunk only compares pure python implementations - even for treap,
which has a cython version.  I tossed my changes after checking blist.

Trunk does operations/second.


More information about the Python-Dev mailing list