Oktave: Abstand zwischen zwei Vektormatrizen berechnen

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

performance octave vectorization 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

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

@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

Wie wäre es mit octave.sourceforge.net/statistics/function/pdist.html

Nemo

Antworten:

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

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