9

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

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

我可以做

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

并使用I，但有更快的方法吗？（我假设 cumsum 即使将 0 和 1 相加也会花费一些时间）。

编辑：我想我矢量化的速度甚至超过了我需要的速度 - Fooz 先生的循环很棒，但 MATLAB 中的每个循环似乎都花费了我很多调试时间，即使它很快。

4

2 回答 2

11

快速是您应该担心的，不一定是全矢量化。最新版本的 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 快得多，但比循环版本慢。

于 2009-05-06T21:52:53.067 回答
7

正如Fooz 先生所展示的，对于新版本的 MATLAB，for 循环现在可以非常快。但是，如果您真的想要紧凑的矢量化代码，我建议您尝试以下操作：

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

这比您基于 CUMSUM 的答案要快，但仍不如 Fooz 先生的循环选项快。

需要考虑的另外两件事：

  • 对于完全没有任何列的列，您希望得到什么结果？通过上面我给你的选项，我相信在这种情况下你会得到一个size(A,1)的索引（即A中的行数）。对于您的选择，我相信在这种情况下您会得到 1，而 Fooz 先生的嵌套循环选项会给您 0。

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

于 2009-05-06T22:17:16.923 回答