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!
Methodology
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
1
2
3
4
5
6
7
8
9
10
11
12
13
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()")
run_times.append(t.timeit(trials)*1e6/float(trials))
fit(var_list,param_list,run_times,f_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:
0.125405*1
(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 |
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 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 |
String2
| 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. ↩
