抽样算法
Reservoir Sampling
📌 概念释义与技术定位 (Definition & Overview)
Reservoir Sampling 是一种在内存受限环境下，对未知长度数据流进行无偏随机抽样的核心算法，能在单次遍历中高效维护固定大小的代表性样本集。
Reservoir Sampling（水库抽样）是由 J. A. Fisher 于 1973 年提出的一种经典概率算法，专门解决在无法预知数据流总长度（N）且内存不足以存储全部数据时，如何从数据流中抽取 n 个无偏随机样本的问题。其核心数学逻辑在于动态调整每个元素被选入样本池的概率，确保无论数据流何时结束，最终样本集中每个元素出现的概率均为 n/N，从而在流式计算场景下实现了统计意义上的公平性与代表性。
在现代大数据架构中，Reservoir Sampling 扮演着流式处理与内存优化之间的关键桥梁角色。面对 Hadoop、Spark Streaming 或 Kafka 等海量数据流，传统的全量加载方案往往受限于内存瓶颈，而该算法仅需 O(n) 的额外空间即可处理无限长数据流。它不仅广泛应用于日志分析、实时推荐系统、网络流量监控及 A/B 测试等场景，更是构建高效流批一体计算引擎的基础组件之一，有效解决了‘只读一次’（Single Pass）场景下的采样难题。
⚙️ 核心架构与工作机制 (Technical Mechanism)
该算法的核心机制在于维护一个大小为 n 的‘水库’（数组）和一个计数器 i。当处理到第 i 个元素时（i 从 1 开始计数），算法首先判断 i 是否大于 n：若 i <= n，则直接将元素存入水库；若 i > n，则以概率 n/i 决定是否将当前元素替换水库中的随机一个元素。这种动态概率机制确保了在数据流结束前，任何时刻水库内的样本都是无偏的；而在数据流完全结束后，数学推导证明每个元素最终留在水库中的概率严格等于 n/N。其时间复杂度为 O(1) 每元素，空间复杂度为 O(n)，完美契合流式计算的实时性要求。
📖 权威专著深度引证与原文精粹 (Expert Book Insights)
1 本专著引用《labuladong的算法小抄 官方完整版》
labuladong
“466 如何在⽆限序列中随机抽取元素 随机算法之⽔塘抽样算法 学算法，认准 labuladong 就够了！ 我最近在 LeetCode 上做到两道⾮常有意思的题⽬，382 和 398 题，关于⽔ 塘抽样算法（Reservoir Sampling），本质上是⼀种随机概率算法，解法应该 说会者不难，难者不会。”
🚀 典型应用场景 (Industrial Applications)
实时日志分析与异常检测
大规模数据集的无偏随机采样
网络流量与用户行为流监控
流式 A/B 测试与在线实验
⚖️ 技术优势与工程权衡 (Trade-offs & Pros/Cons)
🟢 核心优势与技术特性
- + 仅需单次遍历数据流，无需预知总长度
- + 空间复杂度恒定，仅依赖样本大小 n
- + 保证样本的无偏性（Unbiasedness）
- + 实现简单，易于并行化扩展
🔴 工程考量与潜在挑战
- - 无法在数据流结束前确定最终样本集
- - 若样本量 n 过大，内存占用仍可能成为瓶颈
- - 不支持对已采样数据进行回溯或重新采样
- - 在数据流存在明显重复或高基数时效率受限
