Drehen eine binäre Matrix in einen Vektor des letzten Nicht-Null-Index in einer schnellen, vektorisiert Mode

Question

Nehmen wir an, in MATLAB, dass ich eine Matrix, A, deren Elemente entweder 0 oder 1

Wie erhalte ich einen Vektor des Index des letzten Nicht-Null-Elements jeder Spalte in einem schnelleren, vektorisiert Weg?

ich tun konnte,

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

und verwenden I, aber gibt es einen schnelleren Weg? (Ich gehe davon aus cumsum ein wenig Zeit selbst und 1 ist Suming 0 kosten würde).

Edit: Ich denke, dass ich vektorisiert sogar mehr, als ich schnell brauchen - Mr. Fooz‘Schleife groß ist, aber jede Schleife in MATLAB scheint kosten me eine Menge in Debugging-Zeit, auch wenn es schnell ist.

Answer 1

Wie Herr Fooz , für Schleifen ziemlich schnell jetzt mit neueren Versionen von MATLAB sein können. Wenn Sie jedoch wirklich kompakten vektorisiert Code haben wollen, würde ich dies vorschlagen versuchen:

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

Dies ist schneller als Ihre cumSum basierte Antwort, aber immer noch nicht ganz so schnell wie Herr Fooz des Looping-Optionen.

Zwei weitere Dinge zu beachten:

• Welche Ergebnisse haben Sie für eine Spalte erhalten möchten, die überhaupt keine Einsen in ihm hat? Mit der obigen Option gab ich Ihnen, ich glaube, Sie werden einen Index von erhalten Größe (A, 1) (das heißt die Anzahl der Zeilen in A ) in einem solchen Fall. Für Ihre Wahl, ich glaube, Sie ein 1 in einem solchen Fall erhalten wird, während die verschachtelten for-Schleifen Option von Herrn Fooz geben Sie eine 0.

• Die relative Geschwindigkeit dieser verschiedenen Optionen wahrscheinlich von der Größe variieren wird A und die Zahl der Nicht-Nullen Sie es erwarten haben.

Answer 2

Fast ist es, was Sie kümmern sollte, die nicht unbedingt voll Vektorisierung. Neuere Versionen von Matlab sind viel schlaue Handhabung Schleifen effizient. Wenn es etwas auszudrücken, eine kompakte vektorisiert Art und Weise ist, ist es in der Regel schneller, aber Schleifen sollten nicht (immer) zu befürchten, wie sie verwendet werden.

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

Auf R2008a, Windows x64, nimmt die cumsum Version 0.9 Sekunden. Die Schleife und finden Version dauert 0,02 Sekunden. Die Doppel-Loop-Version dauert nur 0,001 Sekunden.

EDIT: Welches ist am schnellsten, hängt von den tatsächlichen Daten. Der Doppel-Loop dauert 0,05 Sekunden, wenn Sie die ,5-,999 ändern (weil es länger dauert die Pause zu schlagen, im Durchschnitt). cumsum und die Schleife & finden Implementierung haben einheitlichere Geschwindigkeiten.

EDIT 2: gnovice der flipud Lösung ist clever. Leider auf meiner Testmaschine dauert es 0,1 Sekunden, es ist so viel schneller als cumsum, aber langsamer als die geschleift Versionen.