Lazy Evaluation bei Zeitreihen

Die verzögerte Auswertung ist eine Auswertungsstrategie, bei der die Auswertung eines Ausdrucks so lange aufgeschoben wird, bis sein Wert benötigt wird. In Kombination mit der Memoisation verhindert die Strategie der verzögerten Auswertung wiederholte Berechnungen und kann die Laufzeit bestimmter Funktionen erheblich verkürzen.

Die Zeitreihenbibliothek nutzt die verzögerte Auswertung zur Verarbeitung der Daten. Theoretisch wird ein Ausführungsgraph auf der Grundlage von Zeitreihendaten erstellt, dessen Auswertung erst dann ausgelöst wird, wenn seine Ausgabe konkretisiert wird. Angenommen, ein Objekt bewegt sich in einem eindimensionalen Raum, dessen Position durch x(t) beschrieben wird. Sie können die starke Beschleunigung/Bremsung (h(t)) dieses Objekts anhand seiner Geschwindigkeits- (v(t)) und Beschleunigungs- (a(t)) Zeitreihen wie folgt bestimmen:

# 1d location timeseries
x(t) = input location timeseries

# velocity - first derivative of x(t)
v(t) = x(t) - x(t-1)

# acceleration - second derivative of x(t)
a(t) = v(t) - v(t-1)

# harsh acceleration/braking using thresholds on acceleration
h(t) = +1 if a(t) > threshold_acceleration
     = -1 if a(t) < threshold_deceleration
     = 0 otherwise

Daraus ergibt sich ein einfacher Ausführungsgraph der Form:

x(t) --> v(t) --> a(t) --> h(t)

Auswertungen werden nur ausgelöst, wenn eine Aktion ausgeführt wird, wie z. B. compute h(5...10), d. h. compute h(5), ..., h(10). Die Bibliothek erfasst enge zeitliche Abhängigkeiten zwischen Zeitreihen. In diesem Beispiel ist h(5...10) erforderlich a(5...10), was wiederum erfordert v(4...10), was wiederum erfordert x(3...10). Es werden nur die relevanten x(t) Teile von a(t), v(t) und ausgewertet.

h(5...10) <-- a(5...10) <-- v(4...10) <-- x(3...10)

Darüber hinaus werden Auswertungen zwischengespeichert und können somit bei nachfolgenden Aktionen auf wiederverwendet h werden. Wenn beispielsweise auf eine Anfrage h(7...12) nach eine Anfrage nach folgt h(5...10), würden die h(7...10) zwischengespeicherten Werte genutzt; außerdem würde unter Verwendung von a(11...12), v(10...12)h(11...12) und ausgewertet, wobei wiederum x(9...12) und v(10) genutzt x(9...10) würden, die bei der vorherigen Berechnung zwischengespeichert wurden.

In einem allgemeineren Beispiel könnte man eine geglättete Geschwindigkeitszeitreihe wie folgt definieren:

# 1d location timeseries
x(t) = input location timeseries

# velocity - first derivative of x(t)
v(t) = x(t) - x(t-1)

# smoothened velocity
# alpha is the smoothing factor
# n is a smoothing history
v_smooth(t) =  (v(t)*1.0 + v(t-1)*alpha + ... + v(t-n)*alpha^n) / (1 + alpha + ... + alpha^n)

# acceleration - second derivative of x(t)
a(t) = v_smooth(t) - v_smooth(t-1)

In diesem Beispiel h(l...u) weist Folgendes eine zeitliche Abhängigkeit auf. Die Auswertung von h(l...u) würde diese zeitliche Abhängigkeit durch Memoisation strikt einhalten.

h(l...u) <-- a(l...u) <-- v_smooth(l-1...u) <-- v(l-n-1...u) <-- x(l-n-2...u)

import tspy
from tspy.builders.functions import transformers

x = tspy.time_series([1.0, 2.0, 4.0, 7.0, 11.0, 16.0, 22.0, 29.0, 28.0, 30.0, 29.0, 30.0, 30.0])
v = x.transform(transformers.difference())
a = v.transform(transformers.difference())
h = a.map(harsh).filter(lambda h: h != 0)

print(h[5, 10])

def harsh(a):
    threshold_acceleration = 2.0
    threshold_braking = -2.0

    if (a > threshold_acceleration):
        return +1
    elif (a < threshold_braking):
        return -1
    else:
        return 0