Abstand Vektor/Matrix < Matlab < Mathe-Software < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:52 Fr 25.04.2008 | | Autor: | mp666 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich habe folgendes Problem. Ich habe hier 2 Matrizen der Dimension (grob geschätzt:) 90000x3 und nun möchte ich den kürzesten Abstand der einzelnen Punkte der einen Matrix zu den Punkten der anderen Matrix.
Mein Code sieht im Moment folgendermaßen aus :
[m,n] = size(matrix1);
[o,p] = size(matrix2);
for i=(1:m)
for k=(1:o)
count(k,:) = norm(matrix2(k,:) - matrix1(i,:));
end
ausgabe(i,1) = min(count);
end
Das Problem hierbei ist, es dauert unendlich lange. Die beiden Matrizen entsprechen 2 Ebenen, welche nicht sooo weit auseinander liegen und somit ist es quatsch, dass auch die beiden entferntesten Punkte miteinander berechnet werden.
Kann man den Code irgendwie optimieren, so dass unnötige Berrechnungen gar nicht erst durchgeführt werden?
MFG
MP
|
|
| |
|
Hallo,
du kannst auf jeden Fall die innere for-Schleife beseitigen, indem du den Vektor aus der äußeren Schleife per repmat auf dieselbe Größe wie matrix2 bringst und so alle Entfernungen zwischen dem einen Vektor und allen Vektoren aus matrix2 auf einen Schlag berechnest.
Außerdem solltest du alle Matrizen, die du Element für Element füllst, mit der richtigen Größe vorinitialisieren, da das Anpassen der Größe zur Laufzeit relative lange dauert und eine richtige Leistungsbremse ist.
Außerdem musst du nicht direkt das Minimum des euklidischen Abstands berechnen. Es reicht schon, wenn du die Summe der Differenzenquadrate berechnest und minimierst. Dann musst du nur noch aus diesem einen Wert die Wurzel ziehen (also nicht norm benutzen).
Mit diesem Ansatz bin ich schon auf immerhin ca. 20 Minuten gekommen (bei gleichverteilten Zufallsdaten, je 90000 Vektoren pro Matrix).
Wenn du nun aber auf unter eine Minute kommen willst, dann empfehle ich folgendes:
Unterteile den Raum, in dem die Daten von matrix2 liegen, durch ein 3D-Gitter (also min/max-x/y/z bestimmen und dazwischen Grenzen ziehen). Bei jedem Vektor aus matrix1 bestimmst du anhand dieser Grenzen, in welchem der kleinen Würfel im Gitter der Punkt liegt und berechnest nur noch die Abstände zu den matrix2-Vektoren in diesem Würfel und den angrenzenden Würfeln.
Ich habe für gleichverteilte Zufallsdaten den gesamten "Datenwürfel" in 15 Teile in x-, y- und z-Richtung unterteilt und konnte die Minimalabstände in einer knappen Minute berechnen. Also recht schnell für die große Datenmenge, denke ich.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 10:20 Mo 28.04.2008 | | Autor: | mp666 |
| Aufgabe | Wenn du nun aber auf unter eine Minute kommen willst, dann empfehle ich folgendes:
Unterteile den Raum, in dem die Daten von matrix2 liegen, durch ein 3D-Gitter (also min/max-x/y/z bestimmen und dazwischen Grenzen ziehen). Bei jedem Vektor aus matrix1 bestimmst du anhand dieser Grenzen, in welchem der kleinen Würfel im Gitter der Punkt liegt und berechnest nur noch die Abstände zu den matrix2-Vektoren in diesem Würfel und den angrenzenden Würfeln.
Ich habe für gleichverteilte Zufallsdaten den gesamten "Datenwürfel" in 15 Teile in x-, y- und z-Richtung unterteilt und konnte die Minimalabstände in einer knappen Minute berechnen. Also recht schnell für die große Datenmenge, denke ich.
|
Hi,
Danke für die Antwort. Also das Vorinitialisieren mit Nullen der Ausgabematrix ist vorher schon geschehen.
Das Prinzip mit den Differenzquadraten, lautet die Formel dann so:
count(k) = sqrt( [mm] (matrix2(k,1)-matrix1(i,1))^2 [/mm] + [mm] (matrix2(k,2)-matrix1(i,2))^2 [/mm] + [mm] (matrix2(k,3)-matrix1(i,3))^2 [/mm] );
ausgabe(i) = min(count(k));
Die Idee mit Matrix2 ind kleine "Würfel" zu unterteilen ist im Prinzip genau die Lösung, nach der ich gesucht habe, leider weiß ich echt nicht, wie das als Code aussieht  Wäre also für ein Codefragment, welches ich da einbauen kann sehr sehr dankbar.
Und wie genau funktioniert der Befehl repmap bzw. was genau macht der, das konnte ich aus der Hilfe nicht genau herauslesen.
MFG
MP
|
|
|
| |
|
Hallo,
wirf mal einen Blick auf ![[a]](/images/paperclip.gif "Dateianhänge") meine Funktion. Du kannst sie erstmal mit kleinen Punktmatrizen testen, um zu sehen, ob diese nicht evtl. noch transponiert werden müssen, um mit meiner Funktion verarbeitet werden zu können.
Gruß
Martin
Dateianhänge:
Anhang Nr. 1 (Typ: m) [nicht öffentlich]
|
|
|
|
