Transformer une matrice binaire en un vecteur du dernier index non nul de manière rapide et vectorisée

Question

Supposons que, dans MATLAB, j'ai une matrice, A, dont les éléments sont 0 ou 1.

Comment obtenir un vecteur de l'index du dernier élément non nul de chaque colonne de manière plus rapide et vectorisée?

Je pourrais faire

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

et utilisez I , mais existe-t-il un moyen plus rapide? (Je suppose que cumsum coûterait un peu de temps, même en additionnant les 0 et les 1).

Modifier: J'imagine que je vectorisais plus que nécessaire - la boucle de M. Fooz est excellente, mais chaque boucle de MATLAB semble coûter très cher à moi temps de débogage même s’il est rapide.

Answer 1

Comme le montre M. Fooz , les boucles peuvent être assez rapides maintenant avec les nouvelles versions de MATLAB. Cependant, si vous voulez vraiment avoir du code vectorisé compact, je vous suggère d'essayer ceci:

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

Ceci est plus rapide que votre réponse basée sur CUMSUM, mais pas tout à fait aussi rapide que les options de bouclage de M. Fooz.

Deux autres points à prendre en compte:

• Quels résultats voulez-vous obtenir pour une colonne qui n'en contient pas du tout? Avec l'option ci-dessus que je vous ai donnée, je pense que vous obtiendrez un index de taille (A, 1) (c'est-à-dire le nombre de lignes dans A ) dans un tel cas. Pour votre choix, je pense que vous obtiendrez un 1 dans un tel cas, tandis que l'option imbriquée pour les boucles de M. Fooz vous donnera un 0.

• La vitesse relative de ces différentes options variera probablement en fonction de la taille de A et du nombre de non-zéros que vous attendez.

Answer 2

Rapide est ce qui doit vous inquiéter, pas nécessairement la vectorisation complète. Les versions récentes de Matlab sont beaucoup beaucoup plus intelligentes pour gérer les boucles efficacement. S'il existe un moyen compact d'expression vectorielle, il est généralement plus rapide, mais les boucles ne doivent pas (toujours) être craintes comme avant.

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

Sous R2008a, Windows, x64, la version de Cumsum nécessite 0,9 seconde. La version en boucle et recherche prend 0,02 seconde. La version double boucle ne prend que 0,001 seconde.

MODIFIER: Le plus rapide dépend des données réelles. La double boucle prend 0,05 seconde lorsque vous modifiez le paramètre 0,5 à 0,999 (car la pause prend plus de temps; en moyenne). Cumsum et l’implémentation loop & find ont des vitesses plus cohérentes.

EDIT 2: La solution flipud de gnovice est intelligente. Malheureusement, sur ma machine de test, cela prend 0,1 seconde. Il est donc beaucoup plus rapide que Cumsum, mais plus lent que les versions en boucle.