Negative array indicies and slice()
Ian Kelly
ian.g.kelly at gmail.com
Mon Oct 29 19:43:03 EDT 2012
On Mon, Oct 29, 2012 at 5:24 PM, Roy Smith <roy at 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.
More information about the Python-list
mailing list