Speeding up list processing in Python

Question

I have two lists list1 and list2, each of size 5000 with every entry of the lists being a numpy.array. I want to calculate the squares of the Euclidean distances between the elements of the lists in a fast and efficient way, i.e. I need to calculate sum((list1[i]-list2[j])**2) for every combination of i and j, which are thus in total 2,500,000 combinations. I currently did so by running a double loop and writing every result into a 2d numpy.array by means of

result[i,j] = sum((list1[i]-list2[j])**2)

but still need on my computer about 4 minutes of time. I was wondering, whether any tricks could be used to further speed the calculation up.

distance of i vs j is the same as distance of j vs i. You can cut half the time by using an inner loop that starts at the outer index — Jean-François Fabre
– Jean-François Fabre ♦, Commented May 26, 2020 at 19:25
Why do you have lists of arrays? This would go much faster with 2D arrays and something like scipy.spatial.distance.cdist. — user2357112
– user2357112, Commented May 26, 2020 at 19:27
from scipy.spatial import distance_matrix; dist_mat = distance_matrix(list1, list2)? — Quang Hoang
– Quang Hoang, Commented May 26, 2020 at 19:27
If all arrays in each list is the same shape, then a simple broadcasting ought to do the trick. — Mercury
– Mercury, Commented May 26, 2020 at 20:06

Ehsan · Accepted Answer · 2020-05-26 21:20:34Z

1

If you insist on numpy (assuming your inner arrays are 1-D):

dist_mat = ((list1[:,None,:]-list2[:,:])**2).sum(2)

Note that according to your definition of distance in question, this is square of Euclidean distances. If you want the distance itself, simply take square root of this.
Otherwise, I would prefer @Quang's comment:

from scipy.spatial import distance_matrix
dist_mat = distance_matrix(list1, list2)

edited May 26, 2020 at 21:20

answered May 26, 2020 at 21:14

Ehsan

12.5k2 gold badges24 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Steve Over a year ago

Many thanks, these are very good responses from everyone! Especially the scipy funtions speed up the computation of the distance matrix by ages.

Collectives™ on Stack Overflow

Speeding up list processing in Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related