Repita cópias dos elementos da matriz: decodificação de run-comprimento no MATLAB
-
21-09-2019 - |
Pergunta
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
.
Solução
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!
Outras dicas
Benchmarks
Atualizado para R2015b: repelem
agora mais rápido para todos os tamanhos de dados.
Funções testadas:
- MATLAB INCLUÍDO DE MATLAB
repelem
função que foi adicionada no R2015A - GNOVICE
cumsum
solução (rld_cumsum
) - Divakar's
cumsum
+diff
solução (rld_cumsum_diff
) - Knedlsepp's
accumarray
solução (knedlsepp5cumsumaccumarray
) a partir de esta postagem - 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 querld_cumsum
.repelem
é mais rápido para tamanhos de dados pequenos (menos de 300-500 elementos)rld_cumsum_diff
torna -se significativamente mais rápido querepelem
Cerca de 5 000 elementosrepelem
torna -se mais lento querld_cumsum
Em algum lugar entre 30 000 e 300 000 elementosrld_cumsum
tem aproximadamente o mesmo desempenho queknedlsepp5cumsumaccumarray
naive_jit_test.m
tem velocidade quase constante e a par comrld_cumsum
eknedlsepp5cumsumaccumarray
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
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{:}];
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 vetorV
e vetorN
, cria um vetorW
onde elementoV(i)
é repetidoN(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
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: