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.
-- Gerhard
--
http://mail.python.org/mailman/listinfo/python-list
