水塘抽样算法能从未知长度数据流中等概率抽取k个样本。初始化大小为k的数组存储前k个元素，第i个后续元素以k/i概率入池并随机替换旧元素，确保最终每个元素被选概率均为k/N。
水塘抽样（Reservoir Sampling）是一种用于从大量或未知长度的数据流中随机抽取样本的算法。特别适合处理无法一次性加载进内存的大数据流场景。C++实现时，核心是使用一个固定大小的“水塘”数组，并在遍历过程中动态维护样本的均匀性。
基本原理：如何保证等概率
假设要从数据流中随机选取 k 个元素，且每个元素被选中的概率相等。算法的关键在于：当读取到第 n 个元素时（n ≥ k），以 k/n 的概率决定是否将其放入水塘。若放入，则随机替换水塘中的一个已有元素。
这样能确保在整个流程结束后，每个元素出现在最终样本中的概率都是 k/N（N为总数量）。
单样本水塘抽样（k=1）
适用于只需抽取一个元素的场景，空间复杂度 O(1)，时间复杂度 O(n)。遍历时，对第 i 个元素，以 1/i 的概率保留它作为当前结果。
立即学习“C++免费学习笔记（深入）”；
#include#include int reservoirSamplingSingle() { int reservoir = 0; int i = 1; int num; srand(time(nullptr)); while (std::cin >> num) { // 假设输入是数据流 if (rand() % i == 0) { reservoir = num; } ++i; } return reservoir; }
多样本水塘抽样（k > 1）
抽取 k 个不同元素，需维护大小为 k 的数组。前 k 个元素直接存入水塘；从第 k+1 个元素开始，对第 i 个元素，生成 [0, i) 范围内的随机数 j，如果 j
#include#include #include #include std::vector reservoirSamplingMultiple(int k) { std::vector reservoir(k); int num; int i = 0; srand(time(nullptr)); // 前 k 个元素直接填入 while (i < k && std::cin >> num) { reservoir[i++] = num; } // 处理后续元素 int count = k; while (std::cin >> num) { ++count; int j = rand() % count; if (j < k) { reservoir[j] = num; } } return reservoir; }
使用建议与注意事项
实际应用中注意以下几点：
- 确保随机数生成器已正确初始化（如使用 srand 或 C++11 的 random 库更佳）
- 对于重复调用场景，避免频繁重置随机种子
- 若需更高精度随机性，推荐使用
头文件中的分布类 - 数据流可以是文件、网络包、传感器输入等任意顺序源
- 算法不要求知道总长度，适合实时处理
