이진 행렬을 빠른 벡터 화 방식으로 마지막 0이 아닌 색인의 벡터로 전환

Question

Matlab에서는 요소가 0 또는 1 인 행렬 인 A가 있다고 가정합니다.

각 열의 마지막 0이 아닌 요소의 인덱스 벡터를 더 빠르고 벡터화 된 방식으로 얻으려면 어떻게해야합니까?

난 할 수 있습니다

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

그리고 사용 I,하지만 더 빠른 방법이 있습니까? (나는 Cumsum이 0과 1을 합산하는 데 약간의 시간이 걸릴 것이라고 가정합니다).

편집하다: 나는 필요한 것보다 훨씬 더 벡터화 된 것 같아요 - Fooz의 루프 씨는 훌륭하지만 Matlab의 각 루프는 비용이 많이 드는 것 같습니다. 나 빠르더라도 디버깅 시간이 많이 있습니다.

Answer 1

다음과 같이 표시됩니다 씨 Fooz, 최신 버전의 MATLAB에서는 루프가 매우 빠를 수 있습니다. 그러나 실제로 컴팩트 한 벡터화 코드를 원한다면 이것을 시도하는 것이 좋습니다.

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

이것은 Cumsum 기반 답변보다 빠르지 만 Fooz 씨의 루핑 옵션만큼 빠르지는 않습니다.

고려해야 할 두 가지 추가 사항 :

• 아무도없는 칼럼에 대해 어떤 결과를 얻고 싶습니까? 내가 준 위의 옵션으로, 나는 당신이 크기 (a, 1) (즉, 행의 수 ㅏ) 몇몇 경우. 귀하의 선택을 위해, 나는 당신이 그러한 경우에 1을 얻을 것이라고 믿는 반면, Fooz 씨의 중첩 루프 옵션은 당신에게 0을 줄 것입니다.

• 이러한 다른 옵션의 상대적인 속도는 크기에 따라 다를 수 있습니다. ㅏ 그리고 당신이 기대할 것으로 예상되는 비제르의 수.

Answer 2

금식은 반드시 완전한 벡터화 일 필요는 없지만 걱정해야 할 것입니다. 최근 버전의 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.5에서 0.999를 변경할 때 0.05 초가 걸립니다 (평균적으로 휴식을 치는 데 시간이 더 걸리기 때문에). Cumsum과 Loop & Find 구현은 더 일관된 속도를 가지고 있습니다.

편집 2 : Gnovice의 Flipud 솔루션은 영리합니다. 불행히도, 테스트 머신에서는 0.1 초가 걸리므로 Cumsum보다 훨씬 빠르지 만 루프 버전보다 느립니다.