Het artikel bespreekt het probleem van sliding-window aggregatie, waarbij een samenvatting (zoals een som, minimum of maximum) van een set gegevens over een verschuivend venster moet worden berekend. Terwijl eenvoudige methoden met een double-ended queue alleen werken voor operatoren met een inverse, introduceert de auteur het two-stack algoritme voor een bredere klasse van associatieve aggregatiefuncties.
Kernpunten van het algoritme:
- Structuur: Het maakt gebruik van twee stacks (
values en cumaggs) en één extra aggregaat (valuesagg).
- Efficiëntie: Het bereikt een geamortiseerde tijdcomplexiteit van $O(1)$ per operatie en een geheugengebruik van $O(w)$, waarbij $w$ de venstergrootte is.
- Robuustheid: In tegenstelling tot naïeve rollende sommen, voorkomt dit algoritme dat fouten (zoals floating-point onnauwkeurigheden of
NaN-waarden) permanent in de berekening blijven hangen; ze beïnvloeden enkel de vensters waarin de betreffende waarde daadwerkelijk aanwezig is.
De auteur benadrukt dat het algoritme niet alleen eenvoudig te implementeren is, maar ook zeer effectief is voor complexe aggregaties zoals kwantielen of HyperLogLog-benaderingen.
Two-Stack Sliding-Window Aggregatie
Als onze aggregatie een binaire operator is met een inverse, zoals bij gehele getallen en sommaties, is er een zeer eenvoudige oplossing met behulp van een double-ended queue:
from collections import deque
class SlidingWindowSum:
def __init__(self):
self.sum = 0
self.elems = deque()
def push(self, x):
self.sum += x
self.elems.append(x)
def pop(self):
self.sum -= self.elems.popleft()
def eval(self):
return self.sum
Maar wat als onze operator geen inverse heeft? Dit is feitelijk het geval voor de meeste interessante samenvattingen, zoals het minimum, kwantielen, een benadering van het aantal unieke waarden (bijvoorbeeld met HyperLogLog), etc. Zelfs iets simpels als een floating-point som lijdt onder het feit dat floating-point optelling niet inverseerbaar is. Als er bijvoorbeeld een NaN in uw inputgegevens voorkomt bij het bovenstaande naïeve algoritme, zal uw som voor altijd NaN blijven, zelfs lang nadat de foutieve waarde het venster heeft verlaten.
Zes jaar geleden bedacht ik een algoritme voor het bijhouden van enkel het minimum/maximum in een sliding window en plaatste ik dit op cs.stackexchange. Inmiddels beschouw ik dat algoritme als zinloos, omdat er een eenvoudig en efficiënt algoritme bestaat dat dit probleem oplost voor een zeer brede klasse van aggregaties. Ik schrijf dit blogbericht om dit algoritme bekend te maken, omdat ik vind dat het breder bekend zou moeten zijn.
Achtergrond
Ik kwam dit algoritme tegen tijdens het lezen van een veel geavanceerder artikel: Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time door Tangwongsan et al. Waarom is dit artikel getiteld "low-latency"? Omdat het hetzelfde doet als wat ik hieronder beschrijf, maar in $O(1)$ tijd per stap. Echter, beschrijven zij daarin ook een "two-stack" algoritme, dat het in geamortiseerde $O(1)$ tijd doet en vele malen eenvoudiger is.
Geamortiseerde $O(1)$ betekent dat over veel operaties de totale hoeveelheid werk per element constant is, maar dat een individuele operatie veel langer kan duren. Dit is bijna altijd acceptabel, tenzij u absoluut een lage bovengrens voor de latentie nodig heeft.
Opvallend genoeg schrijft dat artikel dit algoritme toe aan "adamax" uit een Stack Overflow-bericht uit 2011. Zij verwijzen op hun beurt naar een college-notitie uit 2001 van D. Sleator als inspiratie. Deze notitie beschrijft echter geen sliding window aggregatie, maar het klassieke two-stack algoritme voor het implementeren van een FIFO-wachtrij en voert daarop een geamortiseerde analyse uit. Uiteindelijk zou ik niet verbaasd zijn als dit algoritme al werd beschreven in een obscuur artikel uit de jaren 70, gezien hoe eenvoudig en briljant het is.
De twee stacks
Net als de auteurs van het artikel zal ik het two-stack algoritme generaliseren naar willekeurige associatieve aggregatiefuncties. Door de aggregatie te abstraheren als een set functies—empty(), unit(x), combine(x, y) en finalize(x)—kun je veel mogelijke aggregaties beschrijven. Bijvoorbeeld een gemiddelde:
empty = lambda: (0, 0)
unit = lambda x: (x, 1)
combine = lambda x, y: (x[0] + y[0], x[1] + y[1])
finalize = lambda x: x[0] / x[1] if x[1] else None
Hierbij hebben de functies de volgende signatures:
fn empty() -> Agg;fn unit(x: Value) -> Agg;fn combine(x: Agg, y: Agg) -> Agg;fn finalize(x: Agg) -> Out;
Ik maak hier een onderscheid tussen Value, Agg en Out. Hoewel ze voor iets als een integer-som oppervlakkig hetzelfde lijken, zouden ze bij een benadering van het aantal unieke strings drie wild verschillende typen zijn: (Value, Agg, Out) = (String, HyperLogLogSketch, u64).
Hier is het algoritme:
class TwoStackAgg:
def __init__(self):
self.values = []
self.values_agg = empty()
self.cum_aggs = []
def push(self, x):
self.values.append(x)
self.values_agg = combine(self.values_agg, unit(x))
def pop(self):
if not self.cum_aggs:
cum_agg = empty()
while self.values:
cum_agg = combine(unit(self.values.pop()), cum_agg)
self.cum_aggs.append(cum_agg)
self.values_agg = empty()
self.cum_aggs.pop()
def eval(self):
return finalize(
combine(self.cum_aggs[-1], self.values_agg)
if self.cum_aggs else self.values_agg
)
Dat is het; dat is het volledige algoritme. Er zijn twee stacks (values en cumaggs) en één extra aggregaat, valuesagg. Op elk gegeven moment bevat valuesagg het aggregaat van values, en cumaggs bevat de cumulatieve aggregaten van alle waarden in ons venster die niet in values zitten, in omgekeerde volgorde. Hiermee kunnen we het aggregaat over ons gehele venster in constante tijd verkrijgen door de laatste waarde van cumaggs te combineren met valuesagg.
Het mooie is dat (ervan uitgaande dat $w$ onze venstergrootte is) we elke $w$-de operatie alle values legen en een lopend aggregaat bijhouden terwijl we de partiële cumulatieve aggregaten op cum_aggs pushen. Dit is wat het geamortiseerde $O(1)$ maakt: het uitvoeren van $O(w)$ interne operaties bij elke $w$-de pop begrenst de totale hoeveelheid werk per element tot $O(1)$, ook al is een enkele operatie mogelijk niet constant in tijd.
Dit wordt het beste gevisualiseerd. Stel dat we [1, 2, ..., 10] sommeren met een sliding window van vier elementen. De status bij elke eval() aanroep zou er dan als volgt uitzien (values_agg wordt niet getoond, omdat dit simpelweg het aggregaat van de values is):
| cum\_aggs | values | uitkomst |
|---|
[] | [] | = 0 |
[] | [1] | = 1 |
[] | [1, 2] | = 1 + 2 |
[] | [1, 2, 3] | = 1 + 2 + 3 |
[] | [1, 2, 3, 4] | = 1 + 2 + 3 + 4 |
[4, 3+4, 2+3+4] | [5] | = 2 + 3 + 4 + 5 |
[4, 3+4] | [5, 6] | = 3 + 4 + 5 + 6 |
[4] | [5, 6, 7] | = 4 + 5 + 6 + 7 |
[] | [5, 6, 7, 8] | = 5 + 6 + 7 + 8 |
[8, 7+8, 6+7+8] | [9] | = 6 + 7 + 8 + 9 |
[8, 7+8] | [9, 10] | = 7 + 8 + 9 + 10 |
[8] | [9, 10] | = 8 + 9 + 10 |
[] | [9, 10] | = 9 + 10 |
[10] | [] | = 10 |
[] | [] | = 0 |
Het totale geheugengebruik is $O(w)$, waarbij $w$ de maximale venstergrootte is. Let op dat ik voor de eenvoud van de analyse en het voorbeeld uitging van een vaste venstergrootte $w$, maar er is niets aan het two-stack algoritme dat dit vereist. U kunt push(x) en pop() zo vaak aanroepen als u wilt tussen elke eval(), waardoor de venstergrootte naar behoefte kan groeien en krimpen.
Floating-point non-associativiteit
We stelden hierboven dat onze combine operator associatief moet zijn, wat betekent: combine(combine(x, y), z) = combine(x, combine(y, z))
Technisch gezien respecteert floating-point optelling dit niet. Desalniettemin is het bovenstaande algoritme nog steeds zeer nuttig, omdat de resultaten nauw aansluiten bij de verwachte uitkomst, zeker als u een gecompenseerd sommatie-algoritme zoals de Kahan-sommatie gebruikt.
Een ander prettig aspect van het two-stack algoritme is dat het geen commutativiteit vereist, mits u de bovenstaande implementatie nauwkeurig volgt. De volgorde van operanden wordt behouden, wat belangrijk kan zijn voor zaken als string-concatenatie.
Er is echter een tweede zeer nuttige eigenschap van dit algoritme: elk aggregaat is strikt een combinatie van de elementen in het venster, en geen enkele waarde van buiten het venster. Dit betekent dat als uw venster een NaN of infinity (of een andere uitschieter) bevat, die waarde alleen de vensters vergiftigt waarin deze voorkomt, en niet de rest van uw berekening.
Zelfs zonder NaN of infinity is dit nuttig, omdat het voorkomt dat fouten eindeloos worden voortgeplant. Als uw sliding window bijvoorbeeld begint met [1e20, 1], dan is dit wat er zou gebeuren bij een naïeve rollende som:
>>> 1e20 + 1 - 1e20 - 1
-1.0
Gecompenseerde sommatie zal deze effecten verminderen, maar door ervoor te zorgen dat uw resultaat niet afhankelijk is van waarden buiten het venster, wordt langetermijn-foutaccumulatie volledig geëlimineerd.
Two-Stack Sliding-Window Aggregatie
Als onze aggregatie een binaire operator is met een inverse, zoals bij gehele getallen en sommaties, is er een zeer eenvoudige oplossing met behulp van een double-ended queue:
from collections import deque
class SlidingWindowSum:
def __init__(self):
self.sum = 0
self.elems = deque()
def push(self, x):
self.sum += x
self.elems.append(x)
def pop(self):
self.sum -= self.elems.popleft()
def eval(self):
return self.sum
Maar wat als onze operator geen inverse heeft? Dit is feitelijk het geval voor de meeste interessante samenvattingen, zoals het minimum, kwantielen, een benadering van het aantal unieke waarden (bijvoorbeeld met HyperLogLog), etc. Zelfs iets simpels als een floating-point som lijdt onder het feit dat floating-point optelling niet inverseerbaar is. Als er bijvoorbeeld een NaN in uw inputgegevens voorkomt bij het bovenstaande naïeve algoritme, zal uw som voor altijd NaN blijven, zelfs lang nadat de foutieve waarde het venster heeft verlaten.
Zes jaar geleden bedacht ik een algoritme voor het bijhouden van enkel het minimum/maximum in een sliding window en plaatste ik dit op cs.stackexchange. Inmiddels beschouw ik dat algoritme als zinloos, omdat er een eenvoudig en efficiënt algoritme bestaat dat dit probleem oplost voor een zeer brede klasse van aggregaties. Ik schrijf dit blogbericht om dit algoritme bekend te maken, omdat ik vind dat het breder bekend zou moeten zijn.
Achtergrond
Ik kwam dit algoritme tegen tijdens het lezen van een veel geavanceerder artikel: Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time door Tangwongsan et al. Waarom is dit artikel getiteld "low-latency"? Omdat het hetzelfde doet als wat ik hieronder beschrijf, maar in $O(1)$ tijd per stap. Echter, beschrijven zij daarin ook een "two-stack" algoritme, dat het in geamortiseerde $O(1)$ tijd doet en vele malen eenvoudiger is.
Geamortiseerde $O(1)$ betekent dat over veel operaties de totale hoeveelheid werk per element constant is, maar dat een individuele operatie veel langer kan duren. Dit is bijna altijd acceptabel, tenzij u absoluut een lage bovengrens voor de latentie nodig heeft.
Opvallend genoeg schrijft dat artikel dit algoritme toe aan "adamax" uit een Stack Overflow-bericht uit 2011. Zij verwijzen op hun beurt naar een college-notitie uit 2001 van D. Sleator als inspiratie. Deze notitie beschrijft echter geen sliding window aggregatie, maar het klassieke two-stack algoritme voor het implementeren van een FIFO-wachtrij en voert daarop een geamortiseerde analyse uit. Uiteindelijk zou ik niet verbaasd zijn als dit algoritme al werd beschreven in een obscuur artikel uit de jaren 70, gezien hoe eenvoudig en briljant het is.
De twee stacks
Net als de auteurs van het artikel zal ik het two-stack algoritme generaliseren naar willekeurige associatieve aggregatiefuncties. Door de aggregatie te abstraheren als een set functies—empty(), unit(x), combine(x, y) en finalize(x)—kun je veel mogelijke aggregaties beschrijven. Bijvoorbeeld een gemiddelde:
empty = lambda: (0, 0)
unit = lambda x: (x, 1)
combine = lambda x, y: (x[0] + y[0], x[1] + y[1])
finalize = lambda x: x[0] / x[1] if x[1] else None
Hierbij hebben de functies de volgende signatures:
fn empty() -> Agg;fn unit(x: Value) -> Agg;fn combine(x: Agg, y: Agg) -> Agg;fn finalize(x: Agg) -> Out;
Ik maak hier een onderscheid tussen Value, Agg en Out. Hoewel ze voor iets als een integer-som oppervlakkig hetzelfde lijken, zouden ze bij een benadering van het aantal unieke strings drie wild verschillende typen zijn: (Value, Agg, Out) = (String, HyperLogLogSketch, u64).
Hier is het algoritme:
class TwoStackAgg:
def __init__(self):
self.values = []
self.values_agg = empty()
self.cum_aggs = []
def push(self, x):
self.values.append(x)
self.values_agg = combine(self.values_agg, unit(x))
def pop(self):
if not self.cum_aggs:
cum_agg = empty()
while self.values:
cum_agg = combine(unit(self.values.pop()), cum_agg)
self.cum_aggs.append(cum_agg)
self.values_agg = empty()
self.cum_aggs.pop()
def eval(self):
return finalize(
combine(self.cum_aggs[-1], self.values_agg)
if self.cum_aggs else self.values_agg
)
Dat is het; dat is het volledige algoritme. Er zijn twee stacks (values en cumaggs) en één extra aggregaat, valuesagg. Op elk gegeven moment bevat valuesagg het aggregaat van values, en cumaggs bevat de cumulatieve aggregaten van alle waarden in ons venster die niet in values zitten, in omgekeerde volgorde. Hiermee kunnen we het aggregaat over ons gehele venster in constante tijd verkrijgen door de laatste waarde van cumaggs te combineren met valuesagg.
Het mooie is dat (ervan uitgaande dat $w$ onze venstergrootte is) we elke $w$-de operatie alle values legen en een lopend aggregaat bijhouden terwijl we de partiële cumulatieve aggregaten op cum_aggs pushen. Dit is wat het geamortiseerde $O(1)$ maakt: het uitvoeren van $O(w)$ interne operaties bij elke $w$-de pop begrenst de totale hoeveelheid werk per element tot $O(1)$, ook al is een enkele operatie mogelijk niet constant in tijd.
Dit wordt het beste gevisualiseerd. Stel dat we [1, 2, ..., 10] sommeren met een sliding window van vier elementen. De status bij elke eval() aanroep zou er dan als volgt uitzien (values_agg wordt niet getoond, omdat dit simpelweg het aggregaat van de values is):
| cum\_aggs | values | uitkomst |
|---|
[] | [] | = 0 |
[] | [1] | = 1 |
[] | [1, 2] | = 1 + 2 |
[] | [1, 2, 3] | = 1 + 2 + 3 |
[] | [1, 2, 3, 4] | = 1 + 2 + 3 + 4 |
[4, 3+4, 2+3+4] | [5] | = 2 + 3 + 4 + 5 |
[4, 3+4] | [5, 6] | = 3 + 4 + 5 + 6 |
[4] | [5, 6, 7] | = 4 + 5 + 6 + 7 |
[] | [5, 6, 7, 8] | = 5 + 6 + 7 + 8 |
[8, 7+8, 6+7+8] | [9] | = 6 + 7 + 8 + 9 |
[8, 7+8] | [9, 10] | = 7 + 8 + 9 + 10 |
[8] | [9, 10] | = 8 + 9 + 10 |
[] | [9, 10] | = 9 + 10 |
[10] | [] | = 10 |
[] | [] | = 0 |
Het totale geheugengebruik is $O(w)$, waarbij $w$ de maximale venstergrootte is. Let op dat ik voor de eenvoud van de analyse en het voorbeeld uitging van een vaste venstergrootte $w$, maar er is niets aan het two-stack algoritme dat dit vereist. U kunt push(x) en pop() zo vaak aanroepen als u wilt tussen elke eval(), waardoor de venstergrootte naar behoefte kan groeien en krimpen.
Floating-point non-associativiteit
We stelden hierboven dat onze combine operator associatief moet zijn, wat betekent: combine(combine(x, y), z) = combine(x, combine(y, z))
Technisch gezien respecteert floating-point optelling dit niet. Desalniettemin is het bovenstaande algoritme nog steeds zeer nuttig, omdat de resultaten nauw aansluiten bij de verwachte uitkomst, zeker als u een gecompenseerd sommatie-algoritme zoals de Kahan-sommatie gebruikt.
Een ander prettig aspect van het two-stack algoritme is dat het geen commutativiteit vereist, mits u de bovenstaande implementatie nauwkeurig volgt. De volgorde van operanden wordt behouden, wat belangrijk kan zijn voor zaken als string-concatenatie.
Er is echter een tweede zeer nuttige eigenschap van dit algoritme: elk aggregaat is strikt een combinatie van de elementen in het venster, en geen enkele waarde van buiten het venster. Dit betekent dat als uw venster een NaN of infinity (of een andere uitschieter) bevat, die waarde alleen de vensters vergiftigt waarin deze voorkomt, en niet de rest van uw berekening.
Zelfs zonder NaN of infinity is dit nuttig, omdat het voorkomt dat fouten eindeloos worden voortgeplant. Als uw sliding window bijvoorbeeld begint met [1e20, 1], dan is dit wat er zou gebeuren bij een naïeve rollende som:
>>> 1e20 + 1 - 1e20 - 1
-1.0
Gecompenseerde sommatie zal deze effecten verminderen, maar door ervoor te zorgen dat uw resultaat niet afhankelijk is van waarden buiten het venster, wordt langetermijn-foutaccumulatie volledig geëlimineerd.
Groetjes,