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 -- http://mail.python.org/mailman/listinfo/python-list