#优质博文 #算法 #数据采样 #course
好棒的交互式教程，务必看看原文。（看了这篇打 ACM 的回忆涌了上来呜呜呜）
Reservoir Sampling

AI 摘要：本文详细介绍了蓄水池采样（Reservoir Sampling）这一算法技术，用于在未知数据集大小的情况下公平地随机选择样本。文章通过直观的例子（如抽牌和日志收集）以及逐步推导，解释了蓄水池采样的应用场景、数学原理和实现方法，强调其在处理大规模数据流时的内存效率和公平性。

1. 引言与背景：
• 介绍了蓄水池采样的核心概念，即在不知道数据集大小的情况下，如何公平地随机选择样本。
• 目标：让读者了解何时需要使用蓄水池采样、其背后的数学原理（仅用基本运算：减法、乘法和除法）以及简单的实现方法。
2. 已知大小的采样：
• 通过抽取10张牌中的3张为例，说明传统随机采样的方法（如洗牌或随机索引）。
• 指出当数据量巨大（如百万张牌）时，传统方法变得不切实际，尤其是当数据以流式方式逐个呈现且无法存储所有数据时。
• 提出了一个难题：如果每次只能看到一张牌且只能持有一张，如何公平地选择？
3. 未知大小的采样：
• 引入了蓄水池采样的应用场景，如日志收集服务中处理日志峰值时需要采样。
• 描述了问题：数据流中日志数量未知，无法存储所有日志，需在内存受限的情况下公平选择部分日志。
• 通过模拟日志流，展示了简单采样（如仅取前几个）的不公平性，强调需要一种公平的算法。
4. 蓄水池采样原理（单项选择）：
• 详细解释了蓄水池采样的核心思想：对于第n个元素，以1/n的概率替换当前持有的元素。
• 通过逐步计算概率，证明了该方法确保每个元素被选中的概率相等（公平性）。
• 举例分析了前几张牌的选中概率，确保读者理解数学推导（例如，第1张牌选中概率为100%，第2张为50%，第3张为33.33%）。
5. 扩展到多项选择：
• 介绍了如何从数据流中选择k个元素：新元素以k/n的概率被选中，并随机替换当前持有的k个元素中的一个。
• 提供了实现方法：使用大小为k的数组，生成0到n的随机数，若小于k则替换对应位置的元素。
• 通过公式和实例，验证了多项选择的公平性。
6. 应用于日志收集：
• 将蓄水池采样应用于日志收集场景，设置k=5，每秒发送最多5条日志。
• 展示了该方法的优势：在安静时段不丢失日志，在高峰时段限制发送量，且内存使用可控。
• 指出了一个权衡：日志发送不再是实时流，而是按时间间隔批量发送。
7. 进阶阅读与加权采样：
• 提到蓄水池采样的加权变体，适用于某些日志（如错误日志）更重要的情况。
• 提供了相关资源链接（Wikipedia），供有兴趣的读者深入研究。

author Sam Rose