array, list, performance...

[Tim Peters]

[Michael Chermside]
>     li = [x0, x1, x2, ...]
> ...
>     li.append(x)   appending is O(1)
>                    (actually, it SOMETIMES takes O(len(li)) as it
>                     resizes the list. But if you grow a list by
>                     continually appending, the amortized time is
>                     linear (ie, constant amortized time per element)

[Ype Kingma]
> Append is often enough linear in the length of the list
> that growing by appending is O(len(li) * len(li)).

[Tim]
> For Python 2.2 Michael is correct.  For Python 2.1 and earlier, you're
> correct "in theory", although in practice it was often
> linear-time anyway,> depending on internal details of the platform
> realloc.

[back to Ype]
> Good news.
> Multiplying the list's size by a constant factor when necessary would
> give O(log(len(li)) * len(li)) behaviour, so how was this made
> O(len(li)) in 2.2?

By increasing a list's size (when needed) by an amount proportional to its
current size.

> I checked 'What's new in 2.2' but found nothing about this.

Probably not.  I don't write up a news item when I optimize away a useless
branch in the code either <wink>.  Seriously, it's an internal
implementation detail, and, like I said, it often *acted* linear-time
anyway.  The only platforms I know of where it appeared to make a real
difference were assorted flavors of Windows, and some flavor of BSD Unix (I
don't recall which).  On those it helped a lot in cases of extreme list
abuse.