Ich habe ein Array von x, y, z-Koordinaten von mehreren (~ 10 ^ 10) Punkten (nur 5 hier gezeigt)
%Vor% Ich möchte ein neues Array mit nur den Punkten erstellen, die von allen anderen Punkten in der Liste mindestens um eine Distanz d entfernt sind. Ich schrieb einen Code mit while loop,
Das funktioniert, aber es dauert sehr lange, diese Berechnung durchzuführen. Ich habe irgendwo gelesen, dass while loops sehr langsam sind.
Ich habe mich gefragt, ob jemand Vorschläge hat, wie man diese Berechnung beschleunigen kann.
BEARBEITEN: Während mein Ziel, die Partikel zu finden, die zumindest einigermaßen entfernt von allen anderen sind, ist mir klar geworden, dass mein Code einen ernsthaften Fehler aufweist, sagen wir Habe 3 Partikel, mein Code tut folgendes, für die erste Iteration von i berechnet er die Abstände 1->2 , 1->3 , sagen wir 1->2 ist kleiner als die Schwelldistanz d , also wirft der Code weg Partikel 1 . Für die nächste Iteration von i , tut es nur 2->3 , und sagen wir, es ist größer als d , also behält es Partikel 2 , aber das ist falsch! da 2 sollte auch mit Partikel 1 verworfen werden. Die Lösung von @svohara ist die richtige!
Bei großen Datensätzen und niedrigdimensionalen Punkten (wie z. B. Ihren dreidimensionalen Daten) ist die Verwendung einer räumlichen Indexierungsmethode manchmal von großem Vorteil. Eine beliebte Wahl für niedrigdimensionale Daten ist der k-d-Baum.
Die Strategie besteht darin, den Datensatz zu indizieren. Dann Abfrage des Index mit dem gleichen Datensatz, um die 2 nächsten Nachbarn für jeden Punkt zurückzugeben. Der erste nächste Nachbar ist immer der Punkt selbst (mit dist = 0), also wollen wir wirklich wissen, wie weit der nächstgelegene Punkt entfernt ist (2. nächster Nachbar). Für jene Punkte, wo das 2-NN & gt; Schwelle, Sie haben das Ergebnis.
%Vor% Hier ist ein vektorisierter Ansatz mit distance.pdist -
Bei einem großen Dataset wie 10e10 müssen wir die Operationen möglicherweise in Blöcken basierend auf dem verfügbaren Systemspeicher durchführen.
Ihr Algorithmus ist quadratisch (10 ^ 20 Operationen), hier ist ein linearer Ansatz, wenn die Verteilung nahezu zufällig ist.
Teilt Ihren Platz in Boxen der Größe d/sqrt(3)^3 . Setzen Sie jeden Punkt in seine Box.
Dann für jede Box,
Wenn es nur einen Punkt gibt, müssen Sie nur die Entfernung mit Punkten in einer kleinen Nachbarschaft berechnen.
sonst gibt es nichts zu tun.
Lassen Sie den Anhang fallen, es muss sehr langsam sein. Sie können einen statischen Vektor von Entfernungen haben und [] verwenden, um die Zahl an die richtige Position zu setzen.
Verwenden Sie min statt alle. Sie müssen nur überprüfen, ob der Mindestabstand größer als x ist.
Tatsächlich können Sie Ihren Append in dem Moment unterbrechen, in dem Sie eine Entfernung kleiner als Ihr Limit finden, und dann können Sie beide Punkte auslassen. Auf diese Weise müssen Sie sogar keine Entfernung speichern (außer Sie brauchen sie später).
Von Ihrem Kommentar glaube ich, dass dies tun würde, wenn Sie keine wiederholten Punkte haben.
%Vor%Am Ende überprüfe ich a, b und b, a, weil Sie eine Liste während der Verarbeitung nicht ändern sollten, aber Sie können schlauer sein, indem Sie einige zusätzliche Variablen verwenden.
Tags und Links python python-2.7 numpy while-loop