Balanced tree type coming in next Python?

Discussion in 'Python' started by Kenneth McDonald, Jun 7, 2004.

  1. 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
     
    Kenneth McDonald, Jun 7, 2004
    #1
    1. Advertising

  2. Kenneth McDonald

    Aahz Guest

    In article <.2wire.net>,
    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?


    Not to my recollection. The only references I could find to balanced
    trees was in conjunction with the discussion of the heapq module.
    --
    Aahz () <*> http://www.pythoncraft.com/

    "as long as we like the same operating system, things are cool." --piranha
     
    Aahz, Jun 7, 2004
    #2
    1. Advertising

  3. On Mon, 07 Jun 2004 04:45:13 GMT, rumours say that Kenneth McDonald
    <> 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
     
    Christos TZOTZIOY Georgiou, Jun 7, 2004
    #3
  4. Kenneth McDonald

    Phil Frost Guest

    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
     
    Phil Frost, Jun 7, 2004
    #4
  5. 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
     
    Thomas Guettler, Jun 7, 2004
    #5
  6. [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
     
    Raymond Hettinger, Jun 7, 2004
    #6
  7. On Mon, 07 Jun 2004 16:46:06 +0200, rumours say that "Thomas Guettler"
    <> 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
     
    Christos TZOTZIOY Georgiou, Jun 8, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Luc The Perverse

    Balanced Tree

    Luc The Perverse, Feb 20, 2006, in forum: Java
    Replies:
    8
    Views:
    784
    Chris Uppal
    Feb 22, 2006
  2. Steve Holden

    PyCon is Coming! PyCon is Coming!

    Steve Holden, Jan 5, 2006, in forum: Python
    Replies:
    0
    Views:
    336
    Steve Holden
    Jan 5, 2006
  3. Replies:
    7
    Views:
    903
  4. Deniz Bahar
    Replies:
    2
    Views:
    517
    Andrey Tarasevich
    Mar 9, 2005
  5. Replies:
    1
    Views:
    338
Loading...

Share This Page