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

Groups > comp.lang.python > #44618

Re: Red Black Tree implementation?

Show key headers only | View raw

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

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

Thread

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

csiph-web