Memory overhead for trees?

[Aahz]

In article <mailman.1029501804.17427.python-list at python.org>,
=?iso-8859-1?q?Fran=E7ois?= Pinard <pinard at iro.umontreal.ca> wrote:
>[Aahz]
>>
>> 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 pythoncraft.com)           <*>         http://www.pythoncraft.com/

Project Vote Smart: http://www.vote-smart.org/