Matlab 向量化 - none- 零矩阵行索引到单元格

Question

我正在使用 Matlab。

我有一个二元方阵。对于每一行，有一个或多个 1 的条目。我想遍历该矩阵的每一行和 return 这些 1 的索引并将它们存储在单元格的条目中。

我想知道是否有一种方法可以在不遍历该矩阵的所有行的情况下执行此操作，因为 for 循环在 Matlab 中真的很慢。

比如我的矩阵

M = 0 1 0
    1 0 1
    1 1 1

然后最终，我想要类似

的东西

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

所以A是一个单元格。

有没有一种不用for循环就能达到这个目的，并且计算结果更快的方法？

Answer 1

您可以像下面那样尝试 arrayfun，扫过 M

行

A = arrayfun(@(r) find(M(r,:)),1:size(M,1),'UniformOutput',false)

A =
{
  [1,1] =  2
  [1,2] =

     1   3

  [1,3] =

     1   2   3

}

或（mat2cell 的较慢方法）

[i,j] = find(M.');
A = mat2cell(i,arrayfun(@(r) sum(j==r),min(j):max(j)))

A =
{
  [1,1] =  2
  [2,1] =

     1
     3

  [3,1] =

     1
     2
     3

}

Answer 2

使用accumarray:

M = [0 1 0
     1 0 1
     1 1 1];

[val,ind] = find(M.');

A = accumarray(ind,val,[],@(x) {x});

Answer 3

Edit: 我加了一个benchmark，结果显示a for loop比accumarray更有效率。

您可以使用find和accumarray:

[c, r] = find(A');
C = accumarray(r, c, [], @(v) {v'});

矩阵被转置 (A') 因为 find 按列分组。

示例：

A = [1 0 0 1 0
     0 1 0 0 0
     0 0 1 1 0
     1 0 1 0 1];

%  Find nonzero rows and colums
[c, r] = find(A');

%  Group row indices for each columns
C = accumarray(r, c, [], @(v) {v'});

% Display cell array contents
celldisp(C)

输出：

C{1} = 
     1     4

C{2} = 
     2

C{3} =
     3     4

C{4} = 
     1     3     5

基准：

m = 10000;
n = 10000;

A = randi([0 1], m,n);

disp('accumarray:')
tic
[c, r] = find(A');
C = accumarray(r, c, [], @(v) {v'});
toc
disp(' ')

disp('For loop:')
tic
C = cell([size(A,1) 1]);
for i = 1:size(A,1)
    C{i} = find(A(i,:));
end
toc

结果：

accumarray:
Elapsed time is 2.407773 seconds.

For loop:
Elapsed time is 1.671387 seconds.

for 循环比 accumarray...

更有效

Answer 4

此答案的底部是一些基准测试代码，因为您阐明了您对性能感兴趣而不是武断地避免 for 循环。

事实上，我认为 for 循环可能是此处性能最高的选项。由于引入了 "new" (2015b) JIT 引擎 (source) for 循环本身并不慢 - 事实上它们在内部进行了优化。

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

如果我们去掉那条线以使刻度更清晰，那么我的 splitapply 方法相当慢，obchardon 的好一点，但最快（和可比较）的选项是使用 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

Answer 5

您可以使用 strfind :

A = strfind(cellstr(char(M)), char(1));

Matlab 向量化 - none- 零矩阵行索引到单元格

Matlab Vectorization - none-zero matrix row indices to cell

matlab

vectorization