[Python-Dev] collections.sortedtree (original) (raw)
Dan Stromberg drsalists at gmail.com
Wed Mar 26 23:47:31 CET 2014
- Previous message: [Python-Dev] On the necessity of PEPs [was "collections.sortedtree"]
- Next message: [Python-Dev] collections.sortedtree
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
On Wed, Mar 26, 2014 at 1:55 PM, Benjamin Peterson <benjamin at python.org> wrote:
On Wed, Mar 26, 2014, at 13:31, Marko Rauhamaa wrote:
I have made a full implementation of a balanced tree and would like to know what the process is to have it considered for inclusion in Python 3. It's not a bad idea. (I believe others have proposed an red-black tree.) Certainly, it requires a PEP and a few months of bikesheding, though.
I'd recommend a plain binary tree (for random keys), red-black tree and treap (both for ordered or mostly-ordered keys, where red-black tree gives low operation duration standard deviation, and treap gives low average operation duration).
https://en.wikipedia.org/wiki/Binary_search_tree#Performance_comparisons http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/
It'd likely make sense to have either a pure python implementation, or pure python and C-extended, so that Pypy and Jython can share the feature with CPython.
- Previous message: [Python-Dev] On the necessity of PEPs [was "collections.sortedtree"]
- Next message: [Python-Dev] collections.sortedtree
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]