On Tue, Oct 23, 2007 at 10:10:24PM -0400, Kent Johnson wrote:
[snip]
>
> Perhaps I was a bit hasty.
>
> Lists are implemented as arrays of references. I believe they are
> - amortized O(1) for append - occasionally the list must be reallocated
> and copied
OK. I'm groping here. Wikipedia tells me that O(1) means constant
increase. So, what does "amortized O(1)" mean.
My understanding is that appending in lists is optimized in the
sense that when more space is needed, Python allocates space for
additional elements so that allocation does not need to happen at
every append. Here is a comment from the Python source code
(Python-2.5.1/Objects/listobject.c):
/* 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, ...
*/
Hmmm. There is that "amortized" thing again. Very suspicious.
For a non-math and non-financial type like me, is it sort of like
saying that the costs are averaged out over a sequence of appends?
Dave
--
Dave Kuhlman
http://www.rexx.com/~dkuhlman
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
