Transformar uma matriz binária em um vetor do último índice zero de forma rápida, moda vetorizado

Question

Suponha que, em MATLAB, que eu tenho uma matriz, A, cujos elementos são 0 ou 1.

Como faço para obter um vector do índice do último elemento diferente de zero de cada coluna de forma mais rápida, vetorizado?

eu poderia fazer

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

e uso I, mas há uma maneira mais rápida? (Estou assumindo cumSum custaria um pouco de tempo, mesmo suming 0 e 1 do).

Editar: eu acho que eu vetorizado ainda mais do que eu preciso rápido - laço Sr. Fooz' é grande, mas cada loop em MATLAB parece custo me muito em depuração tempo, mesmo que seja rápido.

Answer 1

Como demonstrado por Mr Fooz , para loops pode ser muito rápido agora com versões mais recentes do MATLAB. No entanto, se você realmente quer ter código vectorized compacto, gostaria de sugerir tentar o seguinte:

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

Esta é mais rápido do que a sua resposta baseada cumSum, mas ainda não é tão rápido como opções de looping do Sr. Fooz.

Duas coisas adicionais a considerar:

• Que resultados você deseja obter para uma coluna que não tem mais nele em tudo? Com a opção acima te dei, eu acredito que você vai ter um índice de tamanho (A, 1) (ou seja, o número de linhas em A ) em tal caso. Para sua opção, eu acredito que você vai obter a 1, em tal caso, enquanto a nested-de-lacetes opção do Sr. Fooz lhe dará um.

0

• A velocidade relativa desses diferentes opções provavelmente vai variar de acordo com o tamanho de A e o número de não-zeros que você espera que ele tem.

Answer 2

rápido é o que você deve se preocupar, não necessariamente vetorização completo. As versões recentes do Matlab são muito mais inteligente sobre a manipulação de loops de forma eficiente. Se há uma maneira vectorized compacto de expressar algo, geralmente é mais rápido, mas voltas não deve (sempre) ser temido como costumavam ser.

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));

Em R2008a, Windows x64, a versão cumSum leva 0,9 segundos. A versão loop e achado leva 0,02 segundos. A versão double loop leva apenas 0,001 segundos.

EDIT: Qual deles é o mais rápido depende dos dados reais. O loop duplo leva 0,05 segundos quando você altera o 0,5-,999 (porque leva mais tempo para atingir o break; em média). cumSum eo loop & implementação encontrar têm velocidades mais consistentes.

EDIT 2: solução flipud de gnovice é inteligente. Infelizmente, na minha máquina de teste que leva 0,1 segundos, por isso é muito mais rápido do que cumSum, mas mais lento do que as versões em loop.