将二进制矩阵以快速矢量化方式转换为最后一个非零索引的向量

Question

假设在MATLAB中,我有一个矩阵A,其元素为0或1.

如何以更快的矢量化方式获取每列的最后一个非零元素的索引向量？

我可以

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

和使用I,但有更快的方法吗？(我假设cumsum会花费一点时间甚至加0和1).

编辑:我想我矢量甚至比我需要快速的更多-福兹先生"循环是伟大的,但在MATLAB每个循环似乎花费了我很多的调试即使是快的时间.

Answer 1

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和循环和查找实现具有更一致的速度.

编辑2: gnovice的flipud解决方案很聪明.不幸的是,在我的测试机器上需要0.1秒,所以它比cumsum快得多,但比循环版本慢.

Answer 2

正如Fooz先生所示,对于新版本的MATLAB,for循环现在可以非常快.但是,如果你真的想拥有紧凑的矢量化代码,我建议你试试这个:

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

这比基于CUMSUM的答案要快,但仍然不如Fooz先生的循环选项快.

还需要考虑两件事:

• 对于一个根本没有内容的列,您希望获得什么结果？根据我给你的上述选项,我相信在这种情况下你会得到一个大小(A,1)的索引(即A中的行数).对于你的选择,我相信你会在这种情况下获得1,而来自Fooz先生的嵌套for循环选项将给你一个0.

• 这些不同选项的相对速度可能会根据A的大小和您期望它的非零数量而变化.