dot products

Raymond Hettinger vze4rx4y at verizon.net
Mon Dec 20 00:47:04 CET 2004


[Rahul].
> I want to compute dot product of two vectors stored as lists a and b.a
> and b are of the same length.
>
> one simple way is
> sum(a[i]*b[i] for i in range(len(a)))
>
> another simple way is
> ans=0.0
> for i in range(len(a)):
> ans=ans+a[i]*b[i]
>
> But is there any other way which is faster than any of the above.

Yes:
     from itertools import imap
     from operator import mul
     ans = sum(imap(mul, a, b))

In general:
* reduction functions like sum() do not need their arguments to
   take time building a full list; instead, an iterator will do fine
* applying itertools instead of genexps can save the eval-loop overhead
* however, genexps are usually more readable than itertools solutions
* xrange() typically beats range()
* but indexing is rarely the way to go
* izip() typically beats zip()
* imap() can preclude the need for either izip() or zip()
* the timeit module settles these questions quickly

Here are the some timings for vectors of length 10 and 3 respectively

C:\pydev>python timedot.py 3
1.25333310984 sum(a[i]*b[i] for i in xrange(len(a)))
1.16825625639 sum(x*y for x,y in izip(a,b))
1.45373455807 sum(x*y for x,y in zip(a,b))
0.635497577901 sum(imap(mul, a, b))
0.85894416601 sum(map(mul, a, b))

C:\pydev>python timedot.py 10
2.19490353509 sum(a[i]*b[i] for i in xrange(len(a)))
2.01773998894 sum(x*y for x,y in izip(a,b))
2.44932533231 sum(x*y for x,y in zip(a,b))
1.24698871922 sum(imap(mul, a, b))
1.49768685362 sum(map(mul, a, b))



Raymond Hettinger





More information about the Python-list mailing list