Wiederholen Sie Kopien von Array-Elementen: Decodierung der Länge in Matlab

Question

Ich versuche, mehrere Werte mit einem "Werte" -Array und einem "Zähler" -Array in ein Array einzufügen. Zum Beispiel wenn: wenn:

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

Ich möchte die Ausgabe einer Funktion

c=somefunction(a,b)

sein

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

Wobei a (1) B (1) Anzahl oft wiederholt, ist a (2) B (2) mal usw.

Gibt es eine integrierte Funktion in Matlab, die dies tut? Ich möchte es vermeiden, wenn möglich eine für Schleife zu verwenden. Ich habe Variationen von 'repmat ()' und 'kron ()' ohne Erfolg ausprobiert.

Dies ist im Grunde genommen Run-length encoding.

Answer 1

Problemstellung

Wir haben eine Reihe von Werten, vals und Runlenlängen, runlens:

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

Wir werden benötigt, um jedes Element in zu wiederholen vals mal jedes entsprechende Element in runlens. Somit wäre die endgültige Ausgabe:

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

Prospektiver Ansatz

Eines der schnellsten Werkzeuge mit MATLAB ist cumsum und ist sehr nützlich, wenn es um vektorisierende Probleme geht, die auf unregelmäßigen Mustern arbeiten. In dem angegebenen Problem kommt die Unregelmäßigkeit mit den verschiedenen Elementen in runlens.

Nun, um zu nutzen cumsum, Wir müssen hier zwei Dinge tun: initialisieren Sie eine Reihe von Auswahl an zeros und platzieren Sie "entsprechende" Werte an "Schlüssel" -Positionen über das Nullen -Array, so dass danach "cumsum"wird angewendet, wir würden eine endgültige Auswahl von wiederholten Wiederholungen haben vals von runlens mal.

Schritte: Zahlen wir die oben genannten Schritte, um dem prospektiven Ansatz eine einfachere Perspektive zu geben:

1) Initialisieren von Nullenarray: Was muss die Länge sein? Da wiederholen wir uns runlens Zeiten müssen die Länge des Nullenarrays die Zusammenfassung aller sein runlens.

2) Suchen vals wiederholen. So für runlens = [2,2,1,3], Die wichtigsten Positionen, die auf das Nullenarray abgebildet sind, wären:

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

3) Finden Sie geeignete Werte: Der endgültige Nagel, der vor der Verwendung gehämmert werden soll cumsum Würde "geeignete" Werte in diese Schlüsselpositionen einfügen. Nun, da wir tun würden cumsum Bald darauf würden Sie eine brauchen, wenn Sie genau denken, Sie brauchen eine differentiated Version von values mit diff, so dass cumsum auf diese würden Bring unsere zurück values. Da diese differenzierten Werte an einem Nullenarray an Orten platziert würden, die von der getrennt sind runlens Entfernungen nach der Verwendung cumsum Wir hätten jeweils vals Element wiederholt runlens mal als endgültige Ausgabe.

Lösungscode

Hier ist die Implementierung, die alle oben genannten Schritte aufnimmt -

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

Voransatzhack

Wie man erscheint, verwendet der oben aufgeführte Code die Voranierung mit Nullen. Nun dadurch Undokumentiertes Matlab-Blog zur schnelleren Voranierung, man kann eine viel schnellere Voranierung mit -erreichen -

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

Wickeln: Funktionscode

Um alles abzuschließen, hätten wir einen kompakten Funktionscode, um diese langen Dekodierung wie so zu erreichen -

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

Benchmarking -Code

Als nächstes ist der Benchmarking -Code aufgeführt, um Laufzeiten und Beschleunigungen für die angegebenen zu vergleichen cumsum+diff Annäherung in diesem Beitrag über die Sonstiges cumsum-only basierter Ansatz an 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')

Zugeordneter Funktionscode für 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;

Laufzeit- und Geschwindigkeitsdiagramme

Schlussfolgerungen

Der vorgeschlagene Ansatz scheint uns eine spürbare Beschleunigung über die zu verleihen cumsum-only Ansatz, was ungefähr geht 3x!

Warum ist das neu cumsum+diff basierter Ansatz besser als der vorherige cumsum-only sich nähern?

Nun, die Essenz des Grundes liegt am letzten Schritt der cumsum-only Ansatz vals. Im neuen cumsum+diff basierter Ansatz, wir tun es diff(vals) Stattdessen, für welche MATLAB nur verarbeitet n Elemente (wobei n die Anzahl der Runlenlängen ist) im Vergleich zur Zuordnung von sum(runLengths) Anzahl der Elemente für die cumsum-only Ansatz und diese Zahl muss um viele Male mehr sein als n Und deshalb die merkliche Beschleunigung mit diesem neuen Ansatz!

Answer 2

Benchmarks

Aktualisiert für R2015B: repelem jetzt am schnellsten für alle Datengrößen.

---

Getestete Funktionen:

1. Matlab's eingebaut repelem Funktion, die in R2015A hinzugefügt wurde
2. Gnovices cumsum Lösung (rld_cumsum)
3. Divakars cumsum+diff Lösung (rld_cumsum_diff)
4. Knedlsepps accumarray Lösung (knedlsepp5cumsumaccumarray) aus dieser Beitrag
5. Naive Loop-basierte Implementierung (naive_jit_test.m) um den Just-in-Time-Compiler zu testen

Ergebnisse von test_rld.m auf R2015b:

Altes Timing -Diagramm mit R2015a hier.

Ergebnisse:

• repelem ist immer der schnellste um ungefähr einen Faktor von 2.
• rld_cumsum_diff ist durchweg schneller als rld_cumsum.
• repelem ist für kleine Datengrößen am schnellsten (weniger als 300-500 Elemente)
• rld_cumsum_diff wird deutlich schneller als repelem ungefähr 5 000 Elemente
• repelem wird langsamer als rld_cumsum irgendwo zwischen 30 000 und 300 000 Elemente
• rld_cumsum hat ungefähr die gleiche Leistung wie knedlsepp5cumsumaccumarray
• naive_jit_test.m hat nahezu konstante Geschwindigkeit und gleichzeitig mit rld_cumsum und knedlsepp5cumsumaccumarray für kleinere Größen, etwas schneller für große Größen

Old Tarif -Diagramm mit R2015a hier.

Fazit

Verwenden repelem unten etwa 5 000 Elemente und die cumsum+diff Lösung oben.

Answer 3

Ich kenne keine integrierte Funktion, aber hier ist eine Lösung:

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

Erläuterung:

Zuerst wird ein Vektor von Nullen aus der gleichen Länge wie das Ausgangsarray erstellt (dh die Summe aller Replikationen in b). Diejenigen werden dann in das erste Element platziert und jedes nachfolgende Element, das darstellt, wo der Beginn einer neuen Wertesequenz in der Ausgabe befindet. Die kumulative Summe des Vektors index kann dann verwendet werden, um in die Index zu indexieren a, replizieren Sie jeden Wert die gewünschte Häufigkeit.

Aus Gründen der Klarheit sehen die verschiedenen Vektoren für die Werte von aus a und b in der Frage gegeben:

        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]

---

BEARBEITEN: Um der Vollständigkeit willen ist Eine andere Alternative Arrayfun, Aber dies scheint zwischen 20 und 100 Mal länger zu dauern als die oben genannte Lösung, wobei Vektoren bis zu 10.000 Elemente lang sind:

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

Answer 4

Es gibt endlich (als R2015A) eine integrierte und dokumentierte Funktion, um dies zu tun, repelem. Die folgende Syntax, bei der das zweite Argument ein Vektor ist, ist hier relevant:

W = repelem(V,N), mit Vektor V und Vektor N, erstellt einen Vektor W wo Element V(i) wird wiederholt N(i) mal.

Oder einen anderen Weg sagen ", jedes Element von N Gibt die Anzahl der Zeiten an, um das entsprechende Element von zu wiederholen V."

Beispiel:

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

Die Leistungsprobleme in Matlabs integriertem Integrieren repelem wurden ab R2015B festgelegt. Ich habe die geführt test_rld.m Programm aus Chappjcs Post in R2015B und repelem ist jetzt schneller als andere Algorithmen um einen Faktor 2: