Red Black Tree implementation?

[Dan Stromberg]

On Thu, May 2, 2013 at 3:46 AM, Christian Heimes <christian at python.org>wrote:

> Am 02.05.2013 01:11, schrieb Dan Stromberg:



> No wonder it's getting slow and doesn't stand a change against Python's
> dict implementation. The rbtree implementation from
> newcenturycomputers.net is written entirely in Python. It's good code
> for academic research in order to study the properties of a rbtree.
>
> If you need something production ready then you have to use an
> implemetation with an optimized backend like a C code, PyPy or Cython.


The newcenturycomputers RBTree is similarly slow on CPython 2.x, CPython
3.x, PyPy and Jython.   I imagine the tree depth is getting deeper than it
should, but I've not verified that.  Also, the other datastructures I'm
comparing it to: B+ Tree, AVL Tree, Treap, etcetera are pure python too,
but they're performing reasonably - in fact, my expectations are pretty
much defined by these.

(OK, the treap code has a Cython version, but I'm not using that in this
project)

Thanks for the response.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20130502/38ad4259/attachment.html>