Repita cópias dos elementos da matriz: decodificação de run-comprimento no MATLAB

Question

Estou tentando inserir vários valores em uma matriz usando uma matriz 'valores' e uma matriz 'contador'. Por exemplo, se:

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

Eu quero a saída de alguma função

c=somefunction(a,b)

ser

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

Onde a (1) se repete B (1) Número de vezes, a (2) se repete B (2) vezes, etc ...

Existe uma função interna no Matlab que isso faz isso? Eu gostaria de evitar usar um loop for for possível. Eu tentei variações de 'repmat ()' e 'kron ()' sem sucesso.

Isso é basicamente Run-length encoding.

Answer 1

Declaração de problemas

Temos uma variedade de valores, vals e comprimentos de execução, 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, a saída final seria:

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

Abordagem prospectiva

Uma das ferramentas mais rápidas com o MATLAB é cumsum e é muito útil ao lidar com os 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 cumsum, precisamos fazer duas coisas aqui: inicializar uma matriz de zeros e coloque os valores "apropriados" em posições de "chave" sobre a matriz Zeros, de modo que depois de "cumsum"É aplicado, acabaríamos com uma variedade final de repetida vals do runlens vezes.

Passos: Vamos numerar as etapas acima mencionadas para dar à abordagem prospectiva uma perspectiva mais fácil:

1) Inicialize a matriz Zeros: qual deve ser o comprimento? Já que estamos repetindo runlens vezes, a duração da matriz zeros deve ser a soma de todos runlens.

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

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

3) Encontre valores apropriados: o prego final a ser martelado antes de usar cumsum seria colocar valores "apropriados" nessas posições -chave. Agora, já que estaríamos fazendo cumsum Logo depois, se você pensar de perto, precisaria de um differentiated versão de values com diff, para que cumsum sobre isso faria Traga de volta o nosso values. Uma vez que esses valores diferenciados seriam colocados em uma matriz zeros em lugares separados pelo runlens distâncias, depois de usar cumsum nós teríamos cada um vals elemento repetido runlens vezes como a saída final.

Código da solução

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

% 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 poderia ser visto que o código listado acima usa pré-alocação com zeros. Agora, de acordo com isso Blog do MATLAB sem documentos em pré-alocação mais rápida, pode -se alcançar uma pré -alocação muito mais rápida com -

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

Encerrando: código de função

Para encerrar tudo, teríamos um código de função compacto para alcançar essa decodificação do comprimento da execução como So -

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 em seguida é o código de benchmarking para comparar os horários de execução e acelerações para o indicado cumsum+diff abordagem neste post sobre o outro cumsum-only abordagem baseada sobre 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 função 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

Conclusões

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

Por que isso é novo cumsum+diff abordagem baseada melhor do que a anterior cumsum-only abordagem?

Bem, a essência da razão está na etapa final do cumsum-only abordagem que precisa mapear os valores "acumulados" em vals. No novo cumsum+diff abordagem baseada, estamos fazendo diff(vals) Em vez disso, para o qual o MATLAB está processando apenas n elementos (onde n é o número de comprimentos de execução) em comparação com o mapeamento de sum(runLengths) número de elementos para o cumsum-only abordagem e esse número deve ser muitas vezes mais do que n E, portanto, a aceitação perceptível com essa nova abordagem!

Answer 2

Benchmarks

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

---

Funções testadas:

1. MATLAB INCLUÍDO DE MATLAB repelem função que foi adicionada no R2015A
2. GNOVICE cumsum solução (rld_cumsum)
3. Divakar's cumsum+diff solução (rld_cumsum_diff)
4. Knedlsepp's accumarray solução (knedlsepp5cumsumaccumarray) a partir de esta postagem
5. Implementação ingênua baseada em loop (naive_jit_test.m) para testar o compilador just-in-time

Resultados de test_rld.m no R2015b:

Gráfico de tempo antigo usando R2015uma aqui.

Descobertas:

• repelem é sempre o mais rápido em aproximadamente um fator de 2.
• rld_cumsum_diff é consistentemente mais rápido do que rld_cumsum.
• repelem é mais rápido para tamanhos de dados pequenos (menos de 300-500 elementos)
• rld_cumsum_diff torna -se significativamente mais rápido que repelem Cerca de 5 000 elementos
• repelem torna -se mais lento que rld_cumsum Em 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 a par com rld_cumsum e knedlsepp5cumsumaccumarray Para tamanhos menores, um pouco mais rápido para tamanhos grandes

Gráfico de taxa antiga usando R2015uma aqui.

Conclusão

Usar repelem abaixo de cerca de 5 000 elementos e o cumsum+diff solução acima.

Answer 3

Não há função interna que eu 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 primeiro com o mesmo comprimento que a matriz de saída (ou seja, a soma de todas as repetições em b). Os são então colocados no primeiro elemento e cada elemento subsequente representando onde o início de uma nova sequência de valores estará na saída. A soma cumulativa do vetor index pode então ser usado 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 pelos valores de a e b dado na pergunta:

        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]

---

EDITAR: Por uma questão de completude, lá é outra alternativa usando Arrayfun, mas isso parece levar de 20 a 100 vezes mais para ser executado 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{:}];

Answer 4

Finalmente existe (como de R2015A) uma função embutida e documentada para fazer isso, repelem. A sintaxe a seguir, onde o segundo argumento é um vetor, é relevante aqui:

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

Ou coloque de outra maneira, "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

Answer 5

Os problemas de desempenho no embutido do Matlab repelem foram consertados a partir do R2015b. Eu corri o test_rld.m programa da postagem do ChappJC em R2015b e repelem agora é mais rápido que outros algoritmos por cerca de um fator 2: