Oktave: Abstand zwischen zwei Vektormatrizen berechnen

12

Angenommen, ich habe zwei Matrizen Nx2, Mx2, die jeweils N, M 2d Vektoren darstellen. Gibt es eine einfache und gute Möglichkeit, die Abstände zwischen den einzelnen Vektorpaaren (n, m) zu berechnen?

Der einfache, aber ineffiziente Weg ist natürlich:

d = zeros(N, M);
for i = 1:N,
  for j = 1:M,
    d(i,j) = norm(n(i,:) - m(j,:));
  endfor;
endfor;

Die nächste Antwort, die ich gefunden habe, lautet bsxfunwie folgt :

bsxfun(inline("x-y"),[1,2,3,4],[3;4;5;6])

ans =
  -2 -1  0  1
  -3 -2 -1  0
  -4 -3 -2 -1
  -5 -4 -3 -2
Kelley van Evert
quelle
Ich habe mir das angeschaut und konnte es nicht besser machen, als die Berechnung zu vektorisieren. Ich denke, diese Berechnung ist ein ziemlich guter Kandidat für das Schreiben einer externen C / Fortran-Funktion.
Aron Ahmadia
1
Ich wette, Sie könnten eine 2xNxM-Matrix erstellen, die Sie mit einem äußeren Produkt füllen, dann jeden der Einträge quadrieren und entlang der nullten Achse und der Quadratwurzel summieren. In Python würde dies so aussehen: distance_matrix = (n [:,:, nexaxis] * m [:, newaxis ,:]); distance_matrix = distance_matrix ** 2; distance_matrix = sqrt (distance_matrix.sum (axis = 1)); Wenn Sie nur die nächsten n-Vektoren kennen müssen, gibt es viel bessere Möglichkeiten, dies zu tun!
Meawoppl
3
@meawoppl (Neu bei Octave) Ich habe herausgefunden, wie man das Linear-Algebra- Paket in Octave verwendet, das folgendes bietet cartprod: (1) x = cartprod(n(:,1), m(:,1)); (2) y = cartprod(n(:,2), m(:,2)); (3) ... d = sqrt((x(:,1)-x(:,2)).^2+(y(:,1)-y(:,2)).^2) was viel schneller läuft!
Kelley van Evert

Antworten:

6

Das Vektorisieren ist in diesen Situationen mit einer Strategie wie der folgenden einfach:

eN = ones(N,1);
eM = ones(M,1);
d  = sqrt(eM*n.^2' - 2*m*n' + m.^2*eN');

Hier ist ein Beispiel, das die for-Schleife mit einer 15-fachen Beschleunigung für M = 1000 und N = 2000 vektorisiert.

n = rand(N,2);
m = rand(M,2);
eN = ones(N,2);
eM = ones(2,M);

tic;
d_vect  = sqrt(eN*m.^2' - 2*n*m' + n.^2*eM);
vect_time = toc;

tic;
for i=1:N
  for j=1:M
     d_for(i,j) = norm(n(i,:)-m(j,:));
  end
end
for_time = toc; 

assert(norm(d_vect-d_for) < 1e-10*norm(d_for)) 
David Bindel
quelle
David, schön dich auf scicomp zu sehen! Ich habe Ihr Codefragment schamlos bearbeitet und es ein wenig erweitert. Bitte machen Sie es wieder rückgängig, wenn meine Änderungen in die falsche Richtung gingen und nicht klarstellten, was Sie beabsichtigten.
Aron Ahmadia
2

Ab Octave 3.4.3 sendet der Operator automatisch (verwendet intern bsxfun). So können Sie vorgehen.

Dx = N(:,1) - M(:,1)';
Dy = N(:,2) - M(:,2)';
D = sqrt (Dx.^2 + Dy.^2);

Sie können dasselbe mit einer 3D-Matrix tun, aber ich denke, dies ist klarer. D ist eine NxM-Matrix von Entfernungen, jeder Vektor in N gegen jeden Vektor in M.

Hoffe das hilft

JuanPi
quelle