Clever Geek Handbook

Efficient double iteration over an array

I have the following code where dots are many rows across a list of 3 cols, coorRadius is the radius within which I want to find the local maximums of the coordinates, and localCoordinateMaxima is the array in which I store these maximums:

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 it lasts forever, when I have several thousand points, I am looking for a way to speed it up. I tried to do it with the all () condition, however I failed with it and I'm not even sure if it would be more efficient. Could you guys suggest a way to do this faster?

Best!

+3


source to share


3 answers


Your search for neighbors is best done with KDTree.

from scipy.spatial import cKDTree

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

Now pairs

is a set of two sets of elements (i, j)

, wherein i < j

and points[i]

and points[j]

are within coorRadius

each other. Now you can just len(points)**2

iterate over them, which is likely to be much smaller than what 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 accelerated 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 each point has at least one neighbor within coorRadius

. If not, you need to complicate things a little:

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)
+2


source


Here's a slightly drawn-out version of your code:

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:

  • Change your search x[2]

    .
  • The j variable was not used.
  • Add an early exit break
  • Use a for-else construct instead of a flag variable
+3


source


With numpy, it's not too hard. You can do it with one (long) expression if you like:

import numpy as np

points = np.array(points)
localCoordinateMaxima = np.where(np.all((np.linalg.norm(points-points[None,:], axis=-1) >
                                         coorRadius) |
                                        (points[:,2] >= points[:,None,2]),
                                        axis=-1))

The algorithm that your current code implements is essential where(not(any(w <= x and y < z)))

. If you allocate not

via logical operations within it (using the Demonator's laws), you can avoid one level of nesting by reversing the inequalities to get where(all(w > x or y >= z)))

.

w

is a matrix of norms applied to the differences between the points passed together. x

is a constant. y

and z

- both arrays with third point coordinates, formed so that they pass together in the same shape as w

.

+1


source






More articles:


All Articles