Agrégations en fenêtre glissante : l'algorithme des deux piles expliqué
Sommaire
En bref
- Un algorithme simple permet de calculer des agrégations (min, max, quantiles, HyperLogLog) sur une fenêtre glissante en temps amorti O(1), sans inverse de l'opération.
- Le truc : deux piles maintiennent les agrégats cumulatifs partiels, permettant une requête en O(1) constant.
- S'appuie sur une technique des années 1970, popularisée récemment ; bien plus utile en pratique que les approches usuelles (monotone queues, segment trees).
- Cas d'usage : streaming analytics, détection d'anomalies, bases de données avec agrégats de fenêtres.
Ce que dit la source
La plupart des agrégations intéressantes (minimum, quantile, HyperLogLog, même sommes flottantes à cause des NaN) n'ont pas d'inverse arithmétique. Le naive algorithm avec double-ended queue ne marche que si combine(x, y) est inversible (ex: addition d'entiers). L'auteur propose donc un algorithme généraliste basé sur deux piles, exploitant l'associativité sans exiger l'inversibilité, avec amortized O(1) par opération et O(1) par requête d'agrégat.
- L'algorithme maintient deux piles (values et cum_aggs) plus un agrégat values_agg : la première accumule les nouveaux éléments, la seconde stocke les agrégats cumulatifs partiels en sens inverse des anciens éléments.
- À chaque W-ème pop (où W est la taille de fenêtre), on vide values en construisant ses agrégats cumulatifs inverses et on les empile sur cum_aggs, ce qui justifie la complexité amortisée O(1) : O(W) travail tous les W pops.
- Ne demande que l'associativité de combine (ex: combine(a, combine(b, c)) = combine(combine(a, b), c)), pas l'inversibilité, ouvrant le champ à min/max, quantiles, HyperLogLog, et autres sketches.
- L'algo garantit O(W) mémoire (une pile par élément en fenêtre active) et requête eval() en O(1) constant, crucial pour streaming analytics à bas latency.
- Originaire probablement des années 1970, l'algo a circulé sous plusieurs noms (van Herk/Gil-Werman en traitement d'image 1990s, adamax sur Stack Overflow 2011, Sleator et algorithme des deux piles pour files) ; la paper Low-Latency Sliding-Window Aggregation (Tangwongsan et al.) l'expose clairement en O(1) exact (non amorti).
Dans les commentaires
Débat très technique et admiratif, peu de friction substantielle. Commentaires enrichissent surtout par contexte historique et cas d'usage concrets (DuckDB segment trees, SQLite windowed aggregates, regression detection à Flakiness.io) ; une objection mineure sur la pédagogie (nommage pop vs shift).
- Plusieurs commentateurs contextualisent l'algo : van Herk/Gil-Werman (image processing années 1990), prefix scans parallélisables (Lichtso note une connexion avec convolutions et réductions parallèles), DuckDB segment trees et SQLite windowed functions qui implémentent déjà des stratégies voisines.
- Un commentaire conteste l'utilité de self.values_agg s'il peut se calculer à la volée ; l'auteur n'a pas réagi, laissant flotter une petite question d'optimalité pédagogique du code.
Notre lecture
Sujet d'algorithmique pure, pas une annonce produit, mais d'intérêt légitime pour qui touche à streaming, analytics, ou bases de données avec agrégats temporels. L'algo lui-même est solide et bien documenté ; la friction historique (l'auteur découvre qu'il réinvente, via une paper récente, quelque chose du folklore algorithmique) renforce la crédibilité plutôt que de l'entamer. À surveiller pour implémentations en prod (Rust benchmark cité : 300M/s pour sommes f32) : l'intérêt croissant chez SQLite/DuckDB suggère que c'est en passe de devenir un best practice. Pas d'action immédiate, mais bon à connaître si vous héritez d'agrégations en fenêtre mal optimisées.