水塘抽样算法能从未知长度数据流中等概率抽取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 <cstdlib>
#include <ctime>
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 <vector>
#include <iostream>
#include <cstdlib>
#include <ctime>
std::vector<int> reservoirSamplingMultiple(int k) {
std::vector<int> 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 库更佳）
- 对于重复调用场景，避免频繁重置随机种子
- 若需更高精度随机性，推荐使用 <random> 头文件中的分布类
- 数据流可以是文件、网络包、传感器输入等任意顺序源
- 算法不要求知道总长度，适合实时处理
