Strange timing data for list.pop()

Roy Smith roy at
Sun Aug 1 13:17:05 EDT 2004

In the recent "transforming a list into a string" thread, we've been 
discussing the fact that list.pop() is O(1), but list.pop(0) is O(n).  I 
decided to do a little timing experiment.  To be sure, I did verify 
experimentally the expected result, but along the way, I came upon an 
interesting artifact that I'm at a loss to explain.

I used the following to generate some timing numbers for pop() on 
various sized lists:

import time
for power in range (20):
    i = 2 ** power
    list = [1] * i
    t0 = time.time ()
    list.pop ()
    t1 = time.time ()
    t = t1 - t0
    print i, t

I know wall clock time isn't a good way to time things, but it was a 
first cut before I dove into the manual and found os.times().  The 
interesting thing is the data that I got with the above code:

1 7.70092010498e-05
2 6.91413879395e-06
4 5.96046447754e-06
8 5.00679016113e-06
16 5.00679016113e-06
32 5.00679016113e-06
64 5.00679016113e-06
128 5.00679016113e-06
256 4.05311584473e-06
512 5.00679016113e-06
1024 5.00679016113e-06
2048 5.96046447754e-06
4096 9.05990600586e-06
8192 9.05990600586e-06
16384 9.05990600586e-06
32768 1.4066696167e-05
65536 2.31266021729e-05
131072 3.09944152832e-05
262144 3.60012054443e-05
524288 3.38554382324e-05

I plotted the data.

An interesting shaped curve!  I haven't done any curve fitting, but by 
eye it looks something like k - log (1/n).  The data is quite 
repeatable, too.  Admitting that clock time is a silly thing to be 
measuring here, anybody have any clue what might be causing this 

This is on an otherwise idle 768 Mbyte PowerBook running OSX-10.3.4 and 
Python 2.3.4.

More information about the Python-list mailing list