2009-05-06 8 views
9

Пусть в MATLAB, что у меня есть матрица, A, элементы которого являются либо 0, либо 1.Включение бинарной матрицы в вектор последнего ненулевого индекса в быстром, векторизованном моды

Как получить вектор индекса последнего ненулевого элемента каждого столбца быстрее, векторизован?

я мог бы сделать

[B, I] = max(cumsum(A));

и использовать I, но есть более быстрый способ? (Я предполагаю, что cumsum будет стоить немного времени, даже если подвести 0 и 1).

Edit: Я предполагаю, что я оцифрованный даже больше, чем мне нужно быстро - цикл г Fooz»является большим, но каждый цикл в MATLAB, кажется, стоит мне много отладки времени, даже если это быстро.

ответ

7

Как показано на рисунке Mr Fooz, для петель может быть довольно быстро с новыми версиями MATLAB. Тем не менее, если вы действительно хотите иметь код компактный векторизованную, я предложил бы попробовать это:

[B,I] = max(flipud(A)); 
I = size(A,1)-I+1; 

Это быстрее, чем ваш CUMSUM на основе ответа, но все же не так быстро, как варианты LOOPING г Fooz в.

Две дополнительные вещи, чтобы рассмотреть следующие вопросы:

  • Каких результатов вы хотите получить для столбца, который не имеет близких в нем вообще? С приведенным выше вариантом я дал вам, я считаю, что вы получите индекс размер (A, 1) (т. Е. Количество строк в A) в таком случае. Для вашего варианта, я считаю, что вы получите 1 в таком случае, в то время как опция inested-for-loops от Mr Fooz даст вам 0.

  • Относительная скорость этих разных вариантов, скорее всего, будет зависеть от размер A и количество ненулевых вы ожидаете от него.

+0

Умная идея. К сожалению, это примерно в 5 раз медленнее, чем loop & find. –

+0

Это своего рода результат, который я ожидал: быстрее, чем CUMSUM, но все же медленнее, чем цикл ... хотя он все еще зависит от размера и доли заполнения A (которые OP действительно не определял). – gnovice

10

Fast - это то, о чем вам следует беспокоиться, а не обязательно полной векторизации. В последних версиях Matlab много умнее об управлении петлями. Если есть компактный векторный способ выражения чего-то, он обычно быстрее, но циклы не должны (всегда) бояться, как раньше.

clc 

A = rand(5000)>0.5; 
A(1,find(sum(A,1)==0)) = 1; % make sure there is at least one match 

% Slow because it is doing too much work 
tic;[B,I1]=max(cumsum(A));toc 

% Fast because FIND is fast and it runs the inner loop 
tic; 
I3=zeros(1,5000); 
for i=1:5000 
    I3(i) = find(A(:,i),1,'last'); 
end 
toc; 
assert(all(I1==I3)); 

% Even faster because the JIT in Matlab is smart enough now 
tic; 
I2=zeros(1,5000); 
for i=1:5000 
    I2(i) = 0; 
    for j=5000:-1:1 
    if A(j,i) 
     I2(i) = j; 
     break; 
    end 
    end 
end 
toc; 
assert(all(I1==I2)); 

На R2008a, Windows, x64, версия cumsum занимает 0,9 секунды. Версия цикла и поиска занимает 0,02 секунды. Версия с двойным циклом занимает всего 0,001 секунды.

EDIT: Какой из них наиболее быстр, зависит от фактических данных. Двойной цикл занимает 0,05 секунды, когда вы меняете 0,5 на 0,999 (потому что в среднем требуется больше времени на перерыв). cumsum и петля & Находка реализации имеет более последовательные скорости.

EDIT 2: Решение flnud gnovice является умным. К сожалению, на моей тестовой машине это занимает 0,1 секунды, поэтому она намного быстрее, чем cumsum, но медленнее, чем петлевые версии.

+0

Wow, являются качествами вашей петли, которые делают ее быстрее или любая такая петля является самым быстрым способом любой подобной операции? –

+1

Когда я начал писать примеры, я ожидал, что двойной цикл будет самым медленным, а loop & find будет самым быстрым. Когда внутренний цикл должен работать до завершения, он несколько медленный (см. Изменение 2). В наши дни Matlab делает компиляцию каждой функции вовремя. Это делает цикл намного быстрее (но имеет некоторые неожиданные последствия для людей, которые любят использовать EVAL). В общем, векторизация по-прежнему лучше использовать, если вы можете сделать это без дополнительной работы (решения flipud и cumsum векторизованы, но выполняют дополнительную работу). –

+0

Еще одна интересная вещь: во многих случаях последние версии Matlab умеют разбирать выражения. Е = А. * * Б. С. * D; будет выполняться без дополнительных временных рядов, поэтапно, подобно тому, как вы это сделаете, если вручную записать операцию в C. При включенной поддержке многоядерности Matlab пытается найти непересекающиеся части операции и выработать их для разных Процессорные ядра. Я не знаю, достаточно ли это достаточно, чтобы разделить независимые циклические итерации между вызовами. Для тестов, которые я сделал, я использовал процессор Core 2 Duo. –

 Смежные вопросы

  • Нет связанных вопросов^_^