Efficient double iteration over array

Question

I have the following code, where points is many lines by 3 cols list of lists, coorRadius is a radius within which I want to find the local coordinate maxima, and localCoordinateMaxima is an array where I store the i's of these maxima:

for i,x in enumerate(points):
        check = 1
        for j,y in enumerate(points):
            if linalg.norm(x-y) <= coorRadius and x[2] < y[2]:
                check = 0

        if check == 1:
            localCoordinateMaxima.append(i)

    print localCoordinateMaxima

Unfortunately, this takes forever when I have several thousand points, I am looking for a way to speed it up. I tried to do it with if all() condition, however I didn't manage it and I am not even sure it will be more efficient. Could you guys propose a way to make it faster?

Best!

Answer 1

Your search for neighbors is best done using a KDTree.

from scipy.spatial import cKDTree

tree = cKDTree(points)
pairs = tree.query_pairs(coorRadius)

Now pairs is a set of two item tuples (i, j), where i < j and points[i] and points[j] are within coorRadius of each other. You can now simply iterate over these, which will likely be a much smaller set than the len(points)**2 you are currently iterating over:

is_maximum = [True] * len(points)
for i, j in pairs:
    if points[i][2] < points[j][2]:
        is_maximum[i] = False
    elif points[j][2] < points[i][2]:
        is_maximum[j] = False
localCoordinateMaxima, = np.nonzero(is_maximum)

This can be further sped up by vectorizing it:

pairs = np.array(list(pairs))
pairs = np.vstack((pairs, pairs[:, ::-1]))
pairs = pairs[np.argsort(pairs[:, 0])]
is_z_smaller = points[pairs[:, 0], 2] < points[pairs[:, 1], 2]
bins, = np.nonzero(pairs[:-1, 0] != pairs[1:, 0])
bins = np.concatenate(([0], bins+1))
is_maximum = np.logical_and.reduceat(is_z_smaller, bins)
localCoordinateMaxima, = np.nonzero(is_maximum)

The above code assumes that every point has at least one neighbor within coorRadius. If that is not the case, you need to slightly complicate things:

pairs = np.array(list(pairs))
pairs = np.vstack((pairs, pairs[:, ::-1]))
pairs = pairs[np.argsort(pairs[:, 0])]
is_z_smaller = points[pairs[:, 0], 2] < points[pairs[:, 1], 2]
bins, = np.nonzero(pairs[:-1, 0] != pairs[1:, 0])
has_neighbors = pairs[np.concatenate(([True], bins)), 0]
bins = np.concatenate(([0], bins+1))
is_maximum = np.ones((len(points),), bool)
is_maximum[has_neighbors] &= np.logical_and.reduceat(is_z_smaller, bins)
localCoordinateMaxima, = np.nonzero(is_maximum)

Answer 2

Here is the version of your code just tightened-up a bit:

for i, x in enumerate(points):
    x2 = x[2]
    for y in points:
        if linalg.norm(x-y) <= coorRadius and x2 < y[2]:
            break
    else:
        localCoordinateMaxima.append(i)
    print localCoordinateMaxima

Changes:

• Factor-out the x[2] lookup.
• The j variable was unused.
• Add a break for an early-out
• Use a for-else construct instead of a flag variable