no shift/unshift?

[Geert-Jan Van den Bogaerde]

On Sun, 2003-02-23 at 00:12, Michael P. Soulier wrote:

[snipped]

> [msoulier at piglet msoulier]$ ./bench.py 
> Finished first loop in 8.207944 seconds.
> Finished second loop in 10.413478 seconds.
> [msoulier at piglet msoulier]$ ./bench.py 
> Finished first loop in 8.146216 seconds.
> Finished second loop in 9.120505 seconds.
> [msoulier at piglet msoulier]$ ./bench.py 
> Finished first loop in 9.507626 seconds.
> Finished second loop in 9.125624 seconds.
> 
>     Well, the second loop takes longer to be sure, but not by much. 

However, if you change:

list = range(10)

to

list = range(1000)

then the difference becomes clear (as every insert(0, i) has to move all
of the elements in the 1000-element list now):

geertjan at laptop:~$ python bench2.py 
Finished first loop in 2.943900 seconds.
Finished second loop in 7.962315 seconds.

Just to be sure, changing it to 10000 gives:

geertjan at laptop:~$ python bench3.py 
Finished first loop in 2.956296 seconds.
Finished second loop in 44.566834 seconds.

The version using insert runs in O(n) where n in the number of elements in the list,
while the append version runs in constant time.

Geert-Jan