Effiziente Methode, um den kürzesten Abstand zwischen zwei Arrays zu finden?

Question

Ich versuche den kürzesten Abstand zwischen zwei Arrays zu finden. Die x-Arrays sind identisch und enthalten nur ganze Zahlen. Hier ist ein Beispiel, was ich versuche zu tun:

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 

Diese Lösung funktioniert, aber das Problem ist Laufzeit. Wenn x eine Länge von ~ 10.000 hat, ist die Lösung nicht durchführbar, weil das Programm eine O (n^2) -Laufzeit hat. Jetzt habe ich versucht, einige Annäherungen zu machen, um das Programm zu beschleunigen:

Aber das Programm dauert noch länger als ich möchte. Nach meinem Verständnis ist es im Allgemeinen ineffizient, durch ein Array zu navigieren, also bin ich sicher, dass es noch Raum für Verbesserungen gibt. Irgendwelche Ideen, wie man dieses Programm beschleunigen kann?

Answer 1

Dies ist ein schwieriges Problem, und es kann hilfreich sein, wenn Sie Näherungswerte akzeptieren möchten. Ich würde etwas wie Spottifys annoy überprüfen.

Answer 2

Ihr Problem könnte auch als 2d Kollisionserkennung dargestellt werden, so dass eine quadtree helfen könnte. Einfügen und Abfragen laufen beide in O (log n) -Zeit, so dass die gesamte Suche in O (n log n) laufen würde.

Ein weiterer Vorschlag, da sqrt monoton ist, können Sie die Quadrate von Entfernungen anstelle der Abstände selbst vergleichen, die Sie sparen^2 Quadratwurzelberechnungen.

Answer 3

scipy hat ein cdist function die Distanz zwischen allen Paaren von Punkten berechnet:

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 

Diese mehr als 250-mal schneller läuft als das Original für die Schleife.