[Python-Dev] collections.sortedtree

[Marko Rauhamaa]

Raymond Hettinger <raymond.hettinger at gmail.com>:

> * An AVL balanced tree isn't the only solution or necessarily the best
> solution to the problem. Tree nodes tend to take more space than
> denser structures and they have awful cache locality (these are the
> same reasons that deques use doubly-linked blocks rather than a plain
> doubly linked lists).

Maybe. The key is the API. The implementation underneath should be
changeable. For example, Jython would probably use SortedTree to
implement it.

Performance tests should help decide when an implementation is switched
for a more efficient one. In some of my tests, I haven't seen any
significant performance differences between RB trees and AVL trees, for
example. The blist implementation, which I have taken a quick glance at,
buys cache locality at the price of block copying; I have no data to
decide if the tradeoff is a good one.

The main thing, IMO, is to get one sorted dictionary in.

> * The name of the tool probably should not be sortedtree.

Correct. That was a mistake on the Subject line. In the code, it's
sorteddict.

> * That said, it is a reasonable possibility that the standard library
> would benefit from some kind sorted collection (the idea comes up from
> time to time).

Yes. As a user, I have craved for an implementation, which is readily
available in Java and the linux kernel, for example.


Marko