Memory overhead for trees?
aahz at pythoncraft.com
Tue Aug 20 05:21:54 CEST 2002
In article <mailman.1029501804.17427.python-list at python.org>,
=?iso-8859-1?q?Fran=E7ois?= Pinard <pinard at iro.umontreal.ca> 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 pythoncraft.com) <*> http://www.pythoncraft.com/
Project Vote Smart: http://www.vote-smart.org/
More information about the Python-list