[Python-Dev] collections.sortedtree (original) (raw)

Marko Rauhamaa marko at pacujo.net
Fri Mar 28 22:54:32 CET 2014

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

More information about the Python-Dev mailing list