title: Optimized dot product in Python
body: <p>The dot product of two n-dimensional vectors <code>u=[u1,u2,...un]</code> and <code>v=[v1,v2,...,vn]</code> is is given by <code>u1*v1 + u2*v2 + ... + un*vn</code>.</p>
  
  <p>A question <a href="https://stackoverflow.com/questions/1823293/optimized-method-for-calculating-cosine-distance-in-python/1823735#1823735">posted yesterday</a> encouraged me to find the fastest way to compute dot products in Python using only the standard library, no third-party modules or C/Fortran/C++ calls.</p>
  
  <p>I timed four different approaches; so far the fastest seems to be <code>sum(starmap(mul,izip(v1,v2)))</code> (where <code>starmap</code> and <code>izip</code> come from the <code>itertools</code> module).</p>
  
  <p>For the code presented below, these are the elapsed times (in seconds, for one million runs):</p>
  
  <pre><code>d0: 12.01215
  d1: 11.76151
  d2: 12.54092
  d3: 09.58523
  </code></pre>
  
  <p>Can you think of a faster way to do this?</p>
  
  <pre><code>import timeit # module with timing subroutines                                                              
  import random # module to generate random numnbers                                                          
  from itertools import imap,starmap,izip
  from operator import mul
  
  def v(N=50,min=-10,max=10):
      """Generates a random vector (in an array) of dimension N; the                                          
      values are integers in the range [min,max]."""
      out = []
      for k in range(N):
          out.append(random.randint(min,max))
      return out
  
  def check(v1,v2):
      if len(v1)!=len(v2):
          raise ValueError,"the lenght of both arrays must be the same"
      pass
  
  def d0(v1,v2):
      """                                                                                                     
      d0 is Nominal approach:                                                                                 
      multiply/add in a loop                                                                                  
      """
      check(v1,v2)
      out = 0
      for k in range(len(v1)):
          out += v1[k] * v2[k]
      return out
  
  def d1(v1,v2):
      """                                                                                                     
      d1 uses an imap (from itertools)                                                                        
      """
      check(v1,v2)
      return sum(imap(mul,v1,v2))
  
  def d2(v1,v2):
      """                                                                                                     
      d2 uses a conventional map                                                                              
      """
      check(v1,v2)
      return sum(map(mul,v1,v2))
  
  def d3(v1,v2):
      """                                                                                                     
      d3 uses a starmap (itertools) to apply the mul operator on an izipped (v1,v2)                           
      """
      check(v1,v2)
      return sum(starmap(mul,izip(v1,v2)))
  
  # generate the test vectors                                                                                 
  v1 = v()
  v2 = v()
  
  if __name__ == '__main__':
  
      # Generate two test vectors of dimension N                                                              
  
      t0 = timeit.Timer("d0(v1,v2)","from dot_product import d0,v1,v2")
      t1 = timeit.Timer("d1(v1,v2)","from dot_product import d1,v1,v2")
      t2 = timeit.Timer("d2(v1,v2)","from dot_product import d2,v1,v2")
      t3 = timeit.Timer("d3(v1,v2)","from dot_product import d3,v1,v2")
  
      print "d0 elapsed: ", t0.timeit()
      print "d1 elapsed: ", t1.timeit()
      print "d2 elapsed: ", t2.timeit()
      print "d3 elapsed: ", t3.timeit()
  </code></pre>
  
  <p>Notice that the name of the file must be <code>dot_product.py</code> for the script to run; I used Python 2.5.1 on a Mac OS X Version 10.5.8.</p>
  
  <p>EDIT:</p>
  
  <p>I ran the script for N=1000 and these are the results (in seconds, for one million runs):</p>
  
  <pre><code>d0: 205.35457
  d1: 208.13006
  d2: 230.07463
  d3: 155.29670
  </code></pre>
  
  <p>I guess it is safe to assume that, indeed, option three is the fastest and option two the slowest (of the four presented).</p>