Konstante Zeit für gleitende Fensteraggregation: Eine verbesserte FIFO

Dieser Beitrag präsentiert eine verbesserte FIFO-Datenstruktur, die eine gleitende Fensteraggregation in konstanter Zeit ermöglicht. Traditionelle Ansätze mit Dual-Stack-Strukturen erweisen sich als ineffizient. Der Autor stellt eine neue Methode vor, die geschickt "Eingabelisten" und "Ausgabelisten" mit ihren laufenden und Suffix-Produkten verwaltet, um eine Aggregation über beliebige Monoide mit konstanter Worst-Case-Zeitkomplexität zu erreichen. Dies vermeidet das umfangreiche Kopieren und die Redundanz früherer Methoden und bietet erhebliche praktische Vorteile. Python-Code ist zur Implementierung enthalten.