gh at ghaering.de
Mon Jun 30 15:52:56 CEST 2008
Larry Bates wrote:
> So its actually faster to append to a long list than an empty one? That
> certainly would not have been intuitively obvious now would it?
Maybe not intuitively, but if you know how dynamically growing data
structures are implemented, it's plausible. They overallocate, and the
amount of overallocation is dependent on the current size. Relevant
source snippet from Python 2.6:
/* 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, ...
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
If, on the other hand, we knew beforehand how big the list will get
approximately, we could avoid all these reallocations. No problem with
Python's C API:
PyAPI_FUNC(PyObject *) PyList_New(Py_ssize_t size);
But you can't do it directly from Python, unless you (ab)use ctypes.
More information about the Python-list