Surprising (for me) benchmark results...

Martin von Loewis loewis at informatik.hu-berlin.de
Mon May 7 13:14:34 CEST 2001


Courageous <jkraska1 at san.rr.com> 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);

Regards,
Martin



More information about the Python-list mailing list