Kent Johnson wrote: > Dave Kuhlman wrote: >> 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? > > Yes, that is exactly right. Most of the time - when there is room at the > end of the allocated block - append is O(1) and very fast. Occasionally, > when there is not enough room, append is O(n) and slow, requiring the > entire list to be copied. Because the size of the new allocation is > proportional to the size of the list, the reallocation happens only each > 1/n appends, so if you average out the cost of the reallocation, each > append is O(1) (with a higher constant). That is what amortized cost > means - sometimes the cost is greater than the specified cost but it > averages out. > > Note that if the reallocation added a fixed amount of extra space each > time the cost would not average out over n inserts and it would not be > O(1) amortized cost. It's important that the new allocation be > proportional to the existing space. >
Actually if you would come to the point you need to make a distinction between amotized O(1) and O(1) then you will certainly be concerned with the initial amount of allocation and with the proportional constant. _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
