Repetir cópias de elementos de matriz: Decodificação de comprimento de execução no MATLAB

Estou tentando inserir vários valores em uma matriz usando uma matriz ‘values’ e uma matriz ‘counter’. Por exemplo, se:

a=[1,3,2,5] b=[2,2,1,3] 

Eu quero a saída de alguma function

 c=somefunction(a,b) 

ser estar

 c=[1,1,3,3,2,5,5,5] 

Onde um (1) ocorre b (1) número de vezes, a (2) ocorre b (2) vezes, etc …

Existe uma function embutida no MATLAB que faz isso? Eu gostaria de evitar o uso de um loop for, se possível. Eu tentei variações de ‘repmat ()’ e ‘kron ()’ sem sucesso.

Isso é basicamente Run-length encoding .

    Declaração do problema

    Nós temos uma matriz de valores, vals e runlengths, runlens :

     vals = [1,3,2,5] runlens = [2,2,1,3] 

    Somos necessários para repetir cada elemento em vals vezes cada elemento correspondente em runlens . Assim, o resultado final seria:

     output = [1,1,3,3,2,5,5,5] 

    Abordagem Prospectiva

    Uma das ferramentas mais rápidas com o MATLAB é o cumsum e é muito útil quando se trata de problemas de vetorização que funcionam em padrões irregulares. No problema declarado, a irregularidade vem com os diferentes elementos em runlens .

    Agora, para explorar o cumsum , precisamos fazer duas coisas aqui: Inicializar uma matriz de zeros e colocar valores “apropriados” em posições “chave” sobre a matriz zeros, de forma que depois que ” cumsum ” for aplicado, cumsum com um arranjo final de vals repetidos de tempos runlens .

    Passos: Vamos numerar os passos acima mencionados para dar à perspectiva prospectiva uma perspectiva mais fácil:

    1) Inicializar zeros array: Qual deve ser o comprimento? Como estamos repetindo tempos de runlens , o comprimento da matriz de zeros deve ser a sum de todos os runlens .

    2) Encontre posições-chave / índices: Agora, essas posições-chave são lugares ao longo da matriz zeros, onde cada elemento de vals começa a se repetir. Assim, para runlens = [2,2,1,3] , as posições chave mapeadas na matriz zeros seriam:

     [X 0 X 0 XX 0 0] % where X's are those key positions. 

    3) Encontre valores apropriados: O prego final a ser marcanvasdo antes de usar o cumsum seria colocar valores “apropriados” nessas posições-chave. Agora, já que estaríamos fazendo cumsum logo depois, se você pensar bem, você precisaria de uma versão differentiated de values com diff , de modo que o cumsum desses retornasse nossos values . Como esses valores diferenciados seriam colocados em um array de zeros em locais separados pelas distâncias de runlens , após o uso do cumsum teríamos cada elemento de vals repetido runlens vezes como a saída final.

    Código da solução

    Aqui está a implementação costurando todas as etapas acima mencionadas –

     % Calculate cumsumed values of runLengths. % We would need this to initialize zeros array and find key positions later on. clens = cumsum(runlens) % Initalize zeros array array = zeros(1,(clens(end))) % Find key positions/indices key_pos = [1 clens(1:end-1)+1] % Find appropriate values app_vals = diff([0 vals]) % Map app_values at key_pos on array array(pos) = app_vals % cumsum array for final output output = cumsum(array) 

    Hack de pré-alocação

    Como pode ser visto, o código listado acima usa a pré-alocação com zeros. Agora, de acordo com este blogue UNDOCUMENTED MATLAB sobre a pré-alocação mais rápida , pode-se conseguir uma pré-alocação muito mais rápida com –

     array(clens(end)) = 0; % instead of array = zeros(1,(clens(end))) 

    Conclusão: Código de Função

    Para finalizar tudo, teríamos um código de function compacto para alcançar essa decodificação de comprimento de execução, como assim –

     function out = rle_cumsum_diff(vals,runlens) clens = cumsum(runlens); idx(clens(end))=0; idx([1 clens(1:end-1)+1]) = diff([0 vals]); out = cumsum(idx); return; 

    avaliação comparativa

    Código de benchmarking

    Listado a seguir está o código de benchmarking para comparar tempos de execução e acelerações para a abordagem cumsum+diff declarada neste post sobre a outra abordagem baseada em MATLAB 2014B cumsum-only no MATLAB 2014B

     datasizes = [reshape(linspace(10,70,4).'*10.^(0:4),1,[]) 10^6 2*10^6]; % fcns = {'rld_cumsum','rld_cumsum_diff'}; % approaches to be benchmarked for k1 = 1:numel(datasizes) n = datasizes(k1); % Create random inputs vals = randi(200,1,n); runs = [5000 randi(200,1,n-1)]; % 5000 acts as an aberration for k2 = 1:numel(fcns) % Time approaches tsec(k2,k1) = timeit(@() feval(fcns{k2}, vals,runs), 1); end end figure, % Plot runtimes loglog(datasizes,tsec(1,:),'-bo'), hold on loglog(datasizes,tsec(2,:),'-k+') set(gca,'xgrid','on'),set(gca,'ygrid','on'), xlabel('Datasize ->'), ylabel('Runtimes (s)') legend(upper(strrep(fcns,'_',' '))),title('Runtime Plot') figure, % Plot speedups semilogx(datasizes,tsec(1,:)./tsec(2,:),'-rx') set(gca,'ygrid','on'), xlabel('Datasize ->') legend('Speedup(x) with cumsum+diff over cumsum-only'),title('Speedup Plot') 

    Código de function associado para rld_cumsum.m :

     function out = rld_cumsum(vals,runlens) index = zeros(1,sum(runlens)); index([1 cumsum(runlens(1:end-1))+1]) = 1; out = vals(cumsum(index)); return; 

    Tempo de Execução e Gráficos de Aceleração

    insira a descrição da imagem aqui

    insira a descrição da imagem aqui

    Conclusões

    A abordagem proposta parece estar nos dando uma aceleração perceptível sobre a abordagem cumsum-only do cumsum-only , que é cerca de 3x !

    Por que essa nova abordagem baseada em cumsum+diff é melhor do que a abordagem anterior cumsum-only ?

    Bem, a essência da razão está na etapa final da abordagem cumsum-only do cumsum-only que precisa mapear os valores “cumsumed” em vals . Na nova abordagem baseada em cumsum+diff , estamos fazendo diff(vals) invés do qual o MATLAB está processando apenas n elementos (onde n é o número de runLengths) em comparação ao mapeamento de sum(runLengths) número de elementos para o cumsum-only abordagem e este número deve ser muitas vezes mais do que n e, portanto, a notável aceleração com esta nova abordagem!

    Referências

    Atualizado para R2015b : repelem agora mais rápido para todos os tamanhos de dados.


    Funções testadas:

    1. Função repelem incorporada do MATLAB que foi adicionada no R2015a
    2. solução cumsum do cumsum ( rld_cumsum )
    3. cumsum + diff da Divakar ( rld_cumsum_diff )
    4. A solução accumarray do accumarray ( knedlsepp5cumsumaccumarray ) deste post
    5. Implementação baseada em loop ingênuo ( naive_jit_test.m ) para testar o compilador just-in-time

    Resultados do test_rld.m no R2015 b :

    repelem tempo

    Lote de tempo antigo usando R2015 um aqui .

    Resultados :

    • repelem é sempre o mais rápido em aproximadamente um fator de 2.
    • rld_cumsum_diff é consistentemente mais rápido que o rld_cumsum .
    • repelem é o mais rápido para tamanhos pequenos de dados (menos de 300 a 500 elementos)
    • rld_cumsum_diff torna-se significativamente mais rápido do que repelem cerca de 5 000 elementos
    • repelem fica mais lento que rld_cumsum algum lugar entre 30 000 e 300 000 elementos
    • rld_cumsum tem aproximadamente o mesmo desempenho que knedlsepp5cumsumaccumarray
    • naive_jit_test.m tem velocidade quase constante e está de acordo com o rld_cumsum e o knedlsepp5cumsumaccumarray para tamanhos menores, um pouco mais rápido para tamanhos grandes

    insira a descrição da imagem aqui

    Lote de taxa antiga usando R2015 aqui .

    Conclusão

    Use repelem abaixo de cerca de 5.000 elementos e a solução cumsum + diff acima .

    Não há nenhuma function interna que conheço, mas aqui está uma solução:

     index = zeros(1,sum(b)); index([1 cumsum(b(1:end-1))+1]) = 1; c = a(cumsum(index)); 

    Explicação:

    Um vetor de zeros é criado pela primeira vez com o mesmo comprimento que o array de saída (ou seja, a sum de todas as replicações em b ). Os Ones são então colocados no primeiro elemento e cada elemento subseqüente representando onde o início de uma nova seqüência de valores estará na saída. A sum cumulativa do index vetor pode então ser usada para indexar em a , replicando cada valor o número desejado de vezes.

    Por uma questão de clareza, é assim que os vários vetores se parecem para os valores de b indicados na questão:

      index = [1 0 1 0 1 1 0 0] cumsum(index) = [1 1 2 2 3 4 4 4] c = [1 1 3 3 2 5 5 5] 

    EDIT: Por motivos de integridade, existe outra alternativa usando ARRAYFUN , mas isso parece levar de 20 a 100 vezes mais tempo para executar do que a solução acima com vetores de até 10.000 elementos de comprimento:

     c = arrayfun(@(x,y) x.*ones(1,y),a,b,'UniformOutput',false); c = [c{:}]; 

    Há finalmente (a partir de R2015a ) uma function repelem e documentada para fazer isso, repelem . A seguinte syntax, em que o segundo argumento é um vetor, é relevante aqui:

    W = repelem(V,N) , com vetor V e vetor N , cria um vetor W onde o elemento V(i) é repetido N(i) vezes.

    Ou dito de outra forma, “Cada elemento de N especifica o número de vezes para repetir o elemento correspondente de V “.

    Exemplo:

     >> a=[1,3,2,5] a = 1 3 2 5 >> b=[2,2,1,3] b = 2 2 1 3 >> repelem(a,b) ans = 1 1 3 3 2 5 5 5 

    Os problemas de desempenho no repelem do MATLAB foram corrigidos a partir do R2015b. Eu test_rld.m programa test_rld.m do post do chappjc no R2015b, e o repelem agora é mais rápido do que outros algoritmos por um fator 2:

    Gráfico atualizado comparando o tempo de execução do repelem de diferentes métodosAceleração de repelem sobre cumsum + diff (sobre um fator 2)