原标题:《Two-Stack Sliding-Window Aggregation》 评分: 25 | 作者: surprisetalk 💭 O(1) 都做到了,难道还要让 pop 从左边偷走元素? 🎯 讨论背景 滑动窗口聚合要持续维护最近 W 个数据点的 sum、min、max 或可合并的统计 sketch,常见于实时监控、streaming analytics(流式分析)和 anomaly detection(异常检测)。朴素实现会在每次加入新值、淘汰旧值后重新扫描整窗,成本为 O(W);双栈结构把 FIFO 队列拆成输入栈和输出栈,并分别保存累计聚合,以获得高效更新和查询。该方法要求聚合操作可通过 merge 合并,且将 sketch 大小视为固定;它还避免让已移出窗口的浮点历史值持续影响结果。讨论同时聚焦 API 语义:该结构实际从左端淘汰最早元素,因而 pop 是否应改称 shift 或 popleft,直接关系到代码可读性。 📌 讨论焦点 算法效率与流式应用价值 评论者认为该双栈方法以额外空间换取计算效率,避免每次窗口移动都重新聚合全部元素。它适合 streaming