7
\$\begingroup\$

Let's say you have two lists of vectors:

v1s = [a, b, c]

v2s = [d, e, f]

I am interested in generating the following result:

angles = [angleBetween(a, d), angleBetween(b, e), angleBetween(c, f)]

Here is my function to do this (it uses vector dot products in order to calculate the angles):

import numpy as np

def findAnglesBetweenTwoVectors(v1s, v2s):
    dot_v1_v2 = np.einsum('ij,ij->i', v1s, v2s)
    dot_v1_v1 = np.einsum('ij,ij->i', v1s, v1s)
    dot_v2_v2 = np.einsum('ij,ij->i', v2s, v2s)

    return np.arccos(dot_v1_v2/(np.sqrt(dot_v1_v1)*np.sqrt(dot_v2_v2)))

I call this function a lot, so optimizing it would be very helpful for me. Is this possible?

\$\endgroup\$
  • 2
    \$\begingroup\$ Is the middle term angleBetween(b, d) or angleBetween(b, e)? \$\endgroup\$ – hpaulj Jun 16 '14 at 7:11
  • \$\begingroup\$ @hpaulj It should be angleBetween(b, e)! Fixed now. \$\endgroup\$ – user89 Jun 16 '14 at 7:19
  • 1
    \$\begingroup\$ You can spare yourself half of your square roots, which are expensive operations, by multiplying before taking the root, i.e. return np.arccos(dot_v1_v2/np.sqrt(dot_v1_v1*dot_v2_v2)). \$\endgroup\$ – Jaime Jun 16 '14 at 15:17
2
\$\begingroup\$

Here's a way of packing the calculation into on call to einsum.

def findAnglesBetweenTwoVectors1(v1s, v2s):
    dot = np.einsum('ijk,ijk->ij',[v1s,v1s,v2s],[v2s,v1s,v2s])
    return np.arccos(dot[0,:]/(np.sqrt(dot[1,:])*np.sqrt(dot[2,:])))

for random vectors of length 10, the speed for this function and yours is basically the same. But with 10000, (corrected times)

In [62]: timeit findAnglesBetweenTwoVectors0(v1s,v2s)
100 loops, best of 3: 2.26 ms per loop

In [63]: timeit findAnglesBetweenTwoVectors1(v1s,v2s)
100 loops, best of 3: 4.24 ms per loop

Yours is clearly faster.

We could try to figure out why the more complex einsum is slower (assuming the issue is there rather than the indexing in the last line). But this result is consistent with other einsum testing that I've seen and done. einsum on simple 2D cases is as fast as np.dot, and in some cases faster. But in more complex cases (3 or more indexes) it is slower than the equivalent constructed from multiple calls to np.dot or einsum.


I tried tried factoring out the array construction, and got a speed improvement.

In [12]: V1=np.array(v1s)  # shape (3,10000,3)
In [13]: V2=np.array(v2s)
In [22]: timeit findAnglesBetweenTwoVectors2(V1,V2)
100 loops, best of 3: 2.63 ms per loop

I've corrected the times, using v1s.shape==(10000,3)

\$\endgroup\$
  • \$\begingroup\$ Pretty interesting. I am setting up things on a new computer where I will do my testing, so I hadn't gotten to testing that out yet myself. I can now cross it off of my list. My next idea was to perhaps execute the three einsum in parallel using multiprocessing.pool. I will get back to you with my results from that experiment. \$\endgroup\$ – user89 Jun 16 '14 at 18:00
  • \$\begingroup\$ I am also considering stealing this code here (there is a function to compute the angle between two vectors), and using PyOpenCL to then implement it. Not sure though. \$\endgroup\$ – user89 Jun 16 '14 at 18:21
  • \$\begingroup\$ Update on the multiprocessing test: its much slower: the normal version is over 9000 (serious, no pun intended) times faster. \$\endgroup\$ – user89 Jun 16 '14 at 20:30
  • \$\begingroup\$ By the way, in my current construction, I am always supplying numpy array objects to the function. The shape should be (10000,). \$\endgroup\$ – user89 Jun 16 '14 at 20:36
  • \$\begingroup\$ I changed the inputs so the shape is correct. The 3 einsum calculations is still better, though most of the extra in the single einsum case is due to the work of assembling the 3d arrays. \$\endgroup\$ – hpaulj Jun 16 '14 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.