Jak znaleźć najbliższe elementy w dwóch tablicach?

Question

Mam dwa niezliczone tablice, takie jak X=[x1,x2,x3,x4], y=[y1,y2,y3,y4]. Trzy elementy są blisko, a czwarta może być blisko.

odczuwalna:

X [ 84.04467948 52.42447842 39.13555678 21.99846595] 
y [ 78.86529444 52.42447842 38.74910101 21.99846595] 

Albo może to być:

X [ 84.04467948 60 52.42447842 39.13555678] 
y [ 78.86529444 52.42447842 38.74910101 21.99846595] 

Chcę zdefiniować funkcję, aby znaleźć odpowiedni wskaźnik w dwóch tablicach, podobnie jak w pierwszym przypadku:

• y[0] odpowiada X[0],
• y[1] odpowiadają X[1],
• y[2] odpowiadają X[2],
• y[3] odpowiadają X[3]

a w drugim przypadku:

• y[0] odpowiadają X[0],
• y[1] odpowiadają T O X[2],
• y[2] odpowiadają X[3]
• i y[3] odpowiadają X[1].

Nie mogę napisać funkcji, aby całkowicie rozwiązać problem, proszę o pomoc.

Answer 1

Wydaje się, że najlepszym sposobem byłoby wstępne sortowanie obu tablic (n log (n)), a następnie wykonanie przechodzenia w podobny sposób przez obie tablice. Jest zdecydowanie szybszy niż n n, który wskazałeś w komentarzu.

Answer 2

Stosując tę ​​odpowiedź https://stackoverflow.com/a/8929827/3627387 i https://stackoverflow.com/a/12141207/3627387

FIXED

def find_closest(alist, target): 
    return min(alist, key=lambda x:abs(x-target)) 

X = [ 84.04467948, 52.42447842, 39.13555678, 21.99846595] 
Y = [ 78.86529444, 52.42447842, 38.74910101, 21.99846595] 

def list_matching(list1, list2): 
    list1_copy = list1[:] 
    pairs = [] 
    for i, e in enumerate(list2): 
     elem = find_closest(list1_copy, e) 
     pairs.append([i, list1.index(elem)]) 
     list1_copy.remove(elem) 
    return pairs 

Answer 3

Możesz zacząć od precomputing macierzy odległości, co pokazują w ten answer:

import numpy as np 

X = np.array([84.04467948,60.,52.42447842,39.13555678]) 
Y = np.array([78.86529444,52.42447842,38.74910101,21.99846595]) 

dist = np.abs(X[:, np.newaxis] - Y) 

Teraz można obliczyć minimalne wzdłuż jednej osi (wybrałem 1 correspo nding celu znalezienia najbliższego elementu Y dla każdego X):

potentialClosest = dist.argmin(axis=1) 

To nadal może zawierać duplikaty (w przypadku 2).Aby sprawdzić, które można znaleźć znaleźć wszystkie Y wskaźników, które pojawiają się w potentialClosest przy użyciu np.unique:

closestFound, closestCounts = np.unique(potentialClosest, return_counts=True) 

Teraz można sprawdzić duplikatów przez sprawdzenie czy closestFound.shape[0] == X.shape[0]. Jeśli tak, to jesteś złoty i potentialClosest będzie zawierać twoich partnerów dla każdego elementu w X. W twoim przypadku 2 jeden element pojawi się dwa razy, a zatem closestFound będzie miał tylko elementy X.shape[0]-1, podczas gdy closestCounts nie będzie zawierał tylko 1 s ale jednego 2. Dla wszystkich elementów z liczyć 1 partner jest już znaleziony. Dla dwóch kandydatów z liczbą 2, ale będziesz musiał wybrać bliżej, podczas gdy partnerem z większym dystansem będzie jeden element z Y, który nie jest w closestFound. To można znaleźć w:

missingPartnerIndex = np.where(
     np.in1d(np.arange(Y.shape[0]), closestFound)==False 
     )[0][0] 

Można zrobić matchin w pętli (choć nie mogą być pewne ładniejszy sposób korzystania numpy). To rozwiązanie jest raczej brzydkie, ale działa. Wszelkie sugestie dotyczące ulepszeń są bardzo mile widziane:

partners = np.empty_like(X, dtype=int) 
nonClosePartnerFound = False 
for i in np.arange(X.shape[0]): 
    if closestCounts[closestFound==potentialClosest[i]][0]==1: 
     # A unique partner was found 
     partners[i] = potentialClosest[i] 
    else: 
     # Partner is not unique 
     if nonClosePartnerFound: 
      partners[i] = potentialClosest[i] 
     else: 
      if np.argmin(dist[:, potentialClosest[i]]) == i: 
       partners[i] = potentialClosest[i] 
      else: 
       partners[i] = missingPartnerIndex 
       nonClosePartnerFound = True 
print(partners) 

Ta odpowiedź będzie działać tylko wtedy, gdy tylko jedna para nie jest zamknięta. Jeśli tak nie jest, musisz określić, jak znaleźć właściwego partnera dla wielu niezamkniętych elementów. Niestety, nie jest to rozwiązanie bardzo ogólne ani bardzo ładne, ale mam nadzieję, że okaże się pomocne.

Answer 4

Poniższe po prostu wypisuje odpowiednie indeksy obu tablic, tak jak zrobiłeś to w pytaniu, ponieważ nie jestem pewien, jaki wynik chcesz nadać swojej funkcji.

X1 = [84.04467948, 52.42447842, 39.13555678, 21.99846595] 
Y1 = [78.86529444, 52.42447842, 38.74910101, 21.99846595] 

X2 = [84.04467948, 60, 52.42447842, 39.13555678] 
Y2 = [78.86529444, 52.42447842, 38.74910101, 21.99846595] 

def find_closest(x_array, y_array): 
    # Copy x_array as we will later remove an item with each iteration and 
    # require the original later 
    remaining_x_array = x_array[:] 
    for y in y_array: 
     differences = [] 
     for x in remaining_x_array: 
      differences.append(abs(y - x)) 
     # min_index_remaining is the index position of the closest x value 
     # to the given y in remaining_x_array 
     min_index_remaining = differences.index(min(differences)) 
     # related_x is the closest x value of the given y 
     related_x = remaining_x_array[min_index_remaining] 
     print 'Y[%s] corresponds to X[%s]' % (y_array.index(y), x_array.index(related_x)) 
     # Remove the corresponding x value in remaining_x_array so it 
     # cannot be selected twice 
     remaining_x_array.pop(min_index_remaining) 

ten następnie przesyła następujące

find_closest(X1,Y1) 
Y[0] corresponds to X[0] 
Y[1] corresponds to X[1] 
Y[2] corresponds to X[2] 
Y[3] corresponds to X[3] 

i

find_closest(X2,Y2) 
Y[0] corresponds to X[0] 
Y[1] corresponds to X[2] 
Y[2] corresponds to X[3] 
Y[3] corresponds to X[1] 

nadzieję, że to pomaga.