如何快捷输出（不用循环）每行的第一个不为零的元素

pacoyang

比如说
a=[0,2,3;
     6,0,8;
     0,0,6];

每行都提取第一个不为零的数，输出的数据是b=[2;6;6];

如何不循环，来实现！！

winner245

如果矩阵尺寸很小，直接用 for 循环 + find 实现即可
如果矩阵尺寸很大，可以用下面的办法

a = randi([0,10],5000,2000);
[~,c,v] = find(a');
v(diff([0;c])~=0)

rocwoods

这样的问题是典型的C/C++比MATLAB擅长的问题,也就是说硬向量化反而不是最优的方法，我的书中有类似的讨论。 具体到本问题，如果硬要不出现循环，全部MATLAB向量化的话，必然导致所有元素都会被判断一下，实际中可能会有较多的计算浪费，譬如第一列刚好是全非0的情形。在MATLAB中可取的办法是按行循环+find，由于是按行，每次处理一行数据，overhead的相对开销还是比较少的，又因为是判断非零数，所以可以把a中每一行直接放入find()中，注意千万不要再用~=0来判断，这样会导致a中每一行所有元素都跟0比较。
所以个人觉得尺寸大时候更适合用刘兄说的第一种情况：

1. 
   
2. a = randi([0,10],5000,2000);
   
3. tic;
   
4. nz1 = zeros(5000,1);
   
5. for k = 1:5000
   
6. [~,~,nz1(k)] = find(a(k,:),1,'first');
   
7. end
   
8. toc
   
9. tic;
   
10. [~,c,v] = find(a');
    
11. nz2 = v(diff([0;c])~=0);
    
12. toc;
    
13. isequal(nz1,nz2)
    
14. 
    

复制代码

winner245

rocwoods 发表于 2014-9-22 11:43
这样的问题是典型的C/C++比MATLAB擅长的问题,也就是说硬向量化反而不是最优的方法，我的书中有类似的讨论。 ...

还是吴兄分析得细致！又一次受教了。
的确，按行for循环搭载find 'first' 方法，效率比生硬向量化要高

nwcwww

这题用向量化也有向量化的优势，如果用循环写的话还得分情况讨论：在极端情况下可能整行都是0，此时find返回为空，直接赋值就会出问题，需要作为特例处理。而向量化的方法由于mathworks已经考虑过这些事情，可以省点心思，函数开销也算值回票价吧。

另外提供一种向量化解答，用max代替find似乎也可行，效率也不错：

1. a = randi([0,10],5000,2000);
   
2. tic;
   
3. nz1 = zeros(5000,1);
   
4. for k = 1:5000
   
5. [~,~,nz1(k)] = find(a(k,:),1,'first');
   
6. end
   
7. toc;
   
8. tic;
   
9. [~,c,v] = find(a');
   
10. nz2 = v(diff([0;c])~=0);
    
11. toc;
    
12. tic;
    
13. [~, tmpInd] = max(logical(a'));
    
14. nz3 = a((sub2ind([5000, 2000], 1:5000, tmpInd))');
    
15. toc;
    
16. isequal(nz1, nz2, nz3)

复制代码

在有全零行时nz3和nz2这两个向量化所得的解会有细微差别:

1. a = [1 0 2; 0 3 4; 0 0 0; 5 6 0; 7 8 9];
   
2. [~,c,v] = find(a');
   
3. nz2 = v(diff([0;c])~=0)
   
4. 
   
5. [~, tmpInd] = max(logical(a'));
   
6. nz3 = a((sub2ind([5 3], 1:5, tmpInd))')

复制代码

这里nz2为4*1, nz3为5*1。在前者中a的全零行没有贡献，在后这种a的全零行对应结果0。

1. nz2 =
   
2. 
   
3.      1
   
4.      3
   
5.      5
   
6.      7
   
7. 
   
8. 
   
9. nz3 =
   
10. 
    
11.      1
    
12.      3
    
13.      0
    
14.      5
    
15.      7

复制代码

另：如果考虑到nan的情况，logical()要用~=0 & ~isnan代替。

ljelly

rocwoods 发表于 2014-9-22 11:43
这样的问题是典型的C/C++比MATLAB擅长的问题,也就是说硬向量化反而不是最优的方法，我的书中有类似的讨论。 ...

的确如吴兄所言，我把规模加大后，你的方法效率更高，更适合大数据
看两位大鹏斗法，十分精彩，受教了！

1. 
   
2. <p>a = randi([0,10],8000,5000);
   
3. tic;
   
4. nz1 = zeros(8000,1);
   
5. for k = 1:8000
   
6. [~,~,nz1(k)] = find(a(k,:),1,'first');
   
7. end
   
8. toc
   
9. tic;
   
10. [~,c,v] = find(a');
    
11. nz2 = v(diff([0;c])~=0);
    
12. toc;
    
13. isequal(nz1,nz2)
    
14. 时间已过 1.718986 秒。
    
15. 时间已过 2.318695 秒。 </p>

复制代码

rocwoods

nwcwww 发表于 2014-9-24 01:41
这题用向量化也有向量化的优势，如果用循环写的话还得分情况讨论：在极端情况下可能整行都是0，此时find返 ...

赞！nwc老兄巧妙利用max返回第一个最大值这个特性，用向量化解决，效率最好！其实像这种参差不齐的问题，难以有统一的向量化方法，只能有需要时灵活掌握。

rocwoods

终于找到比较通用的向量化方法了，还是利用强大的bsxfun函数。

foo函数如下

1. 
   
2. function C = foo(A,~)
   
3. C = false(size(A,1),1);
   
4. ind = find(A,1,'first');
   
5. C(ind) = true;
   

复制代码

效率比较如下：

1. 
   
2. clear;
   
3. a = randi([0,10],8000,5000);
   
4. tic;
   
5. nz1 = zeros(8000,1);
   
6. for k = 1:8000
   
7. [~,~,nz1(k)] = find(a(k,:),1,'first');
   
8. end
   
9. toc;
   
10. tic;
    
11. [~,c,v] = find(a');
    
12. nz2 = v(diff([0;c])~=0);
    
13. toc;
    
14. tic;
    
15. [~, tmpInd] = max(logical(a'));
    
16. nz3 = a((sub2ind([8000, 5000], 1:8000, tmpInd))');
    
17. toc;
    
18. tic;a = a';ind = bsxfun(@foo,a,zeros(1,size(a,2)));
    
19. nz4 = a(ind);
    
20. toc;
    
21. isequal(nz1, nz2, nz3,nz4)
    
22. 时间已过 0.867728 秒。
    
23. 时间已过 1.196446 秒。
    
24. 时间已过 0.390155 秒。
    
25. 时间已过 0.408648 秒。
    
26. ans =
    
27.      1
    

复制代码

遇到类似的问题，修改bsxfun中的foo函数就行。

rocwoods

又改进了下，利用稀疏矩阵可以减少存储又直接返回所要的值,效率很不错：

1. 
   
2. function Find1stNzero
   
3. nrows = 8000;
   
4. ncols = 5000;
   
5. a = randi([0,10],nrows,ncols);
   
6. 
   
7. %method3
   
8. tic;
   
9. [~, tmpInd] = max(logical(a'));
   
10. nz3 = a((sub2ind([nrows, ncols], 1:nrows, tmpInd))');
    
11. toc;
    
12. %method4
    
13. tic;
    
14. NZ = bsxfun(@foo,a',sparse(1,nrows));
    
15. nz4 = NZ(end,:)';
    
16. toc
    
17. isequal(nz3,nz4)
    
18. 
    
19.     function C = foo(A,~)
    
20.         [~,~,val] = find(A,1,'first');
    
21.         if isempty(val)
    
22.             val = nan;
    
23.         end
    
24.         C = sparse(ncols,1,val);
    
25.     end
    
26. end
    
27. 
    

复制代码

测试如下：

1. 
   
2. Find1stNzero
   
3. 时间已过 0.447408 秒。
   
4. 时间已过 0.342874 秒。
   
5. ans =
   
6.      1
   
7. 
   

复制代码

方法四主要耗时在 “a'”上了，如果一开始组织好数据，找每一列的第一个非零值，那么方法四仅耗时0.073秒。

rocwoods

兜了一圈，大家都被楼主绕进去了，楼主说不用循环还快速，基本无解。这个问题最快的就是两重循环。

1. 
   
2. nrows = 8000;
   
3. ncols = 5000;
   
4. a = randi([0,10],nrows,ncols);
   
5. tic
   
6. nz = zeros(nrows,1);
   
7. for ii = 1:nrows
   
8.     for jj = 1:ncols
   
9.         if a(ii,jj)~=0
   
10.             nz(ii) = a(ii,jj);
    
11.             break
    
12.         end        
    
13.     end
    
14. end
    
15. toc
    
16. 
    
17. 时间已过 0.000839 秒。
    

复制代码

比上面所有的方法都快100倍以上！
如果用C/C++的两重循环来写，估计得再快几倍！所以，大家别费尽心思向量化了吧，典型的大炮打蚊子问题,所以这个问题是很好的硬向量化适得其反的很好的例子！其实MATLAB的循环不慢，就是变量访问和赋值效率比C/C++低一些，慢就慢在函数调用开销上。这个问题就是简单的判断和赋值问题，涉及不到复杂的函数调用，所以MATLAB的循环一点儿也不慢。任何向量化都无可避免把问题复杂化。引入大量不必要的计算和内存访问，严重拖累速度。
我之前一个ppt里粗略说了下MATLAB中单次各类型函数调用开销，以及变量访问的时间开销和浮点计算量的大致关系，就是希望大家在面对一个问题时，算之前就可以估计复杂度，是向量化好，还是直接循环好。
其实讨论讨论挺好，起码有一些方法在特定场合还是很有用很高效的。

winner245

nwcwww 发表于 2014-9-24 01:41
这题用向量化也有向量化的优势，如果用循环写的话还得分情况讨论：在极端情况下可能整行都是0，此时find返 ...

nwcwww 版主这个方法真巧妙！将 find 问题转化为了 max 问题，效率大大提升。

考虑到 a 的尺寸很大时，转置也会耗时，所以避免 a' 可进一步提高效率

1. a = randi([0,10],5000,2000);
   
2. tic;
   
3. nz1 = zeros(5000,1);
   
4. for k = 1:5000
   
5. [~,~,nz1(k)] = find(a(k,:),1,'first');
   
6. end
   
7. toc;
   
8. tic;
   
9. [~,c,v] = find(a');
   
10. nz2 = v(diff([0;c])~=0);
    
11. toc;
    
12. tic;
    
13. [~, tmpInd] = max(logical(a'));
    
14. nz3 = a((sub2ind([5000, 2000], 1:5000, tmpInd))');
    
15. toc;
    
16. tic;
    
17. [~, tmpInd] = max(logical(a),[],2);% 避免转置的方法
    
18. nz4 = a((tmpInd-1)*size(a,1)+[1:size(a,1)].');
    
19. toc;
    
20. tic
    
21. a';% 单纯的转置
    
22. toc
    
23. isequal(nz1, nz2, nz3, nz4)

复制代码

Elapsed time is 0.155723 seconds.
Elapsed time is 0.221446 seconds.
Elapsed time is 0.099996 seconds.
Elapsed time is 0.043580 seconds.
Elapsed time is 0.042271 seconds.

ans =

     1
可见避免转置后，代码效率提高1倍，而且整个代码效率跟单纯的转置相当

winner245

rocwoods 发表于 2014-9-24 14:57
兜了一圈，大家都被楼主绕进去了，楼主说不用循环还快速，基本无解。这个问题最快的就是两重循环。比上面所 ...

简单的二重循环和条件判断效率如此之高！诚如吴兄所言，这个算法就是最简单的条件判断，几乎没有任何函数调用开销（当算法很简单，数据达到一定规模时，即使是转置这一类算法也会拖累效率），再一次受教！引入JIT加速后的循环还真不赖！

qibbxxt

效率上来讲，如果数据量大的话，二层循环访问的数据量最小，因此效率最高。
看大家讨论的如何热闹，我也用accumarray来写一个，不考虑效率，只为向量化

1. [x{1:2}] = find(a);
   
2. a(1&sparse(1:size(a,1),accumarray(x{:},[],@min,1),1));

复制代码