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

Question

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

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

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

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

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

Редактировать: Думаю, я векторизовал даже больше, чем мне нужно быстро.Цикл Fooz великолепен, но каждый цикл в MATLAB, кажется, стоит мне много времени на отладку, даже если она быстрая.

Answer 1

Как показано Мистер Фуз, циклы for теперь могут выполняться довольно быстро в новых версиях MATLAB.Однако, если вы действительно хотите иметь компактный векторизованный код, я бы предложил попробовать следующее:

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

Это быстрее, чем ваш ответ на основе CUMSUM, но все же не так быстро, как варианты цикла мистера Фуза.

Еще две вещи, которые следует учитывать:

• Какие результаты вы хотите получить для столбца, в котором вообще нет столбцов?Я полагаю, что с помощью приведенного выше варианта вы получите индекс размер(А,1) (т.е.количество строк в А) в таком случае.Я полагаю, что в таком случае вы получите 1 для вашего варианта, а вариант с вложенными циклами от Mr Fooz даст вам 0.

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

Answer 2

Вам следует беспокоиться о быстром, а не о полной векторизации. Последние версии 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 секунды.

РЕДАКТИРОВАТЬ . Какой из них наиболее быстрый, зависит от фактических данных. Двойной цикл занимает 0,05 секунды, когда вы изменяете 0,5 на 0,999 (потому что на разрыв требуется больше времени; в среднем). cumsum и реализация цикла & find имеют более согласованные скорости.

РЕДАКТИРОВАТЬ 2: Flipud решение Gnovice является умным. К сожалению, на моей тестовой машине это занимает 0,1 секунды, поэтому это намного быстрее, чем cumsum, но медленнее, чем зацикленные версии.