Vetorização Matlab - índices de linha da matriz zero na célula

10

Estou trabalhando com o Matlab.

Eu tenho uma matriz quadrada binária. Para cada linha, há uma ou mais entradas de 1. Quero passar por cada linha dessa matriz e retornar o índice desses 1s e armazená-los na entrada de uma célula.

Eu queria saber se existe uma maneira de fazer isso sem fazer loop em todas as linhas desta matriz, pois o loop for é realmente lento no Matlab.

Por exemplo, minha matriz

M = 0 1 0
    1 0 1
    1 1 1 

Então, eventualmente, eu quero algo como

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

Então Aé uma célula.

Existe uma maneira de atingir esse objetivo sem usar o loop for, com o objetivo de calcular o resultado mais rapidamente?

ftxx
fonte
Deseja que o resultado seja rápido ou deseja evitar forloops? Para esse problema, nas versões modernas do MATLAB, suspeito fortemente que um forloop seja a solução mais rápida. Se você tiver um problema de desempenho, suspeito que esteja procurando o local errado, com base em conselhos desatualizados.
Será
@Quero que os resultados sejam rápidos. Minha matriz é muito grande. O tempo de execução é de cerca de 30s no meu computador usando o loop for. Quero saber se existem algumas operações de vetorização inteligentes ou, mapReduce, etc. que podem aumentar a velocidade.
ftxx 10/02
11
Eu suspeito que você não pode. A vetorização funciona em vetores e matrizes descritos com precisão, mas seu resultado permite vetores de diferentes comprimentos. Assim, suponho que você sempre terá algum loop explícito ou algum loop disfarçado cellfun.
HansHirse
@ftxx quão grande? E quantos 1s em uma fileira típica? Eu não esperaria que um findloop levasse algo próximo dos 30s para algo pequeno o suficiente para caber na memória física.
Será
@ftxx Por favor, veja minha resposta atualizada, editei desde que foi aceita com uma pequena melhoria no desempenho
Wolfie

Respostas:

11

Na parte inferior desta resposta está um código de benchmarking, pois você esclareceu que está interessado em desempenho, em vez de evitar arbitrariamente forloops.

Na verdade, acho que os forloops são provavelmente a opção de melhor desempenho aqui. Desde que o "novo" (2015b) mecanismo JIT foi introduzido ( fonte ), os forloops não são inerentemente lentos - na verdade, eles são otimizados internamente.

Você pode ver no benchmark que a mat2cellopção oferecida por ThomasIsCoding aqui é muito lenta ...

Comparação 1

Se nos livrarmos dessa linha para tornar a escala mais clara, meu splitapplymétodo é bastante lento, a opção accumarray do obchardon é um pouco melhor, mas as opções mais rápidas (e comparáveis) estão usando arrayfun(como também sugerido por Thomas) ou um forloop. Observe que arrayfuné basicamente um forloop disfarçado para a maioria dos casos de uso, portanto, este não é um empate surpreendente!

Comparação 2

Eu recomendo que você use um forloop para aumentar a legibilidade do código e o melhor desempenho.

Editar :

Se assumirmos que o loop é a abordagem mais rápida, podemos fazer algumas otimizações em torno do findcomando.

Especificamente

  • Faça Mlógica. Como mostra o gráfico abaixo, isso pode ser mais rápido para relativamente pequeno M, mas mais lento com a troca de conversão de tipo para grande M.

  • Use um lógico Mpara indexar uma matriz em 1:size(M,2)vez de usar find. Isso evita a parte mais lenta do loop (o findcomando) e supera a sobrecarga de conversão de tipo, tornando-a a opção mais rápida.

Aqui está a minha recomendação para o melhor desempenho:

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

Adicionei isso à referência abaixo, eis a comparação de abordagens no estilo de loop:

Comparação 3

Código de benchmarking:

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
Wolfie
fonte
11
Já vi e votou. :-) Ainda esperando por Luis; ele com certeza tem alguma magia negra do MATLAB para isso.
HansHirse
@Hans Haha, sim, embora seu pacote habitual de truques (expansão implícita, indexação inteligente, ...) normalmente mantenha as coisas como matrizes, o gargalo aqui está resumido nas células
Wolfie
11
Observe que esses horários são fortemente dependentes da esparsidade de M. Se, por exemplo, apenas 5% dos elementos forem preenchidos M = randi([0,20],N) == 20;, o forloop será de longe o mais lento e o seu arrayfunmétodo vencerá.
Será
@HansHirse :-) Minha abordagem seria accumarraysem ind2sub, mas é mais lenta que o forloop
Luis Mendo
2

Você pode tentar arrayfuncomo abaixo, que varre as linhas deM

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

}

ou (uma abordagem mais lenta por 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

}
ThomasIsCoding
fonte
11
Embora arrayfunseja basicamente um disfarce, isso pode falhar nas duas frentes de 1) evitar loops e 2) ser rápido, conforme esperado pelo OP
Wolfie
2

Edit : Eu adicionei uma referência, os resultados mostram que um loop for é mais eficiente do queaccumarray .


Você pode usar finde accumarray:

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

A matriz é transposta ( A') porque findagrupa por coluna.

Exemplo:

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)

Resultado:

C{1} = 
     1     4

C{2} = 
     2

C{3} =
     3     4

C{4} = 
     1     3     5

Referência:

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

Resultado:

accumarray:
Elapsed time is 2.407773 seconds.

For loop:
Elapsed time is 1.671387 seconds.

Um loop for é mais eficiente que accumarray...

Eliahu Aaron
fonte
Esse é praticamente o método já proposto por obchardon , não?
Wolfie
Sim, fiquei um pouco lento, vi a resposta dele depois que publiquei a minha.
Eliahu Aaron 10/02
2

Usando accumarray :

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

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

A = accumarray(ind,val,[],@(x) {x});
obchardon
fonte
11
O tempo de execução em Octave e MATLAB Online é cerca de 2x de um loop for simples como: MM{I} = find(M(I, :)).
HansHirse
2
@Hans, você pode querer ver a minha resposta
Wolfie
Sim, como o tamanho de cada célula não é o mesmo, esse problema não pode ser totalmente vetorizado (ou há um truque que eu não vi). É apenas uma solução que oculta o loop for.
obchardon 10/02
Não há necessidade de ind2sub:[ii, jj] = find(M); accumarray(ii, jj, [], @(x){x})
Luis Mendo
@LuisMendo obrigado, editei minha resposta.
obchardon 10/02
2

Você pode usar strfind :

A = strfind(cellstr(char(M)), char(1));
rahnema1
fonte
Eu (preguiçosamente) nem procurei nos documentos, mas isso seria mais rápido usando stringtipos reais do que caracteres? Existem muitas otimizações para as strings, daí a razão pela qual elas existem ...
Wolfie
@ Wolfie Acho que matrizes numéricas são mais semelhantes a matrizes de caracteres do que cadeias de caracteres, portanto, a conversão da matriz numérica em matriz de caracteres deve ser mais direta do que a conversão em string.
rahnema1 10/02