双栈滑动窗口聚合 — Hacker News 中文摘要
来源：orlp.net — 113 分 · by surprisetalk
📋 概述
作者解释滑动窗口聚合的经典难题：带逆运算的聚合（例如整数求和）可以用双端队列轻松维护，但最小值、分位数、HyperLogLog 近似去重这些没有逆运算的聚合不行，连浮点加法的不可逆性都会让窗口里出现过的 NaN 永久污染结果。于是介绍双栈算法：用两个栈把窗口拆开维护部分聚合，每条元素摊销 O(1) 复杂度。作者说六年前自己为滑动窗口最小值提出过一个算法，现在认为那毫无意义，因为存在这个更简单、适用面更广的做法。
🔑 核心要点
- 有逆运算的聚合可用双端队列维护，但最小值、分位数与 HyperLogLog 这类聚合不行。
- 浮点加法不可逆，窗口里出现过一次 NaN 会让结果永久是 NaN。
- 双栈算法把窗口拆到两个栈上，每个元素摊销 O(1) 复杂度。
- 作者称自己六年前为滑动窗口最小值提出的算法如今已无意义，因为存在更简单且适用更广的做法。
- 该算法出自 Tangwongsan 等人的论文，论文又把它归功于 2011 年 Stack Overflow 上的一个回答。
💡 金句
Six years ago I came up with an algorithm for maintaining just the minimum/maximum in a sliding window... I now consider this algorithm pointless.
👍 0
👎 0
← 返回 Hacker News 首页