Python Running Time Experiments
Image source: Ex Machina

Python Running Time Experiments

I have just (re)started the MIT OCW 6.006, and during the discussion of different algorithms decided to check what are real run-times for different commonly used methods on my machine. Continue reading to see the results…

The original code is located here. There are minor changes to the code, and the modified version and the results are located on GitHub.

Let me know if you find any inconsistencies!


All experiments are run on MacBook Pro (Retina, 13-inch, Late 2013) on 2.4 GHz Intel Core i5 with 8 GB 1600 MHz DDR3 using Python 2.7.12.

For every test, timeit module was used to find the run time of function under test. The parameters for the test are generated given some bounds, and the result is fit to the best guess. Difference in the results is caused by background processes (source).

Here is an example of a run

print "Test List-1: create an empty list"
spec_string = "1<=n<=10"
growth_factor = 2
print "Spec_string: ",spec_string, "by factors of", growth_factor
var_list, param_list = make_param_list(spec_string,growth_factor)
# f_list = ("n","1")
f_list = ("1",)
run_times = []
trials = 1000
for D in param_list:
  t = timeit.Timer("x = list()")

The raw and formatted results:

Test List-1: create an empty list
Spec_string:  1<=n<=10 by factors of 2
var_list ['n']
Function list: ('1',)
run times:
n =      1 : 0.125885 microseconds
n =      2 : 0.125885 microseconds
n =      4 : 0.124931 microseconds
n =      8 : 0.124931 microseconds
Coefficients as interpolated from data:
(measuring time in microseconds)
Sum of squares of residuals: [  5.78285384e-05]
RMS error = 0.38 percent
Operation Description Asymptotic Real (s) Error (%)
list() Create empty list 0.38


is the variable number of elements - could be number of digits in a number number of elements in an array, etc., while

Real values are rounded!!!


Operation Description Asymptotic Real (s) Error (%)
int('1'*n) String to Integer1 1.9
repr(2**n) Integer to String1 1.7
'%x'%x Int to Hex 12
x+y Addition/Subtraction 12
x*y Multiplication 17
x/y Division (Remainder) 5.8
pow(x,y,z) Modular Exponentiation 1.7
2**n Power of two 0.41


Operation Description Asymptotic Real (s) Error (%)
s[i] Extract byte 1.9
s+t Concatenate 34
s[:n/2] Extract sub string 25
s.translate() Translate string 5.1


Operation Description Asymptotic Real (s) Error (%)
list() Create empty list 0.65
L[i] List lookup 3.2
L.append(x) Append in the end 22
L.pop() Pop the last 17
L+M Concatenate 9.2
L[:n/2] Extract slice 5
L[:] Copy 2.5
L[:n/2] = M Slice assignment 1.7
del L[0] Delete first 27
L.reverse() Reverse 9.7
L.sort() Sort array 7.5


Operation Description Asymptotic Real (s) Error (%)
dict() Create empty dict 0
D[i] Dictionary lookup 2
D.copy() Dictionary copy 23
D.items() List items 29.2 - 188.9k + 191k 8.1
  1. I was expecting the conversion to be linear, but it is quadratic. After a brief search I found this SO answer that mentions Python conversion being   2

  2. String operations have high error, and the real time varies a lot during benchmarking. 

Zafar Takhirov

Zafar Takhirov
I am a recent PhD graduate from Boston University. While my work focuses on digital design,error mitigation, and machine learning, my non-work interests range widely from information theory (go Shannon!), quantum computing, grandfather paradox, Star Trek, Little Mermaid, 'why is the grass green?', 1Q84, etc., etc., etc. If you want to talk about, well, anything - just ping me.

Passing cv::Mat as argument

Often times when we pass `cv::Mat`, we forget one important thing: `OpenCV` matrix does not respect the `const` modifier.In this post I w...… Continue reading

Hungarian Algorithm

Published on July 19, 2017

Adaptive Classification and More

Published on February 13, 2017