Почему это намного быстрее?

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

Релиз MATLAB для R2011a делает подобные вещи намного быстрее (что? Вы еще не получили этот релиз? Загрузите!), См. Примечание к выпуску .На моей машине первый цикл занимает 0,02 секунды, а второй - 0,004 секунды.Таким образом, предварительное распределение все еще хорошая идея, но вы не будете в таком плохом месте, если не сможете этого сделать.

Answer 2

Наибольшая стоимость в вашем первом цикле на самом деле связана с динамическим изменением размера массива 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 секунды для векторизованной версии и 0,010 секунды для цикла с памятью для предварительно выделенного tester.

Стоит отметить, что многие другие языки с массивами с изменяемыми размерами выделяют дополнительное пространство в блоках, пропорционально текущему размеру массива, поэтому стоимость создания массива путем добавления одного элемента за раз составляет всего O (n log n), так что это особый недостаток Matlab.