Wydajna podwójna iteracja nad tablicą

Question

Mam następujący kod, gdzie punkty ma wiele linii o 3 COLS Lista list, Coorradius jest promieniem, w którym chcę znaleźć lokalną współrzędną Maxima, a Localcoordinatemaxima jest tablicą, w której przechowuję I's Texima:

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

Niestety, to trwa wiecznie, gdy mam kilka tysięcy punktów, szukam sposobu na przyspieszenie. Próbowałem to zrobić za pomocą, jeśli () stan, jednak nie radziłem sobie z tym i nie jestem nawet pewien, że będzie bardziej wydajny. Czy możesz zaproponować sposób, aby osiągnąć szybciej?

Najlepsza!

python arrays numpy

3

John 17 sierpień 2014, 13:10

Answer 1

Twoje wyszukiwanie dla sąsiadów najlepiej wykonać za pomocą Kdtree.

from scipy.spatial import cKDTree

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

Teraz pairs jest zestawem dwóch skórki elementu (i, j), gdzie i < j i points[i] i points[j] są w coorRadius. Teraz możesz po prostu iterować nad tymi, co prawdopodobnie będzie znacznie mniejszy zestaw niż len(points)**2 jest obecnie itera:

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)

Można go dalej przyspieszyć, Vectorizując go:

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)

Powyższy kod zakłada, że każdy punkt ma co najmniej jeden sąsiad w coorRadius. Jeśli tak nie jest, musisz nieznacznie skomplikować rzeczy:

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

Jaime 18 sierpień 2014, 00:11

Answer 2

Z numpry to nie jest zbyt trudne. Możesz to zrobić za pomocą jednego (długiego) wyrażenia, jeśli chcesz:

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

Algorytm Twoje implemy bieżącego kodu jest zasadniczo where(not(any(w <= x and y < z))). Jeśli dystrybuujesz not przez logiczne operacje wewnątrz go (przy użyciu przepisów demorganowych), można uniknąć jednego poziomu gniazda, przerzucając nierówności, zdobywanie where(all(w > x or y >= z))).

w jest matrycą norm stosowanych do różnic punktów punktowych razem. x jest stałą. y i z są obiektami z trzecimi współrzędnymi punktów, w kształcie, tak że nadają się razem w tym samym kształcie, co w.

1

Blckknght 17 sierpień 2014, 10:53

Wydajna podwójna iteracja nad tablicą

2 odpowiedzi

Podobne pytania

Nowe pytania

python