Производительность замены двух элементов в MATLAB

Question

В качестве эксперимента я пишу функции сортировки в MATLAB, а затем запускаю их через профилировщик MATLAB. Аспект, который я нахожу наиболее озадачивающим, связан со сменой элементов.

Я обнаружил, что "официальный" способ обмена двух элементов в матрице

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

работает намного медленнее, чем в четырех строках кода:

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

Общее время, затрачиваемое во втором примере, в 12 раз меньше, чем в одной строке кода в первом примере.

Будет ли у кого-нибудь объяснение, почему?

Answer 1

На основании опубликованных предложений я провел еще несколько тестов. Похоже, что снижение производительности происходит, когда одна и та же матрица указана в LHS и RHS назначения.

Моя теория состоит в том, что MATLAB использует внутренний механизм подсчета ссылок / копирования при записи, и это вызывает внутреннее копирование всей матрицы, когда на нее ссылаются с обеих сторон. (Это предположение, потому что я не знаю, что такое MATLAB).

Вот результаты вызова функции 885548 раз. (Разница здесь в четыре раза, а не в двенадцать, как я первоначально разместил. Каждая из функций имеет дополнительные издержки переноса функций, в то время как в моем первоначальном посте я просто суммировал отдельные строки).

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

Вот код:

 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

В первом (медленном) подходе значение RHS является матрицей, поэтому я думаю, что MATLAB влечет за собой снижение производительности при создании новой матрицы для хранения двух элементов. Второй (быстрый) подход позволяет избежать этого, работая напрямую с элементами.

Ознакомьтесь со статьей " Методы повышения производительности " на MathWorks, чтобы узнать о способах улучшения кода MATLAB.

Answer 3

Этот пост заслуживает обновления, так как JIT-компилятор теперь является чем-то особенным ( с R2015b ) и поэтому timeit ( с R2013b ) для более надежной синхронизации функций. 1006 *

Ниже приведена краткая сравнительная функция для замены элементов в большом массиве. Я использовал термины «прямая замена» и «использование временной переменной», чтобы описать два метода в вопросе соответственно.

Результаты довольно ошеломляющие, производительность прямого обмена 2-мя элементами все более ухудшается по сравнению с использованием временной переменной.

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

Answer 4

Зак потенциально прав в том, что для выполнения первой операции может быть сделана временная копия матрицы, хотя я рискну предположить, что в MATLAB есть некоторая внутренняя оптимизация, которая пытается этого избежать. Это может быть функцией версии MATLAB, которую вы используете. Я попробовал оба ваших случая в версии 7.1.0.246 (пара лет) и увидел разницу в скорости только около 2-2,5.

Вполне возможно, что это может быть примером улучшения скорости с помощью так называемой "развертки петли". При выполнении векторных операций на некотором уровне во внутреннем коде, скорее всего, есть цикл FOR, который зацикливается на индексах, которые вы меняете. Выполняя скалярные операции во втором примере, вы избегаете любых накладных расходов от циклов. Обратите внимание на эти два (несколько глупых) примера:

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;

По общему признанию, было бы намного проще просто использовать векторные операции, такие как:

vec = vec+1;

но приведенные выше примеры приведены с целью иллюстрации. Когда я повторяю каждый пример несколько раз и проверяю их время, пример 2 на самом деле несколько быстрее, чем пример 1. Для небольшого цикла с известным числом (в примере только 4) фактически может быть более эффективно отказаться от цикла. Конечно, в этом конкретном примере приведенная выше векторная операция на самом деле самая быстрая.

Я обычно следую этому правилу: попробуйте несколько разных вещей и выберите самый быстрый для вашей конкретной проблемы.

Answer 5

Вы также можете сделать:

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