Strange timing data for list.pop()
Roy Smith
roy at panix.com
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. http://www.panix.com/~roy/pop-times.png
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
behavior?
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