Surprising (for me) benchmark results...
Martin von Loewis
loewis at informatik.hu-berlin.de
Mon May 7 07:14:34 EDT 2001
Courageous <jkraska1 at san.rr.com> writes:
> list.append() appends items to a dynamic array in O(1)+k
> constant amortized time. It does this by using a liberal preallocation
> strategy, and leaving empty slots into which new elements can
> be placed. The occasional realloc() amortizes away quite readily.
No, it doesn't. See listobject.c:ins1, in particular the line
NRESIZE(items, PyObject *, self->ob_size+1);
More information about the Python-list