View source

Python is a high-level programming language, with
many powerful primitives.  Analyzing the running
time of a Python program requires an understanding
of the cost of the various Python primitives.

For example, in Python, you can write:
<pre>
    L = L1 + L2
</pre>
where L, L1, and L2 are lists; the given statement
computes <tt>L</tt> as the concatenation of the
two input lists <tt>L1</tt> and <tt>L2</tt>.  The
running time of this statement will depend on the
lengths of lists <tt>L1</tt> and <tt>L2</tt>. 
(The running time is more-or-less proportional to 
the sum of those two lengths.)

Our goal in this section is to review various
Python primitive operations, and to determine
bounds and/or estimates on their running times.
Our approach will involve both a review of the
relevant Python implementation code, and also
some experimentation (analysis of actual running
times and interpolating a nice curve through the
resulting data points).

The Python implementation code base is
'''here'''.

== Python Running Time Experiments and Discussion ==

The running times for various-sized
inputs were measured, and then a least-squares
fit was used to find the coefficient for the
high-order term in the running time.  (Which term
is high-order was determined by some experimentation;
it could have been automated...)

The least-squares fit was designed to minimize
the sum of squares of relative error, using
<tt>scipy.optimize.leastsq</tt>.

(Earlier version of this program worked with more
than the high-order term; they also found coefficients
for lower-order terms.  But the interpolation routines
tended to be poor at distinguishing <i>n</i> and
<i>n</i> lg <i>n</i>.  Also, it was judged to be 
more interesting to work with relative error than
with absolute error.  Finally, it seemed that looking
at only the high-order term, and studying only the
relative error, seemed simplest.)

The machine used was an IBM Thinkpad T43p with
a 1.86GHz Pentium M processor and 1.5GB RAM.

The timing code itself is here:
[http://theory.csail.mit.edu/classes/6.006/fall07/timing/timing.py timing.py].
Sample output from this code is here:
[http://theory.csail.mit.edu/classes/6.006/fall07/timing/timing.out.txt timing.out.txt].
(This output may have results somewhat different than in the charts below,
due to random run-time variations...]

== Cost of Python Integer Operations ==
{| border="2" cellpadding=10
|+ <tt>Cost of Python Integer Operations</tt><br>
<tt>x,y, and z are n-bit numbers</tt><br>
<tt>w is an 2n-bit number</tt><br>
<tt>s is an n-digit string</tt>
|- 
| '''Convert string to integer'''
| <tt>int(s)</tt>
| <tt>84 * (n/1000)^2 microseconds</tt>
| <tt> n <= 8000</tt>
| 6% rms error
|-
| '''Convert integer to string'''
| <tt>str(x)</tt>
| <tt>75 * (n/1000)^2 microseconds</tt>
| <tt> n <= 8000</tt>
| 3% rms error
|- 
| '''Convert integer to hex'''
| <tt>"%x"%x</tt>
| <tt>2.7 * (n/1000) microseconds</tt>
| <tt> n <= 64000</tt>
| 19% rms error
|-
| '''Addition (or Subtraction)'''
| <tt>x+y</tt>
| <tt>0.75 * (n/1000) microseconds</tt>
| <tt>n <= 512000</tt>
| 8% rms error
|-
| '''Multiplication'''
| <tt>x*y</tt>
| <tt>13.73 * (n/1000)^1.585 microseconds</tt>
| <tt>n <= 64000</tt>
| 10% rms error
|-
| '''Division (or Remainder)'''
| <tt>w/x</tt>
| <tt>47 * (n/1000)^2 microseconds</tt>
| <tt> n <= 32000 </tt>
| 6% rms error
|-
| '''Modular Exponentiation'''
| <tt>pow(x,y,z)</tt>
| <tt>60000 * (n/1000)^3 microseconds</tt>
| <tt> n <= 4000 </tt>
| 8% rms error
|-
| '''n-th power of two'''
| <tt>2**n</tt>
| <tt>0.06 microseconds</tt>
| <tt> n <= 512000 </tt>
| 10% rms error
|}

It is perhaps curious that multiplication is implemented using Karatsuba's algorithm,
giving an &Theta;(<i>n</i><sup>lg 3</sup>) running time, while division uses 
an &Theta;(<i>n</i><sup>2</sup>) algorithm.

== Cost of Python String Operations ==

{| border="2" cellpadding=10
|+ <tt>Cost of Python String Operations</tt><br>
<tt>s and t are length-n strings</tt><br>
<tt>u is length (n/2)</tt>
|- 
| '''Extract a byte from a string'''
| <tt>s[i]</tt>
| <tt>0.13 microseconds</tt>
| <tt> n <= 512000</tt>
| 29% rms error
|-
| '''Concatenate'''
| <tt>s+t</tt>
| <tt>1 * (n/1000) microseconds</tt>
| <tt> n <= 256000 </tt>
| 19% rms error
|-
| '''Extract string of length n/2'''
| <tt>s[0:n/2]</tt>
| <tt>0.3 * (n/1000) microseconds</tt>
| <tt> n <= 256000 </tt>
| 28% rms error
|-
| '''Translate a string'''
| <tt>s.translate(s,T)</tt>
| <tt>3.2 * (n/1000) microseconds</tt>
| <tt> n <= 256000 </tt>
| 11% rms error
|}

== Cost of Python List Operations ==

{| border="2" cellpadding=10
|+ <tt>Cost of Python List Operations</tt><br>
<tt>L and M are length-n lists</tt><br>
<tt>P has length n/2</tt>
|- 
| '''Create an empty list'''
| <tt>list()</tt>
| <tt>0.40 microseconds</tt>
| <tt>(n=1)</tt>
| .5% rms error
|- 
| '''Access'''
| <tt>L[i]</tt>
| <tt>0.10 microseconds</tt>
| <tt> n <= 640000</tt>
| 3% rms error
|-
| '''Append'''
| <tt>L.append(0)</tt>
| <tt>0.24 microseconds</tt>
| <tt> n <= 640000</tt>
| 3% rms error
|-
| '''Pop'''
| <tt>L.pop()</tt>
| <tt>0.25 microseconds</tt>
| <tt> n <= 64000 </tt>
| 0.5% rms error
|-
| '''Concatenate'''
| <tt>L+M</tt>
| <tt>22 * (n/1000) microseconds</tt>
| <tt> n <= 64000 </tt>
| 3% rms error
|-
| '''Slice extraction'''
| <tt>L[0:n/2]</tt>
| <tt> 5.4 * (n/1000) microseconds</tt>
| <tt> n <= 64000</tt>
| 4% rms error
|-
| '''Copy'''
| <tt>L[:]</tt>
| <tt> 11.5 * (n/1000) microseconds</tt>
| <tt> n <= 64000 </tt>
| 10% rms error
|- 
| '''Slice assignment'''
| <tt>L[0:n/2] = P</tt>
| <tt> 11 * (n/1000) microseconds</tt>
| <tt> n <= 64000 </tt>
| 4% rms error
|-
| '''Delete first'''
| <tt>del L[0]</tt>
| <tt> 1.7 * (n/1000) microseconds</tt>
| <tt> n <= 64000 </tt>
| 4% rms error
|-
| '''Reverse'''
| <tt>L.reverse()</tt>
| <tt> 1.3 * (n/1000) microseconds</tt>
| <tt> n <= 64000 </tt>
| 10% rms error
|-
| '''Sort'''
| <tt>L.sort()</tt>
| <tt> 0.0039 * n lg(n) microseconds</tt>
| <tt> n <= 64000 </tt>
| 12% rms error
|}

The '''first''' time one appends to a list, there is additional
cost as the list is copied over and extra space, about 1/8 of the
list size, is added to the end.  Whenever the extra space is used
up, the list is re-allocated into a new array with about 1.125 the
length of the previous version.

== Cost of Python Dictionary Operations ==


{| border="2" cellpadding=10
|+ <tt>Cost of Python Dictionary Operations</tt><br>
<tt>D is a dictionary with n items</tt><br>
|- 
| '''Create an empty dictionary'''
| <tt>dict()</tt>
| <tt>0.36 microseconds</tt>
| <tt>(n=1)</tt>
| 0% rms error
|- 
| '''Access'''
| <tt>D[i]</tt>
| <tt>0.12 microseconds</tt>
| <tt> n <= 64000</tt>
| 3% rms error
|-
| '''Copy'''
| <tt>D.copy()</tt>
| <tt> 57 * (n/1000) microseconds</tt>
| <tt> n <= 64000 </tt>
| 27% rms error
|-
| '''List items'''
| <tt>D.items()</tt>
| <tt>0.0096 * n lg(n) microseconds</tt>
| <tt> n <= 64000 </tt>
| 14% rms error
|}

What should the right high-order term be for copy and list items?
It seems these should be linear,
but the data for both looks somewhat super-linear.  We've
modelled copy here as linear and list items as <tt>n lg(n)</tt>,
but these formulae need further work and exploration.

== Cost of Python Set Operations ==

This is a homework problem. See Problem Set 1, Problem 3.

Up: [[Introduction and Document Distance]]