Wydajność zamiany dwóch elementów w MATLAB

Question

Czysto jako eksperyment, piszę funkcje sortowania w MATLAB, a następnie uruchamiam je za pomocą profilera MATLAB. Aspekt, który najbardziej wprawia mnie w zakłopotanie, ma związek z zamianą elementów.

Odkryłam, że „oficjalny” sposób zamiana dwóch elementów w macierzy

self.Data([i1, i2]) = self.Data([i2, i1]) 

przebiega znacznie wolniej niż robi to w czterech liniach kodu:

e1 = self.Data(i1); 
e2 = self.Data(i2); 
self.Data(i1) = e2; 
self.Data(i2) = e1; 

całkowita długość czasu podjętego przez drugi przykład jest 12 razy mniejszy niż pojedyncza linia kodu w pierwszym przykładzie.

Czy ktoś ma wyjaśnienie, dlaczego?

Answer 1

Na podstawie opublikowanych sugestii przeprowadziłem kilka dodatkowych testów. Wygląda na to, że wydajność osiąga się, gdy ta sama macierz jest przywoływana zarówno w LHS, jak i w RHS zadania.

Moja teoria mówi, że MATLAB wykorzystuje wewnętrzny mechanizm liczenia referencji/kopiowania przy zapisie, a to powoduje, że cała macierz jest kopiowana wewnętrznie, gdy jest przywoływana po obu stronach. (To jest domysły, ponieważ nie znam elementów wewnętrznych MATLAB).

Oto wyniki wywołania funkcji 885548 razy. (Różnica polega na tym, że cztery razy, a nie dwanaście, jak pierwotnie napisałem, każda z funkcji ma dodatkową funkcję owijania w głowie, podczas gdy w moim pierwszym wpisie właśnie podsumowałem poszczególne linie).

 
swap1: 12.547 s 
swap2: 14.301 s 
swap3: 51.739 s 

Oto kod:

methods (Access = public) 
    function swap(self, i1, i2) 
     swap1(self, i1, i2); 
     swap2(self, i1, i2); 
     swap3(self, i1, i2); 
     self.SwapCount = self.SwapCount + 1; 
    end 
end 

methods (Access = private) 
    % 
    % swap1: stores values in temporary doubles 
    %   This has the best performance 
    % 
    function swap1(self, i1, i2) 
     e1 = self.Data(i1); 
     e2 = self.Data(i2); 
     self.Data(i1) = e2; 
     self.Data(i2) = e1; 
    end 

    % 
    % swap2: stores values in a temporary matrix 
    %  Marginally slower than swap1 
    % 
    function swap2(self, i1, i2) 
     m = self.Data([i1, i2]); 
     self.Data([i2, i1]) = m; 
    end 

    % 
    % swap3: does not use variables for storage. 
    %  This has the worst performance 
    % 
    function swap3(self, i1, i2) 
     self.Data([i1, i2]) = self.Data([i2, i1]); 
    end 


end 

Answer 2

W pierwszym (powolnym) podejściu wartość RHS jest macierzą, więc myślę, że MATLAB ponosi karę wykonania w tworzeniu nowej macierzy do przechowywania dwóch elementów. Drugie (szybkie) podejście pozwala tego uniknąć, pracując bezpośrednio z elementami.

Zapoznaj się z artykułem "Techniques for Improving Performance" na temat MathWorks, aby znaleźć sposób na ulepszenie kodu MATLAB.

Answer 3

można również zrobić:

tmp = self.Data(i1); 
self.Data(i1) = self.Data(i2); 
self.Data(i2) = tmp; 

Answer 4

Zach jest potencjalnie rację, że tymczasowa kopia matrycy może być wykonana, aby wykonać pierwszą operację, chociaż chciałbym zgadywać, że istnieje jakiś wewnętrzny optymalizacji zasięgu MATLAB, który próbuje tego uniknąć. Może to być funkcja wersji MATLAB, której używasz. Próbowałem obu twoich przypadków w wersji 7.1.0.246 (kilka lat) i widziałem tylko różnicę prędkości około 2-2,5.

Jest możliwe, że może to być przykład poprawy prędkości dzięki tak zwanemu "rozwijaniu pętli". Podczas wykonywania operacji wektorowych, na pewnym poziomie wewnątrz kodu wewnętrznego istnieje prawdopodobnie pętla FOR, która pętli nad indeksami, które wymieniasz. Wykonując operacje skalarne w drugim przykładzie, unikasz jakiegokolwiek narzutu z pętli. Uwaga te dwie (nieco głupie) Przykłady:

vec = [1 2 3 4]; 

%Example 1: 
for i = 1:4, 
    vec(i) = vec(i)+1; 
end; 

%Example 2: 
vec(1) = vec(1)+1; 
vec(2) = vec(2)+1; 
vec(3) = vec(3)+1; 
vec(4) = vec(4)+1; 

Wprawdzie byłoby znacznie łatwiej po prostu użyć operacji wektorowej jak:

vec = vec+1; 

ale przykłady powyżej są dla celów ilustracji. Kiedy powtarzam każdy przykład wiele razy i czas, przykład 2 jest w rzeczywistości nieco szybszy niż w przykładzie 1. Dla małej pętli o znanej liczbie (w przykładzie, tylko 4), może być skuteczniej zrezygnować z pętli. Oczywiście w tym konkretnym przykładzie operacja wektorowa podana powyżej jest w rzeczywistości najszybsza.

Zwykle przestrzegam tej zasady: wypróbuj kilka różnych rzeczy i wybierz najszybszy dla konkretnego problemu.

Answer 5

Ten post zasługuje aktualizacji, ponieważ kompilator JIT jest obecnie rzeczą (since R2015b) i tak jest timeit (since R2013b) dla bardziej wiarygodnego harmonogramu funkcji.

Poniżej przedstawiono krótką analizę porównawczą dla zamiany elementów w dużej tablicy. Użyłem terminów "bezpośrednio zamieniając" i "używając zmiennej tymczasowej", aby opisać odpowiednio dwie metody w pytaniu.

Wyniki są dość zaskakujące, wydajność bezpośredniego zamiany 2 elementów przy użyciu jest coraz słabsza w porównaniu do użycia zmiennej tymczasowej.

function benchie() 
    % Variables for plotting, loop to increase size of the arrays 
    M = 15; D = zeros(1,M); W = zeros(1,M); 
    for n = 1:M; 
     N = 2^n; 
     % Create some random array of length N, and random indices to swap 
     v = rand(N,1); 
     x = randi([1, N], N, 1); 
     y = randi([1, N], N, 1); 
     % Time the functions 
     D(n) = timeit(@()direct); 
     W(n) = timeit(@()withtemp); 
    end 
    % Plotting 
    plot(2.^(1:M), D, 2.^(1:M), W); 
    legend('direct', 'with temp') 
    xlabel('number of elements'); ylabel('time (s)') 

    function direct() 
    % Direct swapping of two elements 
     for k = 1:N 
      v([x(k) y(k)]) = v([y(k) x(k)]); 
     end 
    end 

    function withtemp() 
    % Using an intermediate temporary variable 
     for k = 1:N 
      tmp = v(y(k)); 
      v(y(k)) = v(x(k)); 
      v(x(k)) = tmp; 
     end 
    end 
end