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

Groups > comp.lang.python > #44618 > unrolled thread

Re: Red Black Tree implementation?

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Red Black Tree implementation? Christian Heimes <christian@python.org> - 2013-05-02 12:46 +0200

#44618 — Re: Red Black Tree implementation?

Am 02.05.2013 01:11, schrieb Dan Stromberg:
> 
> What's the best Red Black Tree implementation for Python with an
> opensource license?
> 
> I started out looking at
> http://newcenturycomputers.net/projects/rbtree.html
> <http://newcenturycomputers.net/projects/rbtree..html> because it was
> pretty high in Google and had the operators I wanted, but it gets very
> slow at about half a million elements.  I've been discussing this with a
> C programmer who believes that Red Black Trees should perform very
> similarly to an AVL tree, but that's not at all what I'm getting with
> the newcenturycomputers implementation.

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.

Christian

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web