Как оптимизировать следующий двойной цикл в октаве?

Question

У меня есть следующий код в октаве:

dist=0; 
for i = 1:length(x);   
    for j = 1:length(y); 
     v = x(i,:) - y(j,:); 
     distvect(j) = norm(v); 
    endfor 
    dist = dist + min(distvect); 
endfor 

где х и у матрицы с размером п х 2 и х м 2. Моей главной проблемой: мне нужно запустить код, указанным выше в несколько раз.

Я уверен, что есть способ оптимизировать его с использованием, возможно, только одной матрицы вместо вектора v каждый раз во внутреннем цикле, но я не смог ее найти. Я искал в Интернете, я нашел функцию arrayfun, которая могла бы помочь, но я не мог понять, как ее использовать.

Спасибо за помощь, GRUS

Answer 1

Лучший оптимизации вы можете сделать в этом случае заключается в реализации norm себя, чтобы воспользоваться матричных умножений, а не зацикливание над отдельными элементами.

Напомним, что для значений вектора, norm(v) вычисляет norm(v, 2), что евклидово расстояние

norm(v, 2) = (sum (abs (v) .^ 2))^(1/2) 

Поскольку вам нужно только найти минимальное расстояние, вы на самом деле не нужно, чтобы извлечь квадратный корень, пока позже. Для компактности дайте a = x(i, :), b = y(j, :), M = length(x) и N = length(y). Поскольку переменная v содержит вектор различий, мы можем расширить расчет distvect в

distvect = norm(v) 
      = norm(x(i, :) - y(j, :)) 
      = norm(a - b) 
      = (sum (abs(a - b) .^ 2))^(1/2) 
distvect^2 = sum (abs (a - b) .^ 2) 

Теперь разверните квадратичный член, (a - b)^2 = a^2 - 2ab + b^2, что делает abs функцию избыточных

distvect^2 = sum (sum(a.*a) * ones(1,N) - 2*a*b' + ones(M,1) * sum(b'.*b')) 

Заключительной оптимизацией , чтобы применить функцию к нескольким значениям. Это делается с использованием внешнего продукта ваших матриц x и y, чтобы создать матрицу length(x) на length(y). Затем просто возьмите минимальное расстояние вдоль каждой колонки и суммируйте квадратный корень из результатов.

xx = sum(x .* x, 2) * ones(1, length(y)) 
xy = x * y' 
yy = ones(length(x), 1) * sum(y' .* y') 

dist = sum(sqrt(min(xx - 2.*xy + yy)))