On Mon, Oct 29, 2012 at 5:24 PM, Roy Smith <r...@panix.com> wrote: > I think you're missing the point of "amortized constant time". Yes, the > first item appended to the list will be copied lg(20,000,000) ~= 25 > times, because the list will be resized that many times(*). But, on > average (I'm not sure if "average" is strictly the correct word here), > each item will be copied only once. > > Still, it always stuck me as odd that there's no preallocate() method. > There are times when you really do know how many items you're going to > add to the list, and doing a single allocation would be a win. And it > doesn't cost anything to provide it. I suppose, however, if you're > adding enough items that preallocating would really matter, then maybe > you want an array instead. > > (*) I don't know the exact implementation; I'm assuming each resize is a > factor of 2.
The growth factor is approximately 1.125. "Approximately" because there is also a small constant term. The average number of copies per item converges on 8. -- http://mail.python.org/mailman/listinfo/python-list