matlab - 为什么这么快？

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 秒。

值得一提的是，许多其他具有可调整大小数组的语言会根据数组的当前大小按 block 分配额外空间，因此通过一次添加一个元素来构建数组的成本仅为 O(n log n)，所以这是 Matlab 的一个特殊缺陷。