Negative array indicies and slice()
Roy Smith
roy at panix.com
Mon Oct 29 20:17:17 EDT 2012
In article <mailman.3057.1351554215.27098.python-list at python.org>,
Ian Kelly <ian.g.kelly at gmail.com> wrote:
> 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.
Wow, that's surprising. It also makes it that much more surprising that
there's no way to pre-allocate.
More information about the Python-list
mailing list