蓄水池算法适合流式数据抽样，因为它只需单次遍历、空间复杂度o(k)、时间复杂度o(n)，且每个元素被选概率严格为k/n；无需预知数据总量，不依赖随机访问，适配单向迭代器如istream_iterator。
蓄水池算法为什么适合流式数据抽样
当你面对的是无法一次性加载到内存的超大数组（比如从磁盘逐块读取、网络流、或长度未知的迭代器），std::random_shuffle 或先打乱再取前 k 个的方式就失效了——它们要求完整访问所有元素。蓄水池算法（Reservoir Sampling）正是为这种场景设计的：只需遍历一次，空间复杂度固定为 O(k)，时间复杂度 O(n)，且每个元素被选中的概率严格为 k/n。
它不依赖数组总长度预先可知，也不需要额外存储整个数据集，特别适合 C++ 中处理 std::istream_iterator、文件行流、传感器采样序列等真实流式场景。
标准蓄水池算法的 C++ 实现要点
核心逻辑分两步：前 k 个元素直接入池；从第 k+1 个开始，对每个元素 i（索引从 0 开始，即第 i+1 个），以概率 k/(i+1) 决定是否替换池中某个随机位置。
- 必须用
std::mt19937配合std::uniform_int_distribution，避免rand()的低质量与线程不安全 - 替换时，生成
[0, k)范围内的随机索引，不是[0, i]—— 否则会破坏均匀性 - 若输入迭代器是单向的（如
std::istream_iterator），无法回退，必须边读边决策，不能事后修正 - 示例片段（抽取
k=3个）：
std::vector<int> reservoir(k);
std::mt19937 gen{std::random_device{}()};
std::uniform_int_distribution<int> dist;
// 前 k 个直接填入
for (int i = 0; i (0, i); // 注意：范围是 [0, i]，对应第 i+1 个元素
if (dist(gen)
<h3>常见错误：用错随机范围导致偏差</h3>
<p>最容易踩的坑是混淆“当前元素序号”和“索引下标”。比如把第 <code>i</code> 个元素（从 0 开始计数）的概率写成 <code>k/i</code>，或替换索引生成范围设为 <code>[0, i)</code>，都会让靠后的元素被选中概率偏高。</p>
<p>正确做法始终基于“这是第几个元素”来算概率：第 1 个元素（<code>i=0</code>）必须入选；第 <code>m</code> 个元素（<code>m</code> 从 1 开始计）被选中概率是 <code>k/m</code>；替换位置必须在 <code>[0, k)</code> 内均匀选取。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master"><img
src="https://img.php.cn/upload/skill/000/000/081/179051228971575.jpg" alt="C++ Code Review Master" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="overflowclass">C++ Code Review Master</a>
<p class="overflowclass">组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。</p>
</div>
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<ul>
<li>错误：<code>std::uniform_int_distribution<int>(0, i-1)</int></code>（当 <code>i</code> 是从 0 开始的下标）→ 实际对应第 <code>i+1</code> 个元素，但分布上限写成 <code>i-1</code> 少了 1</li>
<li>错误：<code>rand() % k</code> 直接替换 → 没有保证第 <code>m</code> 个元素整体入选概率为 <code>k/m</code>
</li>
<li>正确：对第 <code>m</code> 个元素（<code>m = i+1</code>），用 <code>dist(gen) 判断是否入选，再用独立的 <code>[0,k)</code> 分布选位置</code>
</li>
</ul>
<h3>当 k=1 时可以简化，但别误用 std::sample</h3>
<p>C++17 引入了 <code>std::sample</code>，但它要求输入迭代器是 RandomAccessIterator，且必须知道总长度（通过 <code>std::distance</code>），本质是先随机选 <code>k</code> 个下标再取值——不适用于流式或长度未知场景。</p>
<p><code>k=1</code> 时蓄水池退化为“只记录当前最优候选”，代码更轻量：</p>
<pre class="brush:php;toolbar:false;">
T result;
int count = 0;
for (const auto& x : range) {
++count;
if (std::bernoulli_distribution(1.0/count)(gen)) {
result = x;
}
}
注意：std::bernoulli_distribution 比手动比较更清晰，但底层仍是 uniform_real_distribution，别为了省一行代码改用浮点误差敏感的除法。
真正难的不是写对算法，而是确认你的数据源是否真的“不可预知长度”——如果只是普通 std::vector，直接用 std::shuffle + vector::begin() 截取更高效；只有当迭代器是 input_iterator、或内存受限时，蓄水池才不可替代。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
