Effizient Berechnen der euklidischen Distanz-Matrix Mithilfe von Numpy
Habe ich eine Reihe von Punkten im 2-dimensionalen Raum und berechnen die Entfernung von jedem Punkt zu jedem anderen Punkt.
Ich habe eine relativ kleine Anzahl von Punkten, vielleicht bei maximal 100. Aber da ich brauche es oft und schnell, um zu bestimmen, die Beziehungen zwischen dieser beweglichen Punkte, und da ich bin mir bewusst, dass, Durchlaufen die Punkte werden konnte, so schlimm wie O(n^2) Komplexität, ich bin auf der Suche nach Möglichkeiten, um die Vorteile von numpy matrix-Magie (oder scipy).
So steht es in meinem code, die Koordinaten für jedes Objekt gespeichert, das in seiner Klasse. Allerdings konnte ich auch aktualisieren Sie Sie in ein numpy-array, wenn ich ein update der Klasse koordinieren.
class Cell(object):
"""Represents one object in the field."""
def __init__(self,id,x=0,y=0):
self.m_id = id
self.m_x = x
self.m_y = y
Fällt mir ein, erstellen Sie eine euklidische Distanz-matrix, um überschneidungen zu vermeiden, aber vielleicht haben Sie ein intelligenter Daten-Struktur.
Ich bin offen für Zeiger auf raffinierte algorithmen als auch.
Ich auch, beachten Sie, dass es ähnliche Fragen, die den euklidischen Abstand und numpy aber nicht finden, eine, die direkt auf diese Frage einzugehen effizient Auffüllen einer vollständigen Entfernung der matrix.
Komplexität wird O(n^2) egal, was: das beste was Sie tun können für einen Allgemeinen Satz von Punkten ist die Berechnung
n * (n - 1) / 2
Entfernungen, die ist immer noch O(n^2).Beispiel?
InformationsquelleAutor Wes Modes | 2014-03-28
Du musst angemeldet sein, um einen Kommentar abzugeben.
Können Sie die Vorteile der
complex
Typ :Erste Lösung
Zweite Lösung
Vernetzen, ist die wichtigste Idee. Aber
numpy
ist clever, so dass Sie nicht haben, um zu generierenm
&n
. Nur berechnen Sie die Differenz mit einer Transponierten version vonz
. Das Netz wird automatisch erledigt :Dritte Lösung
Und wenn
z
direkt als 2-dimensionales array verwenden, können Siez.T
statt dem komischenz[..., np.newaxis]
. So endlich, Ihr code wird wie folgt Aussehen :Beispiel
Als Ergänzung, möchten Sie vielleicht, um Duplikate entfernen danach, unter dem oberen Dreieck :
Einige benchmarks
Ich bearbeitet meine post deutlicher machen, lassen Sie mich wissen, wenn Sie immer noch verloren.
+1 sehr elegant
InformationsquelleAutor Kiwi
Hier ist, wie können Sie dies mithilfe von numpy:
Nun alle übrig bleibt, ist der Berechnung der L2-norm, die entlang der 0-Achse (wie besprochen hier):
InformationsquelleAutor shx2
Wenn Sie nicht brauchen die volle Distanz-matrix, werden Sie besser dran, mit kd-Baum. Betrachten
scipy.spatial.cKDTree
odersklearn.neighbors.KDTree
. Dies ist, weil ein kd-Baum kan finden k-nearnest Nachbarn in O(n log n) Zeit, und daher vermeiden Sie die O(n**2) Komplexität der computing alle n von n Strecken.InformationsquelleAutor Sturla Molden
Jake Vanderplas gibt dieses Beispiel mit Ausstrahlung in Python Data Science Handbook, die ist sehr ähnlich zu dem, was @shx2 vorgeschlagen.
schreiben Sie eine Antwort mit einem Aufruf
%timeit
, vielleicht für einen kleinen (10x10) und großen (1,000,000 x 1,000,000) Distanz-matrix. Das wäre wirklich nützliche Informationen für die Menschen!ich kann nicht mit
%timeit
in meinem jupyter notebook, weil ich die online-Variante und es läuft von Speicher für arrays, die großInformationsquelleAutor Rich Pauloo