Effizienz der Zeitreihenaggregation

8

Ich muss im Allgemeinen eine Zeitreihe mit unregelmäßigem Timing mit einer gegebenen Aggregationsfunktion (d. h. Summe, Mittelwert usw.) zusammenfassen. Die derzeitige Lösung scheint jedoch ineffizient und langsam zu sein.

Nehmen Sie die Aggregationsfunktion:

%Vor%

Beachten Sie, dass sowohl array als auch groupIndex 2D sein können. Jede Spalte in array ist eine unabhängige Serie, die aggregiert werden soll. Die Spalten von groupIndex sollten jedoch (als Zeile) zusammengenommen werden, um einen Zeitraum anzugeben.

Wenn wir dann eine unregelmäßige Zeitreihe dazu bringen (beachten Sie, dass die zweite Periode um eine Basisperiode länger ist), sind die Timing-Ergebnisse schlecht:

%Vor%

Mit dem Profiler können wir herausfinden, dass die grpIdx -Zeile etwa 1/4 der Ausführungszeit (.28 s) und die iSer -Schleife etwa 3/4 (1,17 s) der gesamten 1.48 s).

Vergleichen Sie dies mit dem Zeitraum-indifferenten Fall:

%Vor%

Gibt es eine effizientere Möglichkeit, diese Daten zu aggregieren?

Timing-Ergebnisse

Nehmen wir jede Antwort und setzen sie in eine separate Funktion, hier sind die Timing-Ergebnisse, die ich mit timeit mit Matlab 2015b unter Windows 7 mit einem Intel i7 erhalten habe:

%Vor%

Erläuterung zu groupIndex

Ein Beispiel für eine 2D groupIndex wäre, wenn sowohl die Jahreszahl als auch die Wochennummer für eine Reihe von Tagesdaten für 1980-2015 angegeben sind:

%Vor%

Somit wird eine "Jahr-Woche" -Periode eindeutig durch eine Zeile von groupIndex identifiziert. Dies wird effektiv gehandhabt, indem unique(groupIndex, 'rows') aufgerufen wird und die dritte Ausgabe genommen wird. Sie können also diesen Teil der Frage ignorieren.

    
David Kelley 10.11.2015, 17:28
quelle

5 Antworten

8

Methode # 1

Sie können die Maske für grIdx über alle erstellen groups auf einmal mit bsxfun(@eq,..) . Nun können Sie für collapseFn als @sum matrix-multiplication und haben somit einen vollständig vektorisierten Ansatz, so -

%Vor%

Für collapseFn als @mean müssen Sie ein bisschen mehr arbeiten, wie hier gezeigt -

%Vor%

Methode 2

Wenn Sie mit einem generischen collapseFn arbeiten, können Sie mit der 2D-Maske M , die mit der vorherigen Methode erstellt wurde, in die Zeilen von array indexieren und so die Komplexität von O(n^2) auf% co_de ändern %. Einige schnelle Tests deuten darauf hin, dass der ursprüngliche Loopy-Code merklich beschleunigt wird. Hier ist die Implementierung -

%Vor%

Bitte beachten Sie, dass O(n) in 1 die Dimension angibt, auf die collapseFn(array(M(:,iGr),:),1) angewendet wird, so dass collapseFn dort essentiell ist.

Bonus

Durch den Namen 1 scheint es Integer-Werte zu geben, die missbraucht werden könnten , um eine effizientere groupIndex -Erstellung zu erhalten, indem jede Zeile von M als Indizierungstupel berücksichtigt wird konvertiert jede Zeile von groupIndex in einen Skalar und erhält schließlich eine 1D-Array-Version von groupIndex . Dies muss effizienter sein, da die Datenmenge jetzt groupIndex ist. Dieser 0(n) könnte für alle in diesem Beitrag aufgelisteten Ansätze verwendet werden. Also, wir hätten M gerne -

%Vor%     
Divakar 12.11.2015 21:14
quelle
6

Mex Funktion 1

HAMMER TIME: Mex Funktion um es zu zerquetschen : Der Base-Case-Test mit dem ursprünglichen Code aus der Frage dauerte 1.3314139 Sekunden auf meinem Computer. IMHO, die zweitschnellste Antwort von @Divakar ist:

%Vor%

Die verstrichene Zeit beträgt 0,589330 Sekunden.

Dann meine MEX-Funktion:

%Vor%

Die abgelaufene Zeit beträgt 0,079725 Sekunden.

Testen, dass wir dieselbe Antwort erhalten: norm(groups2-groups3) gibt 0 zurück und norm(aggArray2 - aggArray3) gibt 2.3959e-15 zurück. Die Ergebnisse entsprechen auch dem ursprünglichen Code.

Code zum Generieren der Testbedingungen:

%Vor%

Für pure Geschwindigkeit, gehen Sie Mex. Wenn der Gedanke, C ++ Code / Komplexität zu kompilieren, zu sehr schmerzt, gehen Sie mit Divakars Antwort. Noch ein Disclaimer: Ich habe meine Funktion nicht einem harten Test unterzogen.

Mex Ansatz 2

Für mich etwas überraschend, erscheint dieser Code in einigen Fällen sogar schneller als die vollständige Mex-Version (z. B. in diesem Test dauerte ca. 0,05 Sekunden). Es verwendet eine mex-Funktion mg_getRowsWithKey , um die Indizes von Gruppen herauszufinden. Ich denke, dass es sein kann, weil mein Array, das in der vollen mex-Funktion kopiert, nicht so schnell ist, wie es sein könnte, und / oder overhead vom Aufrufen von "feval". Es ist im Grunde die gleiche algorithmische Komplexität wie die andere Version.

%Vor%

Wenn Sie array(groups(1)==groupIndex,:) ausführen, um Array-Einträge aus der gesamten Gruppe herauszuholen, durchsuchen Sie die gesamte Länge von groupIndex. Wenn Sie Millionen von Zeileneinträgen haben, wird das total scheiße. array(map{1},:) ist viel effizienter.

Es gibt immer noch unnötiges Kopieren von Speicher und anderen Overhead, die mit dem Aufruf von 'feval' bei der Minimierungsfunktion verbunden sind. Wenn Sie die Aggregatorfunktion effizient in C ++ implementieren, um das Kopieren von Speicher zu vermeiden, kann wahrscheinlich eine weitere 2x-Beschleunigung erreicht werden.

    
Matthew Gunn 13.11.2015 11:40
quelle
4

Ein wenig spät auf die Party, aber eine einzelne Schleife mit accumarray macht a großer Unterschied:

%Vor%

Dies wird mit timeit in MATLAB R2016b für die Beispieldaten in der Frage festgelegt das Folgende:

%Vor%

Über eine 500-fache Beschleunigung!

    
gnovice 06.06.2017 15:06
quelle
3

Weg mit der inneren Schleife, d. h.

%Vor%

und Aufruf der Minimierungsfunktion mit einem Dimensionsparameter

%Vor%

gibt bereits eine Beschleunigung (3x auf meiner Maschine) und vermeidet die Fehler z. sum oder mean produce, wenn sie auf eine einzelne Zeile mit Daten ohne Dimensionsparameter und dann auf Spalten statt auf Beschriftungen stoßen.

Wenn Sie nur einen Gruppenbezeichnungsvektor hätten, d. h. gleiche Gruppenbezeichnungen für alle Datenspalten, könnten Sie weiter beschleunigen:

%Vor%

Die letztgenannten Funktionen geben identische Ergebnisse für Ihr Beispiel mit einer 6-fachen Beschleunigung, können aber nicht mit verschiedenen Gruppenbeschriftungen pro Datenspalte umgehen.

Annahme eines 2D-Testfalls für den Gruppenindex (hier auch mit 10 verschiedenen Spalten für groupIndex:

%Vor%

Die verstrichene Zeit beträgt 2,646297 Sekunden. Die abgelaufene Zeit beträgt 1,214365 Sekunden. Die abgelaufene Zeit beträgt 0,039678 Sekunden (!!!!).

%Vor%

Ich denke, das ist so schnell wie es geht, ohne MEX zu verwenden. Dank dem Vorschlag von Matthew Gunn! Profiling zeigt, dass 'unique' hier wirklich günstig ist und nur der erste und letzte Index der sich wiederholenden Zeilen in groupIndex rauscht. Ich bekomme 88x Beschleunigung mit dieser Iteration der Aggregation.

    
Felix Darvas 10.11.2015 21:25
quelle
0

Nun, ich habe eine Lösung, die fast so schnell ist wie die mex, aber nur mit Matlab. Die Logik ist die gleiche wie die meisten der oben genannten und erzeugt eine Dummy-2D-Matrix, aber anstelle von @eq initialisiere ich ein logisches Array von Anfang an.

Die verstrichene Zeit für meine ist 0.172975 Sekunden. Abgelaufene Zeit für Divakar 0.289122 Sekunden.

%Vor%     
eyalsoreq 14.11.2015 11:31
quelle

Tags und Links