Memory overhead for trees?

Aahz aahz at
Tue Aug 20 05:21:54 CEST 2002

In article <mailman.1029501804.17427.python-list at>,
=?iso-8859-1?q?Fran=E7ois?= Pinard <pinard at> wrote:
>> I think the memory savings afforded by tuples probably makes a fair bit
>> of sense, and I think the Timbot would concur based on comments it has
>> made in the past.
>If I read you correctly, you assert that tuples are significantly more
>economical than lists?  I know they are, but I thought it was essentially
>because of an indirect pointer from the object to a separately allocated
>array, plus some more overhead for the management of that array with the
>mallocator.  I guess it doubles (or so) the memory requirements for nodes
>that are binary, and might be less important for nodes having many children.

With any luck, Tim won't correct me, but I think one of the big memory
wasters with lists is the overallocation of the pointer vector to avoid
O(N^2) on list.append().
Aahz (aahz at           <*>

Project Vote Smart:

More information about the Python-list mailing list