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 runtimes 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!
Methodology
All experiments are run on MacBook Pro (Retina, 13inch, 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
1
2
3
4
5
6
7
8
9
10
11
12
13
print "Test List1: 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()")
run_times.append(t.timeit(trials)*1e6/float(trials))
fit(var_list,param_list,run_times,f_list)
The raw and formatted results:
Operation  Description  Asymptotic  Real (s)  Error (%) 

list() 
Create empty list  0.38 
Results
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!!!
Integer
Operation  Description  Asymptotic  Real (s)  Error (%) 

int('1'*n) 
String to Integer^{1}  1.9  
repr(2**n) 
Integer to String^{1}  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 
String^{2}
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 
List
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 
Dict
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 

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}

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