Performances d'échange de deux éléments dans MATLAB

Question

A titre expérimental, j'écris des fonctions de tri dans MATLAB puis je les exécute dans le profileur MATLAB. L'aspect que je trouve le plus perplexe est de faire avec des éléments d'échange.

J'ai trouvé que la façon « officielle » d'échanger deux éléments dans une matrice

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

fonctionne beaucoup plus lentement que de le faire en quatre lignes de code:

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

La longueur totale de temps pris par le second exemple est 12 fois moins que la seule ligne de code dans le premier exemple.

Quelqu'un pourrait-il expliquer pourquoi?

Answer 1

Basé sur des suggestions postées, j'ai effectué quelques tests supplémentaires. Il semble que le coup de performance survienne lorsque la même matrice est référencée à la fois dans le LHS et le RHS de l'affectation. Ma théorie est que MATLAB utilise un mécanisme interne de comptage de références/copie sur écriture, ce qui provoque la copie interne de la matrice entière lorsqu'elle est référencée des deux côtés. (Ceci est une supposition car je ne connais pas les internes de MATLAB).

Voici les résultats de l'appel de la fonction 885548 fois. (La différence ici est quatre fois, pas douze fois, comme je l'ai écrit à l'origine.) Chacune des fonctions a le surcouple de fonctions, alors que dans mon post initial je viens de résumer les lignes individuelles.

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

Voici le 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

Dans la première approche (lente), la valeur RHS est une matrice, donc je pense que MATLAB encourt une pénalité de performance en créant une nouvelle matrice pour stocker les deux éléments. La deuxième approche (rapide) évite cela en travaillant directement avec les éléments.

Consultez l'article "Techniques for Improving Performance" sur MathWorks pour savoir comment améliorer votre code MATLAB.

Answer 3

vous pouvez aussi le faire:

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

Answer 4

Zach est potentiellement droit en ce qu'une copie temporaire de la matrice peut être faite pour effectuer la première opération, bien que je hasarder une hypothèse qu'il existe une certaine optimisation interne au sein MATLAB qui tente d'éviter cela. Cela peut être une fonction de la version de MATLAB que vous utilisez. J'ai essayé vos deux cas dans la version 7.1.0.246 (quelques années) et j'ai seulement vu une différence de vitesse d'environ 2-2.5.

Il est possible que ce soit un exemple d'amélioration de la vitesse par ce que l'on appelle le "déroulement de la boucle". Lorsque vous faites des opérations vectorielles, à un certain niveau dans le code interne, il y a probablement une boucle FOR qui boucle sur les indices que vous permutez. En effectuant les opérations scalaires dans le second exemple, vous évitez toute surcharge des boucles. Notez ces deux (un peu stupides) exemples:

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; 

Certes, il serait beaucoup plus facile à utiliser simplement des opérations vectorielles comme:

vec = vec+1; 

mais les exemples ci-dessus aux fins d'illustration. Lorsque je répète plusieurs fois l'exemple et que je les chronomètre, l'exemple 2 est un peu plus rapide que l'exemple 1. Pour une petite boucle avec un nombre connu (dans l'exemple, 4), il peut être plus efficace de renoncer à la boucle. Bien sûr, dans cet exemple particulier, l'opération vectorielle donnée ci-dessus est en réalité la plus rapide.

En général, je suis la règle suivante: Essayez plusieurs choses et choisissez la plus rapide pour votre problème spécifique.

Answer 5

Ce poste mérite une mise à jour, puisque le compilateur JIT est maintenant une chose (since R2015b) et est donc timeit (since R2013b) pour la synchronisation de fonction plus fiable. Ci-dessous est une fonction d'analyse comparative pour l'échange d'éléments dans un grand réseau. J'ai utilisé les termes «échange direct» et «utilisation d'une variable temporaire» pour décrire respectivement les deux méthodes de la question.

Les résultats sont assez stupéfiants, la performance de l'échange direct de 2 éléments utilisant est de plus en plus médiocre par rapport à l'utilisation d'une variable temporaire.

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