Surprising (for me) benchmark results...

Martin von Loewis loewis at
Mon May 7 07:14:34 EDT 2001

Courageous <jkraska1 at> writes:

> NO.
> 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 mailing list