MATLAB中的高效数组预分配

Question

在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吗？

Answer 1

考试

使用MatLab 2013b I和Intel Xeon 3.6GHz + 16GB RAM我运行下面的代码进行配置.我区分了3种方法,只考虑了1D阵列,即矢量.已经使用列向量和行向量(即(n,1)和(1,n))测试了方法1和2.

方法1(M1R,M1C)

a = zeros(1,n);

方法2 M2R,M2C

a = NaN(1,n);

方法3(M3)

a(n) = 0;

结果

时序结果和元件数量已经在图形时序1D中以duuble对数标度绘制.

如图所示,第三种方法的分配几乎与矢量大小无关,而另一种方法稳定增加,表明矢量的隐含定义.

讨论

MatLab使用JIT(即时)进行了大量代码优化,即在运行时进行代码优化.因此,提出代码运行速度更快的部分是由于编程(无论是否优化)或优化原因,都是一个有效的问题.要测试此优化,可以使用feature('accel','off')关闭此优化.再次运行代码的结果非常有趣:

结果表明,现在方法1对于行和列向量都是最优的.方法3的行为与第一次测试中的其他方法相似.

结论

优化内存预分配是无用的,浪费时间,因为MatLab无论如何都会为您优化.

请注意,应该预先分配内存,但是执行此操作的方式并不重要.预分配内存的性能在很大程度上取决于MatLab的JIT编译器是否选择优化代码.这完全依赖于.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; 除了将值1分配给预分配数组中的随机元素以外,不要做任何事情,以便使用该数组来挑战JIT编译器.这些线路不会显着影响预分配测量,即它们不可测量且不影响测试.

Answer 2

让 Matlab 为您处理分配怎么样？

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

然后，Matlab 可以使用它认为最佳的值（可能为零）来分配和填充数组。不过，您没有 的调试优势NaNs。