Balanced tree type coming in next Python?

[Kenneth McDonald]

I can't see anything about this in the notes on the upcoming
2.4 on python.org, but for some reason I thought I remembered
seeing that a balanced tree sequence type would be included
in Python in the near future. Is this correct?

Thanks,
Ken

 

[Aahz]

I can't see anything about this in the notes on the upcoming 2.4 on
python.org, but for some reason I thought I remembered seeing that a
balanced tree sequence type would be included in Python in the near
future. Is this correct?

Not to my recollection. The only references I could find to balanced
trees was in conjunction with the discussion of the heapq module.

 

[Christos TZOTZIOY Georgiou]

I can't see anything about this in the notes on the upcoming
2.4 on python.org, but for some reason I thought I remembered
seeing that a balanced tree sequence type would be included
in Python in the near future. Is this correct?

Not AFAIK (although it would be a good addition to the new collections
module).

PS Any volunteers to port and maintain Judy arrays/trees for Python?-)
http://judy.sourceforge.net/
They'd be an interesting alternative to dictionaries in some cases (esp
very large dictionaries).

 

[Phil Frost]

I'm not aware of any such feature to be added, but an AVL tree module is
available now:

http://www.nightmare.com/squirl/python-ext/avl/

 

[Thomas Guettler]

Am Mon, 07 Jun 2004 12:57:09 +0300 schrieb Christos "TZOTZIOY" Georgiou:

PS Any volunteers to port and maintain Judy arrays/trees for Python?-)
http://judy.sourceforge.net/
They'd be an interesting alternative to dictionaries in some cases (esp
very large dictionaries).

Hi,

How do they compare to BTrees (ZODB)?

Regards,
Thomas

 

[Raymond Hettinger]

[Kenneth McDonald]

I can't see anything about this in the notes on the upcoming
2.4 on python.org, but for some reason I thought I remembered
seeing that a balanced tree sequence type would be included
in Python in the near future. Is this correct?

The docs for the collections module show that balanced trees are not
going in to Py2.4 but are under consideration an a future addition to
the module.


Raymond

 

[Christos TZOTZIOY Georgiou]

How do they compare to BTrees (ZODB)?

I really don't know, to be honest; I have never used Zope's Btrees.

It's just that in some older C program of mine, with big data structures
running on a shared computer with lots of RAM but with limits per user,
I gave Judy trees a try and I was impressed by their speed and their
efficient usage of RAM. Since I was hitting my limits, before using
Judy trees I had retorted to using the C stdlib qsort and bsearch on
linear arrays (like Python lists); of course, the speed of adding
elements and re-running qsort was not impressive (no timsort in the C
stdlib .

Before using Judy trees, my program used up to 492 MiB of ram (with
careful implementation so that realloc'ing my large list would just
extend it, not copy it to another address and then freeing the old
space); with Judy trees, it used about 508 MiB, which was inside my
limit of 512, and much faster.

I haven't tried so far to port Judy trees to Python; ISTR that somebody
did an attempt using Pyrex, but never gave it a shot. Python dicts are
excellent, but memory inefficient on large amounts of data. Also, they
are not the right structure to use if you want range checks. Trees do
have their use, as you surely know.