Welches Verfahren beschleunigt am besten diesen Code

Python in C/C++ embedden, C-Module, ctypes, Cython, SWIG, SIP etc sind hier richtig.
tobix
User
Beiträge: 2
Registriert: Sonntag 3. Mai 2015, 16:29

Welches Verfahren beschleunigt am besten diesen Code

Beitragvon tobix » Sonntag 3. Mai 2015, 16:46

Hallo zusammen,

es wäre sehr hilfreich, wenn ihr mir einen Hinweis zur Verbesserung meines Codes geben könntet.
Ich bin Neuling, dh. falls ich offensichtliche Sachen übersehen habe, war es keine Absicht.

Die Ausgangslage ist folgende:
ein Gegenstand liegt als 3D-Punktwolke vor
--> es existiert ein Textfile mit zigtausend Koordinaten (x,y,z) =test
derselbe Gegenstand, der sich aber im Laufe der Zeit leicht verändert hat, soll verglichen werden, um die Veränderungen zu zeigen
--> noch ein Textfile mit zigtausend Koordinaten =test2
Prinzip: Alle Punkte, die in beiden Files vorkommen raus und die welche nur einmal vorkommen sollten dann die "Veränderungspunkte" sein.

Aber die Punkte sind nicht bis auf die letzte Dezimale gleich und daher muss ein Pufferbereich eingebaut werden.
--> Gedanklich: Kugel um Punkt a und wenn Punkt b innerhalb des Radius liegt ignorieren,
ansonsten in ein neues Textfile schreiben... welches dann die Veränderungspunkte enthalten sollte.
-->Rechnerisch gelöst über Vektorrechnung:
Vektor mit Anfangspunkt u und Endpunkt b --> Ist der Vektor länger als das als Puffer gesetzte Limit, sollte es sich um einen Veränderungspunkt handeln.

Leider musste ich nach 5 Tagen den ersten Durchlauf abbrechen, weil das einfach viel zu lange dauert (habe rund 50 Gegenstände, die so verglichen werden sollen)

Was denkt ihr, wäre der beste Weg die Berechnung schneller durchzuführen? Cython?
Oder habe ich einfach nur einen unnötigen Schritt in den Code gebaut und es ginge viel eleganter?
(Oder falls jemandem ein anderer Weg zur Lösung des Problems einfällt... )

Bin für jeden Hinweis dankbar!

  1. import numpy as np
  2. vorher = np.genfromtxt("Dateipfad/test.asc")
  3. nachher = np.genfromtxt("Dateipfad/test2.asc")
  4. anders = []
  5. limit = 29
  6. for a in vorher:
  7.     for b in nachher:
  8.         vec = a - b
  9.         length = np.sqrt(vec[0]*vec[0] + vec[1]*vec[1] + vec[2]*vec[2])
  10.         if length < limit:
  11.             anders.append(b)
Sirius3
User
Beiträge: 7042
Registriert: Sonntag 21. Oktober 2012, 17:20

Re: Welches Verfahren beschleunigt am besten diesen Code

Beitragvon Sirius3 » Sonntag 3. Mai 2015, 17:07

@tobix: Du nutzt ja gar nicht die Matrixrechnung von numpy. Wie gehst Du mit zwei Punkten um, die nahe beieinander liegen? Gibt es die? "anders" sollte nach Deinem Code eigentlich "gleich" heißen.
Die erste Beschleunigung wäre also:

Code: Alles auswählen

limit = 29 ** 2
gleich = [b for b in nachher
    if ((vorher-b)**2).sum(1).min() < limit]

Das hat jetzt immer noch die Komplexität von O(n^2) sollte aber deutlich schneller sein. Wenn Du das ganze mit einem B-Tree machst, käme O(n * log(n)) raus, aber dafür mit etwas mehr Code.
BlackJack

Re: Welches Verfahren beschleunigt am besten diesen Code

Beitragvon BlackJack » Sonntag 3. Mai 2015, 17:13

@tobix: Kannst Du eventuell beide Punktwolken nehmen und beide auf ein Raster ”abrunden” und dann einfach Mengenoperationen ausführen?
tobix
User
Beiträge: 2
Registriert: Sonntag 3. Mai 2015, 16:29

Re: Welches Verfahren beschleunigt am besten diesen Code

Beitragvon tobix » Sonntag 3. Mai 2015, 18:40

@Sirius3:
numpy wurde mir empfohlen um möglichst einfach mein textfile in python laden zu können. Hat auch gut funktioniert;)

Es gibt sicherlich Punkte die nah nebeneinanderliegen .. aber auch welche die ewig weit weg sind. Es handelt sich ja um 3D-Aufnahmen.
Vom Prinzip her möchte ich also diese beiden Bilder übereinanderlegen - und wenn zwei Punkte sich so nahe kommen,dass sie inklusive Messungenauigkeit etc.
fast beieinander liegen, dass sage ich das ist derselbe Punkt -> der für das gleiche Element im Bild steht.
Nur wenn in dem einen Bild ein Punkt nicht mit dem Punkt aus dem anderen Bild zur Deckung gebracht werden, kann soll der in die Rubrik anders.

Sprich: einmal Haus ohne Schnee, einmal Haus mit Schnee und ich will den Schnee abtrennen (und das Messgerät hat nen gewissen Versatz drin, sodass ich nicht genau weiß, was wirklich Schnee ist oder nur Unterschied aufgrund des Versatzes...daher die Annäherung über einen Art Toleranzwert)

Stimmt, du hast recht. Für "anders" müsste es "if length > limit" heißen, oder?

Leider muss ich sagen, dass ich Deinen Code nicht so ganz verstehe.. wäre es möglich, dass Du mir erklärst, was Du damit machst?
Für den B-Tree informiere ich mich gerade ;)


@BlackJack: Denke nicht, dass das möglich ist, da die Punkte sehr inhomogen verteilt sind (das Endbild ist aus mehreren Bildern mit unterschiedlicher Auflösung zusammengesetzt- die Punktdichte ist unterschiedlich) Und die von mir gesuchten unterschiede sind recht fein. Nicht, dass ich diese dann durch das Raster schon rauskicke.


Aber schon mal vielen Dank für Eure raschen Antworten!
Benutzeravatar
diesch
User
Beiträge: 80
Registriert: Dienstag 14. April 2009, 13:36
Wohnort: Brandenburg a.d. Havel
Kontaktdaten:

Re: Welches Verfahren beschleunigt am besten diesen Code

Beitragvon diesch » Sonntag 3. Mai 2015, 20:07

Wenn du die Punkte in "nachher" nach z.B. x-Koordinate sortierst, kannst du für jeden Punkt a nach dem ersten Punkt mit x => a.x - limit suchen und dann alle Punkte bis x >= a.x + limit prüfen. Das sollte deutlich schneller sein als die innere for-Schleife.
Benutzeravatar
googol
User
Beiträge: 6
Registriert: Montag 16. November 2015, 17:30
Kontaktdaten:

Re: Welches Verfahren beschleunigt am besten diesen Code

Beitragvon googol » Montag 16. November 2015, 20:39

"divide et impera" , bin aber mit der Effizienz von numpy nicht vertraut:
Nach dem Motto:
Nachdem die Dubletten aussortiert sind:
ai,bi jeweils Punkte bestehend aus Koordinaten aus den Dateien A und B:
Baue eine neue Liste aus Punkten, deren eukl. Abstand geringer ist als int-Grenze eps1 (mit dem Wert würde ich länger rumprobieren), in der Form
[ [a1,[b5,b7]] , [ a2, [b29,b31]], [a3, []], ... [an,[b19,b23]] ].

Jetzt wieder die ursprünglichen Fließkommawerte hernehmen und mit eps2 ein analoges Spiel nochmal, allerdings diesmal mit den floats auf der o.generierten Sollmenge.

Für noch höhere Rechengeschwindigkeit fielen mir nur Quader der Form [x1,y1,[z1-eps1,z1+eps1]] und wiederholte Anwendung (und Granulierung über floats) dieses Prinzips, z.B. alle Koordinaten, auf Int-Werten über erhaltene Schnittmengen ein.

Ich kenne jetzt natürlich die Quelle und Natur Deiner Daten nicht, aber wenn sich das z.B. im mm-Bereich bewegt müsstest Du, um die o.g. int-Abkürzung zu nutzen, das Komma vorher entsprechend verschieben.
Wer nicht fragt, bleibt dumm. :D

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder