Trasformare una matrice binaria in un vettore del ultimo indice diverso da zero in modo rapido, la moda vettorizzati

Question

Supponiamo che, in MATLAB, che ho una matrice, A, i cui elementi sono 0 o 1.

Come si arriva un vettore dell'indice dell'ultimo elemento diverso da zero di ciascuna colonna in un modo più veloce e vettoriale?

ho potuto fare

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

e usare I, ma c'è un modo più veloce? (Suppongo che cumsum costerebbe un po 'di tempo persino a decantare gli 0 e gli 1).

Edit: credo che mi Vettorializzare anche più di quanto ho bisogno veloce - ciclo Mr Fooz' è grande, ma ogni ciclo in MATLAB sembra costare me molto nel tempo, anche se è veloce debug.

Answer 1

Come mostrato da Mr Fooz, per i loop può essere abbastanza veloce ora con le versioni più recenti di MATLAB. Tuttavia, se si vuole veramente avere il codice vettorizzati compatto, vorrei suggerire di provare questa:

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

Questo è più veloce di quanto la vostra risposta cumSum-based, ma ancora non abbastanza veloce come le opzioni di loop di Mr Fooz.

Due cose aggiuntive da considerare:

• Quali risultati si vuole ottenere per una colonna che non ha quelle in esso a tutti? Con la suddetta opzione che ti ho dato, credo che otterrai un indice di dimensioni (A, 1) (ovvero il numero di righe in A) in questo caso. Per vostra scelta, credo che otterrete un 1 in tal caso, mentre l'opzione nested-for-loops di Mr Fooz vi darà 0. 0.

• La velocità relativa di queste diverse opzioni probabilmente varierà in base a la dimensione di A e il numero di non zero che ci si aspetta che abbia.

Answer 2

Il fast è ciò di cui dovresti preoccuparti, non necessariamente la completa vettorizzazione. Le versioni recenti di Matlab sono molto più intelligenti su come gestire i loop in modo efficiente. Se c'è un modo vettoriale compatto di esprimere qualcosa, di solito è più veloce, ma i loop non dovrebbero (sempre) essere temuti come un tempo.

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

Su R2008a, Windows, x64, la versione cumSum richiede 0,9 secondi. Il ciclo e la versione di ricerca impiegano 0,02 secondi. La versione a doppio loop richiede solo 0,001 secondi.

EDIT: Qual è il più veloce dipende dai dati effettivi. Il doppio ciclo richiede 0,05 secondi quando si cambia da 0,5 a 0,999 (perché in media ci vuole più tempo per battere la pausa). cumsum e il loop & trovano un'implementazione con più velocità coerenti.

EDIT 2: soluzione flipud di gnovice è intelligente. Sfortunatamente, sulla mia macchina di prova ci vogliono 0,1 secondi, quindi è molto più veloce di cumsum, ma più lento delle versioni ad anello.