Ripetere le copie di elementi di un array: la decodifica Run-length in MATLAB

Question

Sto cercando di inserire valori multipli in un array utilizzando un array di 'valori' e un allineamento 'contatore'. Per esempio, se:

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

Voglio l'uscita di qualche funzione

c=somefunction(a,b)

essere

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

Quando una (1) ricorre b (1) numero di volte, una (2) ricorre b (2) volte, ecc ...

C'è una funzione built-in in MATLAB che fa questo? Vorrei evitare di utilizzare un ciclo for, se possibile. Ho provato le variazioni di 'repmat ()' e 'Kron ()' senza alcun risultato.

Questo è fondamentalmente Run-length encoding .

Answer 1

problema dichiarazione

Abbiamo un array di valori, vals e runlengths, runlens:

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

Siamo bisogno di ripetere ogni elemento in tempi vals ciascun elemento corrispondente runlens. Così, il risultato finale potrebbe essere:

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

approccio prospettico

Uno degli strumenti più veloci con MATLAB è cumsum ed è molto utile quando si tratta di problemi Vettorizzazione che lavorano su modelli irregolari. Nel problema dichiarato, l'irregolarità viene fornito con i diversi elementi in runlens.

Ora, per sfruttare cumsum, dobbiamo fare due cose qui: Inizializzare un array di zeros e posizionare valori "appropriati" a posizioni "chiave" sulla matrice zero, tale che dopo l'applicazione "cumsum", saremmo finiti con una serie finale di ripetute vals di volte runlens.

Passi: il numero di lasciare che i suddetti passi per dare l'approccio prospettico un punto di vista più semplice:

1) Inizializza zeri matrice: Quale deve essere la lunghezza? Poiché stiamo ripetendo volte runlens, la lunghezza della matrice zeri deve essere la somma di tutti runlens.

2) Trovare posizioni chiave / indici: Ora queste posizioni chiave sono posti lungo l'array zeri in cui ogni elemento da vals iniziare a ripetere. Così, per runlens = [2,2,1,3], le posizioni chiave mappati sulla matrice zeri sarebbe:

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

3) Trovare i valori appropriati: L'ultimo chiodo di essere martellato prima di utilizzare cumsum sarebbe quella di mettere i valori "appropriati" in quelle posizioni chiave. Ora, dal momento che avremmo fatto cumsum subito dopo, se si pensa a stretto contatto, si avrebbe bisogno di una versione di differentiated values con diff , in modo che cumsum su quelli sarebbe riportare la nostra values . Poiché questi valori differenziati sarebbero collocati su una matrice di zeri in luoghi separati dalle distanze runlens, dopo usando cumsum avremmo ciascun elemento vals volte runlens utilizzate come uscita finale.

Codice Soluzione

Ecco l'implementazione ricucire tutti i passaggi sopra menzionati -

% 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)

Pre-allocazione Hack

Come potrebbe essere visto che il codice elencato sopra usa pre-assegnazione con zeri. Ora, secondo questo PRIVI DI DOCUMENTI MATLAB blog il più veloce preassegnazione , si può ottenere molto più veloce pre -allocation con -

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

avvolgendo: Funzione Codice

Per concludere tutto, avremmo un codice funzione compatta per raggiungere questo decodifica run-length in questo modo -

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;

Benchmarking

Codice Benchmarking

elencato accanto è il codice di benchmarking per confrontare i tempi di esecuzione e incrementi nella velocità per l'approccio cumsum+diff dichiarato in questo post sul altro approccio basato cumsum-only su 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')

codice funzione associato, per 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;

Runtime e velocizzare Parcelle

Conclusioni

L'approccio proposto sembra essere dandoci un aumento di velocità notevole rispetto all'approccio cumsum-only, che è di circa 3x

Perché approccio si basa questa nuova cumsum+diff migliore rispetto al precedente approccio cumsum-only?

Bene, l'essenza della ragione è alla fase finale del metodo cumsum-only che ha bisogno di mappare i valori "cumsumed" in vals. Nel nuovo approccio basato cumsum+diff, stiamo facendo diff(vals) invece per i quali MATLAB sta elaborando solo elementi n (dove n è il numero di runLengths) rispetto alla mappatura del numero sum(runLengths) di elementi per l'approccio cumsum-only e questo numero deve essere molte volte più di n e quindi l'aumento di velocità evidente con questo nuovo approccio!

Answer 2

I benchmark

Aggiornamento per R2015b :. repelem ora più veloce per tutti i formati di dati

---

funzioni testati:

1. di MATLAB built-in repelem funzione che è stata aggiunta in R2015a
2. soluzione cumsum di gnovice ( rld_cumsum )
3. cumsum + diff soluzione Divakar ( rld_cumsum_diff )
4. di knedlsepp soluzione accumarray ( knedlsepp5cumsumaccumarray ) da questo post
5. Naive implementazione basata su loop ( naive_jit_test.m ) per testare il compilatore just-in-time

I risultati di test_rld.m su R2015 b :

Old trama temporale mediante R2015 a qui .

risultati :

• repelem è sempre il più veloce di circa un fattore 2.
• rld_cumsum_diff è costantemente più veloce di rld_cumsum.
• repelem è più veloce per le taglie piccole di dati (meno di circa 300-500 elementi)
• rld_cumsum_diff diventa significativamente più veloce di repelem circa 5 000 elementi
• repelem diventa più lento rispetto rld_cumsum da qualche parte tra 30 000 e 300 000 elementi
• rld_cumsum ha all'incirca le stesse prestazioni knedlsepp5cumsumaccumarray
• naive_jit_test.m ha velocità quasi costante e alla pari con rld_cumsum e knedlsepp5cumsumaccumarray per taglie inferiori, un po 'più veloce per grandi dimensioni

Old tasso di trama usando R2015 a qui .

Conclusione

Utilizzare repelem di sotto di circa 5 000 elementi e la soluzione cumsum + diff sopra .

Answer 3

Non c'è alcuna funzione built-in che io conosca, ma qui c'è una soluzione:

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

Spiegazione:

Un vettore di zeri viene creato della stessa lunghezza della matrice di uscita (cioè la somma di tutte le repliche in b). Quelli vengono poi poste nel primo elemento e ogni elemento successivo rappresenta dove l'inizio di una nuova sequenza di valori sarà nell'output. La somma cumulativa del index vettore può quindi essere utilizzato per indicizzare a, replicando ciascun valore del numero di volte desiderato.

Per motivi di chiarezza, questo è ciò che i vari vettori assomigliano per i valori di a e b indicati nella domanda:

        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]

---

Modifica Per ragioni di completezza, si è un'altra alternativa utilizzando ARRAYFUN , ma questo sembra richiedere 20-100 volte più lungo per l'esecuzione rispetto alla soluzione di cui sopra con vettori fino a 10.000 elementi lunghi:

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

Answer 4

V'è infine (come di R2015a ) una funzione built-in e documentato per fare questo, repelem . La sintassi seguente, dove il secondo argomento è un vettore, è rilevante qui:

  

W = repelem(V,N), con il vettore V e vettoriale N, crea un W vettore in cui elemento V(i) si ripete volte N(i).

Oppure, in altre, "Ogni elemento N specifica il numero di ripetizioni del corrispondente elemento di V."

Esempio:

>> 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

I problemi di prestazioni in repelem built-in di MATLAB sono stati fissati come di R2015b. Ho eseguito il programma test_rld.m dal post di chappjc in R2015b, e repelem è ora più veloce rispetto ad altri algoritmi di circa un fattore 2: