水塘抽样适用于流式数据且空间受限场景，仅需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 dist;
for (int i = k; i ::param_type(0, i)); // [0, i]
int j = dist(gen);
if (j
<h3>用 C++20 ranges + views 实现流式接口要注意什么</h3>
<p>如果封装成接受 <code>std::ranges::input_range</code> 的函数，必须确保底层迭代器是单次遍历的（如 <code>std::istream_iterator</code>），且不能反复调用 <code>begin()</code>。水塘抽样本身不支持 rewind，任何试图“重放流”的尝试都会破坏算法前提。</p>
<ul>
<li>不要对 <code>std::cin</code> 或文件流对象多次调用该函数 —— 第二次时流已到末尾</li>
<li>若需多次采样，必须重建流对象或缓存原始数据（那就不再属于纯流式场景）</li>
<li>
<code>std::views::take</code> 和 <code>std::views::drop</code> 可用于构造子流，但不能改变水塘抽样所需的全局顺序保证</li>
</ul>
<h3>多个样本同时抽取时，<code>k</code> 接近数据量会怎样</h3>
<p>当 <code>k</code> 很大（例如占预估总量 30% 以上），虽然算法逻辑仍正确，但实际性能会劣化：每次新元素都有高概率触发替换，导致 <code>reservoir</code> 频繁写入。更严重的是，若误将 <code>k</code> 设得比真实数据总量还大，前 <code>k</code> 步填充会越界访问。</p>
<ul>
<li>务必在填充阶段加 <code>i 边界检查，尤其当 <code>n</code> 是运行时才确定的（如逐行读文件直到 EOF）</code>
</li>
<li>没有“提前知道总长”时，<code>k</code> 应显著小于预期数据规模，否则空间优势消失，且随机性在尾部数据不足时会倾斜</li>
<li>真正的大规模流式采样（如 <code>k=1000</code>，数据亿级），建议用分层水塘或带权重变种，基础版只适合 <code>k</code> 在百级别稳定场景</li>
</ul>
<p>最常被忽略的一点：算法假设输入流中每个元素独立同分布，如果流本身有周期性或隐藏模式（比如按用户 ID 分块写入），即使数学上等概率，实际采样结果也可能系统性偏离——这时候得先打乱流结构，而不是换抽样算法。</p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
