Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Balanced tree type coming in next Python?

Reply
Thread Tools

Balanced tree type coming in next Python?

 
 
Kenneth McDonald
Guest
Posts: n/a
 
      06-07-2004
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
 
Reply With Quote
 
 
 
 
Aahz
Guest
Posts: n/a
 
      06-07-2004
In article <(E-Mail Removed).2wir e.net>,
Kenneth McDonald <(E-Mail Removed)> 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 ((E-Mail Removed)) <*> http://www.pythoncraft.com/

"as long as we like the same operating system, things are cool." --piranha
 
Reply With Quote
 
 
 
 
Christos TZOTZIOY Georgiou
Guest
Posts: n/a
 
      06-07-2004
On Mon, 07 Jun 2004 04:45:13 GMT, rumours say that Kenneth McDonald
<(E-Mail Removed)> 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
 
Reply With Quote
 
Phil Frost
Guest
Posts: n/a
 
      06-07-2004
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


 
Reply With Quote
 
Thomas Guettler
Guest
Posts: n/a
 
      06-07-2004
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

 
Reply With Quote
 
Raymond Hettinger
Guest
Posts: n/a
 
      06-07-2004
[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
 
Reply With Quote
 
Christos TZOTZIOY Georgiou
Guest
Posts: n/a
 
      06-08-2004
On Mon, 07 Jun 2004 16:46:06 +0200, rumours say that "Thomas Guettler"
<(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Trying to determing if n-ary tree is balanced. cgirl C++ 1 06-26-2009 05:32 AM
Determining if an n-ary tree is balanced or not. cgirl C Programming 1 06-26-2009 03:03 AM
arranging items in memory as multimap(balanced tree) kasthurirangan.balaji@gmail.com C++ 1 08-23-2008 12:13 PM
Balanced Tree Luc The Perverse Java 8 02-22-2006 12:51 PM
Balanced binary tree with fixed leaf nodes abhrajit@hotmail.com C Programming 7 03-09-2005 11:01 PM



Advertisments