水塘抽样适用于流式数据且空间受限场景，仅需O(k)空间和单次遍历，不依赖数据总长度；误用于已知长度数组会增加冗余开销；标准算法中随机数范围应为[0,i)，而非闭区间。
水塘抽样适用于流式数据且空间受限的场景
当数据无法全部载入内存（比如日志流、网络包序列、超大文件逐行读取），又需要等概率随机采样 k 个元素时，Reservoir Sampling 是唯一可行的标准解法。它不依赖数据总长度，只用 O(k) 空间和单次遍历 —— 这是它不可替代的核心价值。
常见误用是拿它去处理已知长度的数组：此时直接 std::shuffle 或随机索引更简单高效，强行套水塘抽样反而多出不必要的判断和交换开销。
标准算法第 R 行怎么写才不出错
最易错的是索引边界和随机数范围。C++ 中 std::uniform_int_distribution 默认闭区间，而算法要求“前 i 个元素中以 k/i 概率选中第 i 个”，对应随机数应落在 [0, i) 范围内，再与 k 比较。
- 错误写法：
dist(gen) (i)—— 浮点除法引入精度误差，且分布不均 - 正确写法：用整数比较，生成
[0, i)的随机整数，判断是否 k - 注意
i从 1 开始计数（第 1 个元素下标为 0，但概率是k/1）
std::vector<int> reservoir(k);
// 填充前 k 个
for (int i = 0; i < k && i < n; ++i) {
reservoir[i] = data[i];
}
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<int> dist;
for (int i = k; i < n; ++i) {
dist.param(std::uniform_int_distribution<int>::param_type(0, i)); // [0, i]
int j = dist(gen);
if (j < k) {
reservoir[j] = data[i];
}
}
用 C++20 ranges + views 实现流式接口要注意什么
如果封装成接受 std::ranges::input_range 的函数，必须确保底层迭代器是单次遍历的（如 std::istream_iterator），且不能反复调用 begin()。水塘抽样本身不支持 rewind，任何试图“重放流”的尝试都会破坏算法前提。
立即学习“C++免费学习笔记（深入）”；
- 不要对
std::cin或文件流对象多次调用该函数 —— 第二次时流已到末尾 - 若需多次采样，必须重建流对象或缓存原始数据（那就不再属于纯流式场景）
-
std::views::take和std::views::drop可用于构造子流，但不能改变水塘抽样所需的全局顺序保证
多个样本同时抽取时，k 接近数据量会怎样
当 k 很大（例如占预估总量 30% 以上），虽然算法逻辑仍正确，但实际性能会劣化：每次新元素都有高概率触发替换，导致 reservoir 频繁写入。更严重的是，若误将 k 设得比真实数据总量还大，前 k 步填充会越界访问。
- 务必在填充阶段加
i 边界检查，尤其当 <code>n是运行时才确定的（如逐行读文件直到 EOF） - 没有“提前知道总长”时，
k应显著小于预期数据规模，否则空间优势消失，且随机性在尾部数据不足时会倾斜 - 真正的大规模流式采样（如
k=1000，数据亿级），建议用分层水塘或带权重变种，基础版只适合k在百级别稳定场景
最常被忽略的一点：算法假设输入流中每个元素独立同分布，如果流本身有周期性或隐藏模式（比如按用户 ID 分块写入），即使数学上等概率，实际采样结果也可能系统性偏离——这时候得先打乱流结构，而不是换抽样算法。
