array, list, performance...

[Ype Kingma]

Tim Peters wrote:
> 
> [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)).
> 
> 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.

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?
I checked 'What's new in 2.2' but found nothing about this.

Regards,
Ype