두 배열 사이의 최단 거리를 찾는 효율적인 방법은 무엇입니까?

Question

배열의 두 세트 사이의 최단 거리를 찾으려고합니다. x- 배열은 동일하며 정수 만 포함합니다. 다음은 내가하려는 일의 예입니다.

import numpy as np 
x1 = x2 = np.linspace(-1000, 1000, 2001) 
y1 = (lambda x, a, b: a*x + b)(x1, 2, 1) 
y2 = (lambda x, a, b: a*(x-2)**2 + b)(x2, 2, 10) 

def dis(x1, y1, x2, y2): 
    return sqrt((y2-y1)**2+(x2-x1)**2) 

min_distance = np.inf 
for a, b in zip(x1, y1): 
    for c, d in zip(x2, y2): 
     if dis(a, b, c, d) < min_distance: 
      min_distance = dis(a, b, c, d) 

>>> min_distance 
2.2360679774997898 

이 솔루션은 작동하지만 문제는 런타임입니다. x의 길이가 ~ 10,000이면 프로그램은 O (n^2) 런타임이므로 실행 불가능합니다. 이제 프로그램을 빠르게 진행하기 위해 약간의 근사값을 만들려고했습니다 :

for a, b in zip(x1, y1): 
    cut = (x2 > a-20)*(x2 < a+20) 
    for c, d in zip(x2, y2): 
     if dis(a, b, c, d) < min_distance: 
      min_distance = dis(a, b, c, d) 

그러나 프로그램은 여전히 ​​내가 원하는 것보다 오래 걸립니다. 자, 내 이해에서, 그것은 일반적으로 비효율적 인 배열을 통해 루프를 비효율적 인, 그래서 거기에 아직 개선의 여지가 확실 해요. 이 프로그램의 속도를 높이는 방법에 대한 아이디어가 있습니까?

Answer 1

이것은 어려운 문제이며 근사치를 기꺼이 수용하려는 경우 도움이 될 수 있습니다. 나는 Spottify의 annoy과 같은 것을 조사 할 것입니다.

Answer 2

문제는 2d 충돌 감지로도 표현 될 수 있으므로 quadtree이 도움이 될 수 있습니다. 삽입 및 쿼리는 모두 O (log n) 시간에 실행되므로 전체 검색은 O (n log n)에서 실행됩니다.

sqrt가 단조 적이기 때문에 하나 더 제안하면 거리 대신에 거리의 제곱을 비교할 수 있습니다. 그러면 거리가 계산되지 않아서^2 제곱근 계산이 절약됩니다.

Answer 3

scipy 포인트의 모든 쌍 사이의 거리를 계산하는 cdist function을 갖는다 :이보다 250 배 빠른 루프 원래보다 실행

from scipy.spatial.distance import cdist 
import numpy as np 

x1 = x2 = np.linspace(-1000, 1000, 2001) 
y1 = (lambda x, a, b: a*x + b)(x1, 2, 1) 
y2 = (lambda x, a, b: a*(x-2)**2 + b)(x2, 2, 10) 

R1 = np.vstack((x1,y1)).T 
R2 = np.vstack((x2,y2)).T 

dists = cdist(R1,R2) # find all mutual distances 

print (dists.min()) 
# output: 2.2360679774997898 

.