第10章 流式算法：数据流动时的算法思维
核心问题：当数据永不停止流动时，算法设计的前提发生了什么变化？
章节概述
你写过一个完美的统计程序——O(n)时间复杂度，优雅简洁。但当数据变成了持续流动的无限流时，程序彻底失效了。
发生了什么？
静态算法的前提在流式环境下失效了：
- 数据永不停止 → 没有"完成"的概念
- 只能看一遍 → 无法回头重新扫描
- 内存远小于数据量 → 无法存储所有数据
- 必须实时响应 → 数据还在流动就要给出答案
本章将带你理解：当"约束变了，算法也变"时，如何重新设计流式算法。
三个看似简单的问题
问题1：实时热搜榜
统计过去1小时内最热门的100个搜索词。
静态思路：收集1小时数据 → O(n) 排序 → 取Top100
流式困境：
- 数据每秒10万次搜索请求
- 搜索词种类超过1000万种
- 哪个时刻算"数据完成"？每小时重算？
- 存储1000万种词的频率，内存爆炸
困惑：O(n) 在静态数据上简单，为什么流式数据上变成"不可能精确"？
问题2：网站独立访客数
统计过去24小时内有多少独立用户访问网站。
静态思路：HashSet去重 → O(n) 时间，O(n) 空间
流式困境：
- 24小时有10亿次访问
- HashSet需要存储10亿个用户ID ≈ 100GB内存
- 内存不够怎么办？
- 数据还在流动，什么时候统计？
困惑：精确统计需要存所有数据，内存不够怎么办？
问题3：异常流量检测
实时检测网络流量中的异常峰值。
静态思路：收集完整数据 → 计算统计量 → 检测异常
流式困境：
- 数据在流动，没有"完整数据"
- 异常可能在数据流动中发生
- 检测必须实时，不能等数据"完成"
- 每个数据包只能看一遍
困惑：如何在数据还在流动时就做出决策？
核心叙事：前提变了，算法也变
第1-9章默认的前提是：数据是静态的，我们可以多次扫描，可以存储所有数据，可以在"完成"后给出答案。
流式环境把这个前提打碎：
- 数据永不停止，没有"完成"的概念
- 每个元素只能看一遍，无法回头
- 内存远小于数据量，无法存储全部
- 必须在数据流动时实时响应
约束变化的影响：
| 静态前提 | 流式现实 | 算法需要改变 |
|---|---|---|
| 数据完整可得 | 数据流过即消失 | 只能单遍扫描 |
| 内存足够存所有数据 | 内存远小于数据量 | 必须用近似方法 |
| 可以多次扫描 | 只能看一遍 | 无法回头 |
| 可以等待"完成" | 数据永不停止 | 必须实时响应 |
| 可以给出精确答案 | 精确解空间不够 | 接受近似答案 |
关键洞察：流式算法的核心问题是"如何在约束变化下重新设计算法"——从"精确计算"到"近似估计"，从"全量存储"到"摘要结构"，从"事后分析"到"实时决策"。
与Ch9分布式算法的关系
Ch9讨论了数据分布到多台机器的情况，Ch10讨论数据持续流动的情况：
| 维度 | Ch9 分布式 | Ch10 流式 |
|---|---|---|
| 核心约束 | 数据分布多机器 | 数据单遍流过 |
| 成本瓶颈 | 通信成本 | 内存空间 |
| 设计目标 | 可用性 | 近似性 |
| 精度 | 通常精确 | 通常近似 |
两种约束可能同时存在：数据既分布在多机，又持续流动。本章聚焦单机的空间约束。
本章导航
| 节 | 标题 | 核心问题 | 核心工具 |
|---|---|---|---|
| 10.1 | 流式成本模型 | O(n)的静态算法，流式下为何"不可能精确"？ | 近似保证 |
| 10.2 | 滑动窗口 | 内存有限时如何处理无限数据？ | 滑动窗口、指数衰减 |
| 10.3 | 频率估计 | 如何用少量内存估计频率？ | Count-Min Sketch |
| 10.4 | 去重计数 | 如何用少量内存估计基数？ | HyperLogLog |
| 10.5 | 流式聚合 | 数据流动时如何做决策？ | 竞争比分析 |
| 10.6 | LLM流式视角 | LLM时代的流式挑战？ | 上下文窗口 |
| 10.7 | 综合练习 | 如何审查LLM的流式方案？ | 综合应用 |
学习目标
完成本章学习后，你将能够：
- 理解流式成本模型：从"精确解"到"近似解"的视角转变
- 掌握滑动窗口技术：在有限窗口内维护统计量
- 设计频率估计方案：用Count-Min Sketch处理海量数据
- 设计去重计数方案：用HyperLogLog估计基数
- 分析在线决策问题：理解秘书问题的竞争比
- 审查流式方案：识别LLM给出的"功能正确但空间爆炸"的方案
核心概念预告
本章将学习四大核心工具：
| 概念 | 功能 | 空间复杂度 | 精度保证 |
|---|---|---|---|
| 滑动窗口 | 有限窗口统计 | O(window_size) | 确或近似 |
| Count-Min Sketch | 频率估计 | O(1/ε · log(1/δ)) | 高估，误差 ≤ εN |
| HyperLogLog | 基数估计 | O(log log n) | 标准误差 ≈ 1.04/√m |
| 竞争比分析 | 在线决策质量 | - | 比值保证 |
与其他章节的联系
前置知识
- Ch2 数据结构：哈希表、堆 → Count-Min Sketch、Top-K
- Ch4 概率与随机化：概率分析 → 误差概率分析
- Ch8 NP完全：近似算法 → 近似保证
- Ch9 分布式算法：分布式约束 → 与流式约束对比
后续铺垫
- Ch11 Transformer：上下文窗口 → 流式生成
- Ch12 设计方法论：约束分析 → Agent设计案例
War Story预告
本章包含三个真实的工程教训：
- 热搜榜系统的教训：精确统计需要存储所有数据，用摘要结构换空间
- UV统计的教训：HyperLogLog用12KB内存统计10亿用户
- 流式生成的教训：LLM的上下文窗口就是流式约束
开始阅读
准备好探索流式世界的挑战了吗？
让我们从第一个问题开始：10.1 流式成本模型