Red Black Tree implementation?
Dan Stromberg
drsalists at gmail.com
Thu May 2 13:04:07 EDT 2013
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>
More information about the Python-list
mailing list