为什么这么快？

Question

当我在MatLab中执行这些等效操作时,第一个在24.158371秒(for循环)运行.第二个运行在0.004976秒(逻辑索引).MatLab可能会做什么,这使得运行速度更快？这仍然是O(n)时间,对吧？

t = linspace(-2*pi,2*pi,100000);
fd = 1e3;
tau = 1e-6;


% Calculate arbitrary function using a loop
tic
for tind = 1:length(t)
    tester(tind) = cos(2*pi*fd*t(tind))/(2*pi*fd.*t(tind));
end
toc

pause; disp('Press a key');
% Same calculation with logical indexing
tic
tester2 = cos(2*pi*fd.*t)./(2*pi*fd.*t);
toc

Answer 1

第一个循环中的最大成本实际上来自动态调整阵列大小tester.每次循环时,Matlab都必须将现有数组复制到内存中的新位置,并为额外元素留出空间.所以,这是循环的每次迭代的O(n)操作.如果预先分配数组,它将运行得更快,例如

tic
tester = zeros(100000,1);
for tind = 1:length(t)
    tester(tind) = cos(2*pi*fd*t(tind))/(2*pi*fd.*t(tind));
end
toc

在我的系统上,原始循环得到11.3秒,向量化版本得到0.0013秒,带有tester预分配内存的循环得到0.010秒.

值得一提的是,许多其他具有可调整大小的数组的语言在与数组的当前大小成比例的块中分配额外的空间,因此通过一次附加一个元素来构建数组的成本仅为O(n log n),因此这是Matlab的一个特殊缺陷.

Answer 2

R2011a发布的MATLAB让这种事情变得更快(什么？你还没有发布那个版本？下载!),请参阅发行说明.在我的机器上,第一个循环需要0.02秒,第二个循环需要0.004秒.因此,预分配仍然是一个好主意,但如果你不能这样做,你就不会处于相当糟糕的地方.