array, list, performance...

[Kragen Sitaker]

Ype Kingma <ykingma at accessforall.nl> writes:
> Michael Chermside wrote:
> >     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)
> 
> Append is often enough linear in the length of the list
> that growing by appending is O(len(li) * len(li)).

Not when I try it:
Python 2.1.1 (#2, Dec 19 2001, 12:19:22) 
[GCC 2.95.2 20000220 (Debian GNU/Linux)] on linux2
Type "copyright", "credits" or "license" for more information.
>>> import MetaPy.Speed
>>> def mklist(n):
...     ar = []
...     for ii in xrange(n):
...             ar.append(ii)
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(0))
1.7825510264682151e-05
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(1))
2.862680041153042e-05
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(10))
7.8054009556034588e-05
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(100))
0.00057740376706547905
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(1000))
0.0055893541133707342
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(10000))
0.055918868174255905
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(100000))
0.59515897688580466

Looks linear to me.