Wektoryzacja Matlaba - niezerowe indeksy wierszy macierzy do komórki

Pracuję z Matlabem.

Mam binarną macierz kwadratową. Dla każdego wiersza znajduje się jeden lub więcej wpisów 1. Chcę przejrzeć każdy wiersz tej macierzy i zwrócić indeks tych 1s i zapisać je we wpisie komórki.

Zastanawiałem się, czy można to zrobić bez zapętlania wszystkich wierszy tej macierzy, ponieważ w Matlabie pętla jest naprawdę wolna.

Na przykład moja matryca

M = 0 1 0
    1 0 1
    1 1 1 

W końcu chcę coś takiego

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

Podobnie Ajak komórka.

Czy istnieje sposób na osiągnięcie tego celu bez użycia pętli for, w celu szybszego obliczenia wyniku?

Na dole tej odpowiedzi znajduje się kod porównawczy, ponieważ wyjaśniłeś, że interesuje Cię wydajność, a nie arbitralne unikanie forpętli.

W rzeczywistości myślę, że forpętle są prawdopodobnie najbardziej wydajną opcją tutaj. Od czasu wprowadzenia „nowego” (2015b) silnika JIT pętle ( źródłowe ) fornie są z natury wolne - w rzeczywistości są zoptymalizowane wewnętrznie.

Można zobaczyć od benchmarku, że mat2cellopcja oferowana przez ThomasIsCoding tutaj jest bardzo powolny ...

Jeśli pozbywamy się tej linii, aby skala była wyraźniejsza, wówczas moja splitapplymetoda jest dość powolna, opcja akumulacji tablicy obchardon jest nieco lepsza, ale najszybsze (i porównywalne) opcje albo używają arrayfun(jak sugeruje Thomas), albo forpętli. Pamiętaj, że w większości przypadków arrayfunjest to forukryta pętla, więc nie jest to zaskakujący remis!

Polecam użycie forpętli dla zwiększenia czytelności kodu i najlepszej wydajności.

Edytuj :

Jeśli założymy, że zapętlenie jest najszybszym podejściem, możemy dokonać optymalizacji wokół findpolecenia.

konkretnie

• Zrób Mlogiczne. Jak pokazuje poniższy wykres, może to być szybsze dla stosunkowo małych M, ale wolniejsze z kompromisem konwersji typu dla dużych M.

• Użyj logiki, Maby zindeksować tablicę 1:size(M,2)zamiast używać find. Pozwala to uniknąć najwolniejszej części pętli ( findpolecenia) i przewyższa narzut związany z konwersją typów, co czyni ją najszybszą opcją.

Oto moja rekomendacja dla najlepszej wydajności:

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

Dodałem to do poniższego testu porównawczego, oto porównanie podejść w stylu pętli:

Kod porównawczy:

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

Możesz spróbować arrayfunjak poniżej, które przesuwają się przez rzędyM

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

}

lub (wolniejsze podejście do 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

}

Edycja : Dodałem test porównawczy, wyniki pokazują, że pętla for jest bardziej wydajna niżaccumarray .

Możesz użyć findi accumarray:

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

Macierz jest transponowana ( A'), ponieważ findgrupuje według kolumn.

Przykład:

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)

Wynik:

C{1} = 
     1     4

C{2} = 
     2

C{3} =
     3     4

C{4} = 
     1     3     5

Reper:

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

Wynik:

accumarray:
Elapsed time is 2.407773 seconds.

For loop:
Elapsed time is 1.671387 seconds.

Pętla for jest bardziej wydajna niż accumarray...

Za pomocą accumarray :

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

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

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

Możesz użyć strfind :

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