Negative array indicies and slice()

[Ian Kelly]

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.