Эффективное выделение массивов в MATLAB

Одна из первых вещей, которые хорошо узнают о программировании в MATLAB, заключается в том, чтобы избежать динамического изменения размеров массивов. Стандартный пример следующий.

N = 1000;

% Method 0: Bad
clear a
for i=1:N
    a(i) = cos(i);
end

% Method 1: Better
clear a; a = zeros(N,1);
for i=1:N
    a(i) = cos(i)
end

Для варианта "Bad" требуется время O (N ^ 2), так как оно должно выделять новый массив и копировать старые значения на каждой итерации цикла.

Моя собственная предпочтительная практика, когда отладка заключается в распределении массива с NaN, сложнее путать с допустимым значением, чем 0.

% Method 2: Easier to Debug
clear a; a = NaN(N,1);
for i=1:N
    a(i) = cos(i)
end
Тем не менее, можно было бы наивно полагать, что как только наш код отлаживается, мы теряем время, выделяя массив, а затем заполняя его 0 или NaN. Как отмечено здесь, вы можете создать неинициализированный массив следующим образом 
% Method 3 : Even Better?
clear a; a(N,1) = 0;
for i=1:N
    a(i) = cos(i);
end

Однако в моих собственных тестах (MATLAB R2013a) я не вижу заметной разницы между методами 1 и 3, в то время как метод 2 занимает больше времени. Это говорит о том, что MATLAB избегала явной инициализации массива до нуля, когда вызывается a = zeros(N,1).

Таким образом, мне любопытно узнать

  • Каков оптимальный способ переназначения (неинициализированного) массива в MATLAB? (Самое главное, большие массивы)
  • Это также относится к Octave?

Ответы

Ответ 1

Тест

Используя MatLab 2013b я и Intel Xeon 3.6GHz + 16GB RAM, я запустил код ниже в профиль. Я выделил 3 метода и рассмотрел только 1D массивы, т.е. Векторы. Методы 1 и 2 были протестированы с использованием как векторов столбцов, так и векторов строк, то есть (n, 1) и (1, n).

Способ 1 (M1R, M1C)

a = zeros(1,n);

Способ 2 M2R, M2C

a = NaN(1,n);

Способ 3 (M3)

a(n) = 0;

Результаты

Результаты синхронизации и количество элементов были нанесены на диаграмму с правильной логарифмической шкалой на рисунке 1D.

timings1d

Как показано, третий метод имеет назначение, почти не зависящее от размера вектора, в то время как другое неуклонно увеличивается, предполагая неявное определение вектора.

Обсуждение

MatLab делает много оптимизации кода, используя JIT (как раз вовремя), то есть оптимизацию кода во время выполнения. Таким образом, вопрос заключается в том, чтобы определить, действительно ли часть кода работает быстрее из-за программирования (всегда то же, независимо от того, оптимизирована или нет) или из-за оптимизации. Для проверки этой оптимизации можно отключить, используя функцию ( "ускорить", "выключить" ). Результаты запуска кода снова довольно интересны:

timings1Dnoacceleration

Показано, что теперь метод 1 является оптимальным, как для векторов строк и столбцов. И метод 3 ведет себя как другие методы в первом тесте.

Заключение

Оптимизация предопределения памяти бесполезна и пустая трата времени, так как MatLab будет оптимизировать для вас в любом случае.

Обратите внимание, что память должна быть предварительно выделена, но способ, которым вы это делаете, не имеет значения. Производительность предварительно распределяющей памяти во многом зависит от того, хочет ли JIT-компилятор MatLab оптимизировать ваш код или нет. Это полностью зависит от всего другого содержимого вашего .m файла, поскольку компилятор в это время рассматривает куски кодов, а затем пытается оптимизировать (у него даже есть память, так что запуск файла несколько раз может привести к еще более низкому исполнению - время). Кроме того, предварительное распределение памяти чаще всего является очень коротким процессом, рассматривающим производительность по сравнению с выполненным впоследствии вычислением.

По моему мнению, память должна быть предварительно назначена либо с использованием метода 1, либо с помощью метода 2 для поддержания читаемого кода и использования функции, которую предлагает MatLab, поскольку они наиболее вероятно будут улучшены в будущем.

Используемый код

clear all
clc
feature('accel','on')

number1D=30;

nn1D=2.^(1:number1D);

timings1D=zeros(5,number1D);

for ii=1:length(nn1D);
    n=nn1D(ii);
    % 1D
    tic
    a = zeros(1,n);
    a(randi(n,1))=1;
    timings1D(1,ii)=toc;
    fprintf('1D row vector method1 took: %f\n',timings1D(1,ii))
    clear a

    tic
    b = zeros(n,1);
    b(randi(n,1))=1;
    timings1D(2,ii)=toc;
    fprintf('1D column vector method1 took: %f\n',timings1D(2,ii))
    clear b

    tic
    c = NaN(1,n);
    c(randi(n,1))=1;
    timings1D(3,ii)=toc;
    fprintf('1D row vector method2 took: %f\n',timings1D(3,ii))
    clear c

    tic
    d = NaN(n,1);
    d(randi(n,1))=1;
    timings1D(4,ii)=toc;
    fprintf('1D row vector method2 took: %f\n',timings1D(4,ii))
    clear d

    tic
    e(n) = 0;
    e(randi(n,1))=1;
    timings1D(5,ii)=toc;
    fprintf('1D row vector method3 took: %f\n',timings1D(5,ii))
    clear e
end
logtimings1D = log10(timings1D);
lognn1D=log10(nn1D);
figure(1)
clf()
hold on
plot(lognn1D,logtimings1D(1,:),'-k','LineWidth',2)
plot(lognn1D,logtimings1D(2,:),'--k','LineWidth',2)
plot(lognn1D,logtimings1D(3,:),'-.k','LineWidth',2)
plot(lognn1D,logtimings1D(4,:),'-','Color',[0.6 0.6 0.6],'LineWidth',2)
plot(lognn1D,logtimings1D(5,:),'--','Color',[0.6 0.6 0.6],'LineWidth',2)
xlabel('Number of elements (log10[-])')
ylabel('Timing of each method (log10[s])')
legend('M1R','M1C','M2R','M2C','M3','Location','NW')
title({'Various methods of pre-allocation in 1D','nr. of elements vs timing'})
hold off

Примечание

Строки, содержащие c(randi(n,1))=1; не делайте ничего, кроме присвоения значения одному случайному элементу в предварительно выделенном массиве, чтобы массив использовался, чтобы немного бросить вызов компилятору JIT. Эти линии не влияют на измерение предварительного распределения значительно, то есть они не измеряются и не влияют на тест.

Ответ 2

Как насчет того, чтобы Matlab позаботился о вас для распределения?

clear a;
for i=N:-1:1
    a(i) = cos(i);
end

Затем Matlab может выделять и заполнять массив тем, что, по его мнению, будет оптимальным (возможно, нулевым). Однако у вас нет возможности отладки NaNs.