Repeat copies of array elements: Run-length decoding in MATLAB

Stwierdzenie Problemu

Mamy tablicę wartości, vals i runlengths, runlens:

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

Musimy powtarzać każdy element w vals razy każdy odpowiadający mu element w runlens. Tak więc wynik końcowy będzie:

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

Perspektywiczne Podejście

Jednym z najszybszych narzędzi z MATLAB jest cumsum i jest bardzo przydatny przy problemach wektoryzacji, które działają na nieregularnych wzorcach. W przedstawionym problemie, nieprawidłowość pochodzi z różne elementy w runlens.

Teraz, aby wykorzystać cumsum, musimy zrobić dwie rzeczy: zainicjalizować tablicę zeros i umieścić "odpowiednie" wartości na" kluczowych " pozycjach nad tablicą zer, tak, że po zastosowaniu "cumsum", skończymy z ostateczną tablicą powtarzanych vals z runlens razy.

Liczba kroków: Policzmy wyżej wymienione kroki, aby dać perspektywę perspektywicznego podejścia łatwiejszą:

1) Inicjalizacja tablicy zer: jaka musi być Długość? Ponieważ powtarzamy runlens razy, długość tablicy zer musi być sumowaniem wszystkich runlens.

2) Znajdź kluczowe pozycje / indeksy: teraz te kluczowe pozycje są miejscami wzdłuż tablicy zer, gdzie każdy element z vals zaczyna się powtarzać. Tak więc dla runlens = [2,2,1,3] kluczowe pozycje odwzorowane na tablicy zer będą następujące:

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

3) Znajdź odpowiednie wartości: ostatnim gwoździem, który należy wbić przed użyciem cumsum, byłoby umieszczenie "odpowiednich" wartości w tych kluczowych pozycjach. Teraz, odkąd będzie robić cumsum wkrótce potem, jeśli dobrze się zastanowisz, będziesz potrzebował differentiated wersji values Z diff, aby cumsum na nich przywrócić nasze values. Ponieważ te zróżnicowane wartości byłyby umieszczone na tablicy zer w miejscach oddzielonych odległościami runlens, po użyciu cumsum każdy element vals powtórzyłby się runlens razy jako końcowy wynik.

Kod Rozwiązania

Oto implementacja wszystkich powyższych wspomniane kroki -

% 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-allocation Hack

Jak widać, powyższy kod używa prealokacji z zerami. Teraz, zgodnie z tym nieudokumentowanym blogiem MATLAB na temat szybszej wstępnej alokacji , można osiągnąć znacznie szybszą wstępną alokację za pomocą-{52]}

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

Wrapping up: Function Code

Aby wszystko zakończyć, mielibyśmy zwarty kod funkcyjny, aby osiągnąć dekodowanie o długości przebiegu w ten sposób -

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

Kod Porównawczy

Poniżej znajduje się kod porównujący czasy uruchamiania i prędkości dla podanego podejścia cumsum+diff w tym poście nad innym podejściem cumsum-only opartym na na 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')

Skojarzony kod funkcji dla 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;

Działek Runtime i Speedup

Wnioski

The proponowane podejście wydaje się dawać nam zauważalne przyspieszenie nad podejściem cumsum-only, które wynosi około 3x !

Dlaczego nowe podejście oparte na cumsum+diff jest lepsze niż poprzednie podejście oparte na cumsum-only?

Cóż, istota rozumu leży na ostatnim etapie podejścia cumsum-only, które wymaga mapowania wartości "cumsumed" na vals. W nowym podejściu cumsum+diff, robimy diff(vals) zamiast tego, dla którego MATLAB przetwarza tylko n elementy (gdzie n jest liczba runLengths) w porównaniu do odwzorowania sum(runLengths) Liczba elementów dla podejścia cumsum-only i liczba ta musi być wielokrotnie większa niż {[45] } i dlatego zauważalne przyspieszenie z tym nowym podejściem!