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]

In article <sl*******************************@g4.gateway.2wir e.net>,
Kenneth McDonald <ke****************@sbcglobal.net> wrote:

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.
--
Aahz (aa**@pythoncraft.com) <*> http://www.pythoncraft.com/

"as long as we like the same operating system, things are cool." --piranha

[Christos TZOTZIOY Georgiou]

On Mon, 07 Jun 2004 04:45:13 GMT, rumours say that Kenneth McDonald
<ke****************@sbcglobal.net> might have written:

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).
--
TZOTZIOY, I speak England very best,
"I have a cunning plan, m'lord" --Sean Bean as Odysseus/Ulysses

[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/

On Mon, Jun 07, 2004 at 04:45:13AM +0000, Kenneth McDonald wrote:

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

[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]

On Mon, 07 Jun 2004 16:46:06 +0200, rumours say that "Thomas Guettler"
<gu*****@thomas-guettler.de> might have written:

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).

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.
--
TZOTZIOY, I speak England very best,
"I have a cunning plan, m'lord" --Sean Bean as Odysseus/Ulysses