Превращение двоичной матрицы в вектор последнего ненулевого индекса быстрым векторизованным способом - PullRequest
Новая
       22

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

9 голосов
/ 07 мая 2009

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

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

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

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

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

Редактировать: Полагаю, я векторизовал даже больше, чем нужно быстро - цикл мистера Фуза хорош, но каждый цикл в MATLAB, кажется, стоит мне много времени на отладку даже если это быстро.

Ответы [ 2 ]

10 голосов
/ 07 мая 2009

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

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

7 голосов
/ 07 мая 2009

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

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

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

Две дополнительные вещи для рассмотрения:

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

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

...