Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #44641

Re: Red Black Tree implementation?

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

On Thu, May 2, 2013 at 3:46 AM, Christian Heimes <christian@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.

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-02 10:04 -0700

csiph-web