[Tutor] why is list.pop(0) slow?

[Gregor Lingl]

Alan Gauld schrieb:

>I've been playing around with very large lists and found out by
>chance
  
>that pop(0) is 8 times slower than pop(). Is it really that bad?
>Performance improved when the list i have is reversed and used
>pop().
>
>How big are your lists? I just tried a 1 million member list and
>got no measurable difference between pop() and pop(0).
>  
>

Hi all!

I tried this out and (invariably) found the following
paradox result:

 >>> l=range(1000000)
 >>> if 1:
...     for i in range(3):
...         a=clock()
...         l.pop()
...         b=clock()
...         l.pop(0)
...         c=clock()
...         print b-a
...         print c-b
...
999999
0
0.101023984606
0.059478771889
999998
1
0.0128689504199
0.0605054383992
999997
2
0.0128781694661
0.0593547338127

which means: when done for the first time, pop() takes
approximately twice as much time as pop(0) , whereas
in all the following executions of the body of the loop
pop() is approximately five times faster than pop(0).
Notice that only the performance of pop() changes.

Aha! ??? Let's try the converse:

 >>> l=range(1000000)
 >>> if 1:
...     for i in range(3):
...         a=clock()
...         l.pop(0)
...         b=clock()
...         l.pop()
...         c=clock()
...         print b-a
...         print c-b
...
0
999999
0.14588973015
0.0120258267389
1
999998
0.065228104346
0.0120895219675
2
999997
0.0598760289713
0.0118950839017

Hmmm. So the first call of the method pop is
significantly slower than any following one. And
pop() in fact five times faster than pop(0) with
this 1000000-member-list

(Done on a 400MHz-Windows 2000 Machine)

Best wishes, Gregor