While there may be a discussion somewhere in the archives, the comments in listobject.c are enlightening too.
/* Ensure ob_item has room for at least newsize elements, and set
* ob_size to newsize. If newsize > ob_size on entry, the content
* of the new slots at exit is undefined heap trash; it's the caller's
* responsiblity to overwrite them with sane values.
* The number of allocated elements may grow, shrink, or stay the same.
* Failure is impossible if newsize <= self.allocated on entry, although
* that partly relies on an assumption that the system realloc() never
* fails when passed a number of bytes <= the number of bytes last
* allocated (the C standard doesn't guarantee this, but it's hard to
* imagine a realloc implementation where it wouldn't be true).
* Note that self->ob_item may change, and even if newsize is less
* than ob_size on entry.
*/
[...]
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
"linear-time amortized behavior" (i.e., that list.append() is O(1) on average)
is the important characteristic you're probably looking for.
CVS source for listobject.c can be seen here:
http://cvs.sourceforge.net/viewcvs.py/python/python/dist/src/Objects/listobject.c?rev=2.227&view=markup
Jeff
pgp4hldyPHMvN.pgp
Description: PGP signature
-- http://mail.python.org/mailman/listinfo/python-list
