Negative array indicies and slice()

[Roy Smith]

In article <mailman.3056.1351552107.27098.python-list at python.org>,
 Ian Kelly <ian.g.kelly at gmail.com> wrote:

> On Mon, Oct 29, 2012 at 9:42 AM, Andrew Robinson
> <andrew3 at r3dsolutions.com> wrote:
> > The list was generated in a single pass by many .append() 's, and then
> > copied once -- the original was left in place; and then I attempted to slice
> > it.
> 
> Note that if the list was generated by .appends, then it was copied
> more than once.  Python reserves a specific amount of space for the
> list.  When it grows past that, the list must be reallocated and
> copied.  It grows the list exponentially in order to keep the
> amortized time complexity of append at O(1), but the point is that a
> list of 20 million items is going to be resized and copied several
> times before it is complete.

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.