Balanced tree type coming in next Python?

Christos TZOTZIOY Georgiou tzot at sil-tec.gr
Tue Jun 8 11:12:53 CEST 2004


On Mon, 07 Jun 2004 16:46:06 +0200, rumours say that "Thomas Guettler"
<guettli at 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



More information about the Python-list mailing list