高速でベクトル化された方法でバイナリマトリックスを最後の非ゼロインデックスのベクトルに変換する
-
06-07-2019 - |
質問
MATLABで、要素が0または1の行列Aがあると仮定します。
より速く、ベクトル化された方法で各列の最後の非ゼロ要素のインデックスのベクトルを取得するにはどうすればよいですか?
できること
[B、I] = max(cumsum(A));
そして I
を使用しますが、もっと速い方法はありますか? (cumsumは0と1を合計しても少し時間がかかると仮定しています)。
編集:必要以上にベクトル化したと思います。Mr。Foozのループは素晴らしいですが、MATLABの各ループは me のコストが高いようですたとえ高速であってもデバッグ時間。
解決
Mr Fooz 、新しいバージョンのMATLABではforループが非常に高速になりました。ただし、コンパクトなベクトル化コードが本当に必要な場合は、これを試してみることをお勧めします。
[B,I] = max(flipud(A));
I = size(A,1)-I+1;
これはCUMSUMベースの回答よりも高速ですが、Mr Foozのループオプションほど高速ではありません。
考慮すべき2つの追加事項:
-
何も含まれていない列に対して、どのような結果を得たいですか?上記のオプションを使用すると、このような場合に size(A、1)(つまり、 A の行数)のインデックスを取得できると思います。あなたのオプションについては、そのような場合には1が得られると思いますが、Mr Foozからのネストされたfor-loopsオプションは0を与えます。
-
これらのさまざまなオプションの相対速度は、 A のサイズと、予想される非ゼロの数に基づいて異なる可能性があります。
他のヒント
Fastは、完全なベクトル化とは限らず、心配するべきことです。 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のフリップソリューションは賢明です。残念ながら、私のテストマシンでは0.1秒かかります。そのため、cumsumよりはるかに高速ですが、ループバージョンよりも低速です。