Negative array indicies and slice()

[Roy Smith]

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.