[Tutor] Alternatives to append() for "growing" a list

[eryksun]

On Sun, Dec 1, 2013 at 2:04 AM, Steven D'Aprano <steve at pearwood.info> wrote:
> might trigger a re-size. If the list needs to increase, it will double
> in size up to some maximum, then it will grow by a smaller amount. The
> purpose of this is that *on average* appending to the list will take a
> fixed amount of time.

Here's the over-allocation rule:

    if newsize > 0:
        const = 3 if newsize < 9 else 6
        newsize += newsize // 8 + const

Starting from empty and appending:

    0, 4,  8, 16, 25, 35, 46, 58, 72, 88

CPython's list uses realloc, which tries to resize without copying.