Октава: вычислить расстояние между двумя матрицами векторов

12

Предположим, у меня есть две матрицы Nx2, Mx2, представляющие N, M 2d векторов соответственно. Есть ли простой и хороший способ рассчитать расстояния между каждой векторной парой (n, m)?

Простой, но неэффективный способ, конечно:

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

Самый близкий ответ, который я нашел bsxfun, использовался так:

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 Келли ван Эверт
источник
Я посмотрел на это, и я не мог сделать намного лучше, чем векторизация вычислений. Я думаю, что это вычисление является довольно хорошим кандидатом для написания внешней функции C / Fortran.
Арон Ахмадиа
1
Могу поспорить, что вы могли бы сделать матрицу 2xNxM, которую вы заполнили бы внешним произведением, а затем возвести в квадрат каждую из записей и суммировать по нулевой оси и квадратному корню. В Python это будет выглядеть следующим образом: distance_matrix = (n [:,:, nexaxis] * m [:, newaxis ,:]); distance_matrix = distance_matrix ** 2; distance_matrix = sqrt (distance_matrix.sum (axis = 1)); Если вам нужно знать только ближайшие n-векторы, есть гораздо лучшие способы сделать это!
Meawoppl
3
@meawoppl (новичок в Octave) Я узнал, как использовать пакет линейной алгебры в Octave, который обеспечивает 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) ... который работает намного быстрее!
Келли ван Эверт
Как насчет octave.sourceforge.net/statistics/function/pdist.html
Nemo

Ответы:

6

Векторизация проста в этих ситуациях, используя такую ​​стратегию:

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

Вот пример, который векторизует цикл for с ускорением в 15 раз для M = 1000 и N = 2000.

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))
Дэвид Биндел
источник
Дэвид, рад видеть тебя на scicomp! Я бесстыдно отредактировал ваш фрагмент кода и немного расширил его, пожалуйста, вернитесь, если мои изменения пошли в неправильном направлении от разъяснения того, что вы хотели.
Арон Ахмадиа
2

Начиная с октавы 3.4.3 и более поздних, оператор - осуществляет автоматическое вещание (использует bsxfun для внутреннего использования). Таким образом, вы можете продолжать таким образом.

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

Вы можете сделать то же самое, используя 3D-матрицу, но я думаю, что это более понятно. D - матрица расстояний NxM, каждый вектор в N против каждого вектора в M.

Надеюсь это поможет

Аньор, Хуанпите
источник