Включение бинарной матрицы в вектор последнего ненулевого индекса в быстром, векторизованном моды

Question

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

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

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

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

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

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

Answer 1

Как показано на рисунке 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 и количество ненулевых вы ожидаете от него.

Answer 2

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, но медленнее, чем петлевые версии.