Matlab向量化-单元格的非零矩阵行索引

Question

我正在与Matlab合作。

我有一个二进制方阵。对于每一行，都有一个或多个1的条目。我想遍历此矩阵的每一行，并返回这些1的索引，并将其存储在单元格的条目中。

我想知道是否有一种方法可以不循环遍历该矩阵的所有行，因为在Matlab中循环确实很慢。

例如我的矩阵

M = 0 1 0
    1 0 1
    1 1 1 

然后最终，我想要类似

A = [2]
    [1,3]
    [1,2,3]

因此A是一个单元格。

是否有一种无需使用for循环即可达到此目标的方法，目的是更快地计算结果？

Answer 1

该答案的底部是一些基准测试代码，因为您已表明您对性能感兴趣，而不是任意避免for循环。

实际上，我认为for循环可能是此处性能最高的选项。自从引入了“new”(2015b)JIT引擎(source)以来，for循环并不是天生就很慢-实际上，它们是在内部进行了优化。

您可以从基准测试中看到，ThomasIsCoding here提供的mat2cell选项非常慢...



如果我们摆脱那条线以使刻度更清晰，那么我的splitapply方法会相当慢，obchardon的accumarray option会好一些，但是最快(且可比)的选项是使用arrayfun(也由Thomas提出)或for环形。请注意，对于大多数用例，arrayfun基本上是伪装的for循环，因此这并不奇怪!



，我建议您使用for循环以提高代码的可读性和最佳性能。

编辑:

如果我们假设循环是最快的方法，则可以围绕find命令进行一些优化。

具体来说

使M符合逻辑。如下图所示，对于相对较小的M来说，这可能会更快，但是对于较大的M而言，在类型转换的权衡下它会变慢。

使用逻辑M索引数组1:size(M,2)而不是使用find。这避免了循环中最慢的部分(find命令)，并且超过了类型转换的开销，从而使其成为最快的选择。

这是我推荐的最佳性能:

function A = f_forlooplogicalindexing( M )
    M = logical(M);
    k = 1:size(M,2);
    N = size(M,1);
    A = cell(N,1);
    for r = 1:N
        A{r} = k(M(r,:));
    end
end

我已将其添加到下面的基准测试中，这是循环样式方法的比较:



基准测试代码:

rng(904); % Gives OP example for randi([0,1],3)
p = 2:12; 
T = NaN( numel(p), 7 );
for ii = p
    N = 2^ii;
    M = randi([0,1],N);

    fprintf( 'N = 2^%.0f = %.0f\n', log2(N), N );

    f1 = @()f_arrayfun( M );
    f2 = @()f_mat2cell( M );
    f3 = @()f_accumarray( M );
    f4 = @()f_splitapply( M );
    f5 = @()f_forloop( M );
    f6 = @()f_forlooplogical( M );
    f7 = @()f_forlooplogicalindexing( M );

    T(ii, 1) = timeit( f1 ); 
    T(ii, 2) = timeit( f2 ); 
    T(ii, 3) = timeit( f3 ); 
    T(ii, 4) = timeit( f4 );  
    T(ii, 5) = timeit( f5 );
    T(ii, 6) = timeit( f6 );
    T(ii, 7) = timeit( f7 );
end

plot( (2.^p).', T(2:end,:) );
legend( {'arrayfun','mat2cell','accumarray','splitapply','for loop',...
         'for loop logical', 'for loop logical + indexing'} );
grid on;
xlabel( 'N, where M = random N*N matrix of 1 or 0' );
ylabel( 'Execution time (s)' );

disp( 'Done' );

function A = f_arrayfun( M )
    A = arrayfun(@(r) find(M(r,:)),1:size(M,1),'UniformOutput',false);
end
function A = f_mat2cell( M )
    [i,j] = find(M.');
    A = mat2cell(i,arrayfun(@(r) sum(j==r),min(j):max(j)));
end
function A = f_accumarray( M )
    [val,ind] = ind2sub(size(M),find(M.'));
    A = accumarray(ind,val,[],@(x) {x});
end
function A = f_splitapply( M )
    [r,c] = find(M);
    A = splitapply( @(x) {x}, c, r );
end
function A = f_forloop( M )
    N = size(M,1);
    A = cell(N,1);
    for r = 1:N
        A{r} = find(M(r,:));
    end
end
function A = f_forlooplogical( M )
    M = logical(M);
    N = size(M,1);
    A = cell(N,1);
    for r = 1:N
        A{r} = find(M(r,:));
    end
end
function A = f_forlooplogicalindexing( M )
    M = logical(M);
    k = 1:size(M,2);
    N = size(M,1);
    A = cell(N,1);
    for r = 1:N
        A{r} = k(M(r,:));
    end
end