Matlab Векторизация - ненулевые индексы строк матрицы в ячейке

Question

Я работаю с Matlab.

У меня есть двоичная квадратная матрица. Для каждой строки есть одна или несколько записей 1. Я хочу go пройти через каждую строку этой матрицы и вернуть индекс этих 1-х единиц и сохранить их в записи ячейки.

Я был Интересно, есть ли способ сделать это без зацикливания на всех строках этой матрицы, так как l oop в Matlab действительно медленный.

Например, моя матрица

M = 0 1 0
    1 0 1
    1 1 1 

Тогда, в конце концов, я хочу что-то вроде

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

Так что A - это клетка.

Есть ли способ достичь этой цели без использования для l oop с целью более быстрого вычисления результата?

Answer 1

В нижней части этого ответа приведен код тестирования, поскольку вы пояснили, что заинтересованы в производительности, а не в том, чтобы произвольно избегать циклов for.

На самом деле, я думаю, что циклы for, вероятно, самый производительный вариант здесь. Поскольку был введен «новый» (2015b) механизм JIT ( source ), циклы for не являются медленными по своей природе - фактически они оптимизируются внутри.

Из теста можно видеть, что опция mat2cell, предлагаемая ThomasIsCoding здесь , очень медленная ...

Если мы избавимся от этой строки, сделайте шкалу более понятной, тогда мой splitapply метод будет довольно медленным, опция accmarray от obchardon немного лучше, но самые быстрые (и сопоставимые) варианты используют либо arrayfun (что также предложено Томасом) или for l oop. Обратите внимание, что arrayfun в основном скрыт для for l oop для большинства случаев использования, так что это не удивительно t ie!

Я бы порекомендовал вам использовать for l oop для повышения читабельности кода и лучшей производительности.

Редактировать :

Если мы предположим, что цикл является самым быстрым подходом, мы можем сделать некоторые оптимизации вокруг команды find.

В частности

• Сделайте M логичным. Как показано на графике ниже, это может быть быстрее для относительно небольших M, но медленнее с компромиссом преобразования типов для больших M.

• Используйте логический M индексировать массив 1:size(M,2) вместо использования find. Это позволяет избежать самой медленной части l oop (команда 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

Я добавил это в тест ниже, вот сравнение подходов в стиле l oop:

Код бенчмаркинга:

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 2

Вы можете использовать strfind :

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

Answer 3

Использование accumarray :

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

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

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

Answer 4

Редактировать : я добавил тест, результаты показывают, что a для l oop более эффективно, чем 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.

A для l oop эффективнее accumarray ...

Answer 5

Вы можете попробовать 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

}