Leistung des Tauschens zweier Elemente in MATLAB

Question

Rein als ein Experiment, schreibe ich Sortierfunktionen in MATLAB dann diese durch den MATLAB Profiler laufen. Der Aspekt, den ich am meisten verblüffend finde, ist der Austausch von Elementen.

Ich habe festgestellt, dass der „offizielle“ Weg, um zwei Elemente von Austausch in einer Matrix

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

läuft viel langsamer als es in vier Zeilen Code tun:

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

Die Gesamtlänge von Zeit, die von dem zweiten Beispiel belegt ist, ist 12 mal weniger als die einzelne Codezeile im ersten Beispiel.

Würde jemand eine Erklärung haben, warum?

Answer 1

Gestützt auf Vorschläge, habe ich noch ein paar Tests durchgeführt. Es scheint, dass der Performance-Hit auftritt, wenn dieselbe Matrix sowohl in der LHS als auch in der RHS der Zuweisung referenziert wird.

Meine Theorie ist, dass MATLAB verwendet einen internen Referenzzählung/Copy-on-Write-Mechanismus, und dies verursacht die gesamte Matrix intern kopiert werden, wenn es auf beiden Seiten verwiesen wird. (Dies ist eine Vermutung, weil ich die MATLAB-Interna nicht kenne).

Hier sind die Ergebnisse aus dem Aufruf der Funktion 885548 mal. (Der Unterschied hier ist mal vier, nicht mal zwölf, wie ich ursprünglich gepostet habe. Jede der Funktionen hat die zusätzliche Funktion-Umhüllungs-Overhead, während ich in meiner ersten Post nur die einzelnen Zeilen summierte).

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

Hier ist der Code:

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

Im ersten (langsamen) Ansatz ist der RHS-Wert eine Matrix, daher denke ich, dass MATLAB beim Erstellen einer neuen Matrix zum Speichern der beiden Elemente eine Leistungseinbuße erleidet. Der zweite (schnelle) Ansatz vermeidet dies, indem direkt mit den Elementen gearbeitet wird.

Überprüfen Sie den Artikel "Techniques for Improving Performance" auf MathWorks für Möglichkeiten, Ihren MATLAB-Code zu verbessern.

Answer 3

Sie könnten auch tun:

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

Answer 4

Zach ist möglicherweise richtig, dass eine temporäre Kopie der Matrix vorgenommen werden kann, die erste Operation durchzuführen, obwohl ich ahne würde, dass es eine interne Optimierung ist innerhalb MATLAB versucht dies zu vermeiden. Es kann eine Funktion der Version von MATLAB sein, die Sie verwenden. Ich habe beide Fälle in der Version 7.1.0.246 (ein paar Jahre alt) ausprobiert und nur einen Geschwindigkeitsunterschied von 2-2,5 gesehen.

Es ist möglich, dass dies ein Beispiel für die Geschwindigkeitsverbesserung ist, was als "Schleifenabrollen" bezeichnet wird. Wenn Vektoroperationen ausgeführt werden, gibt es auf einer Ebene innerhalb des internen Codes wahrscheinlich eine FOR-Schleife, die über die Indizes, die Sie austauschen, eine Schleife bildet. Durch Ausführen der Skalaroperationen im zweiten Beispiel vermeiden Sie jeglichen Overhead von Schleifen. Beachten Sie, diese beiden (etwas albern) Beispiele:

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; 

Zwar wäre es viel einfacher sein, wie Vektor-Operationen zu verwenden:

vec = vec+1; 

aber die Beispiele oben sind zum Zwecke der Veranschaulichung. Wenn ich jedes Beispiel mehrfach wiederhole und zeitlich wiederhole, ist Beispiel 2 tatsächlich etwas schneller als Beispiel 1. Für eine kleine Schleife mit einer bekannten Zahl (im Beispiel nur 4) kann es tatsächlich effizienter sein, auf die Schleife zu verzichten. Natürlich ist in diesem speziellen Beispiel die oben angegebene Vektoroperation tatsächlich die schnellste.

Normalerweise folge ich dieser Regel: Versuchen Sie ein paar verschiedene Dinge, und wählen Sie die schnellste für Ihr spezifisches Problem.

Answer 5

Dieser Beitrag Update verdient, da der JIT-Compiler jetzt eine Sache ist (since R2015b) und so ist timeit (since R2013b) für eine zuverlässigere Funktion Timing.

Unten finden Sie eine kurze Benchmarking-Funktion für das Element-Swapping innerhalb eines großen Arrays. Ich habe die Begriffe "direktes Austauschen" und "Verwenden einer temporären Variablen" verwendet, um die beiden Methoden in der Frage zu beschreiben.

Die Ergebnisse sind ziemlich atemberaubend, die Leistung des direkten Tauschens von zwei Elementen ist im Vergleich zur Verwendung einer temporären Variable zunehmend schlechter.

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