How to avoid quadratic computation resulting from double 'for loop' when computing distances between vectors

Question

Given the following code that computes distances between vectors in list 'vect’:

import numpy as np
vect=([0.123, 0.345, 0.789], [0.234, 0.456, 0.567],[0.134, 0.246, 0.831])
def kn():
    for j in vect:
        c=np.array(j)
        for z in vect:
            p=np.array(z)
            space = np.linalg.norm(c-p)
            print space
kn()

Is there a way to avoid the quadratic complexity that will result from the double ‘for loop’?

Computation as a result of the double for loop (quadratic) ==3X3=9

Ideal computation (what I want) should be (3):
[0.123, 0.345, 0.789] and [0.234, 0.456, 0.567] =
[0.123, 0.345, 0.789] and [0.134, 0.246, 0.831] =
[0.234, 0.456, 0.567] and [0.134, 0.246, 0.831] =

Thanks in advance for your suggestion(s).

rkhayrov · Accepted Answer · 2013-08-02 10:48:47Z

2

To avoid duplicate pairs nested loop should go upwards from the index of the outer loop, i.e.:

for i, v1 in enumerate(vect):
    for j in xrange(i + 1, len(vect)):
        a = np.array(v1)
        b = np.array(vect[j])
        space = np.linalg.norm(b - a)
        print space

Or use a solution provided by the standard library:

import itertools

for v1, v2 in itertools.combinations(vect, 2):
    a = np.array(v1)
    b = np.array(v2)
    space = np.linalg.norm(b - a)
    print space

answered Aug 2, 2013 at 10:48

rkhayrov

10.3k2 gold badges38 silver badges42 bronze badges

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

1 Comment

Tiger1 Over a year ago

Spot-on mate. your solutions worked like magic. Thanks a lot.

Jaime · Accepted Answer · 2013-08-02 12:49:26Z

2

Others have noted that you can't avoid the quadratic complexity. But if your concern is performance, you can speed things up considerably by using scipy.spatial.distance.pdist, which will have all the looping and function calling happen in C, not Python. The following code returns a square, symmetrical array, but it only makes n *(n-1)/2 calculations:

from scipy.spatial.distance import pdist

pairwise_distances = pdist(vect, metric='euclidean', p=2)

If you want a flattened array with only the unique, off-diagonal values, you can use scipy.spatial.distance.squareform:

from scipy.spatial.distance import pdist, squareform

pairwise_distances = squareform(pdist(vect, metric='euclidean', p=2))

In your case, pairwise_distances would be a 3 element long array.

answered Aug 2, 2013 at 12:49

Jaime

67.7k19 gold badges128 silver badges164 bronze badges

1 Comment

Tiger1 Over a year ago

thanks for the solution and information, they both worked. I prefer the one that involves importing only pdist. Thanks.

Collectives™ on Stack Overflow

How to avoid quadratic computation resulting from double 'for loop' when computing distances between vectors

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related