蓄水池算法适合流式数据抽样，因为它能在单次遍历中以等概率选出k个样本，空间复杂度o(k)、时间复杂度o(n)，不依赖数据总长度，且适用于无法预知长度或内存受限的场景。

蓄水池算法为什么适合流式数据抽样

当你面对的是无法预知长度的输入流（比如从文件逐行读取、网络实时数据），或者数组大到不能一次性加载进内存时，std::random_shuffle或先打乱再取前k个的做法就失效了。蓄水池算法（Reservoir Sampling）能在单次遍历中以等概率选出k个样本，空间复杂度稳定为O(k)，时间O(n)，且不依赖数组总长度。

它核心逻辑简单：前k个元素直接入池；之后每遇到第i个元素（i > k），以k/i的概率决定是否用它替换池中某个随机位置的元素。这个概率设计保证了最终每个元素被选中的概率都是k/n。

标准蓄水池抽样的C++实现要点

标准版本（k=1可简化，但通用写法更易复用）需注意三个关键点：随机数生成器选择、边界处理、避免整数溢出。

• std::random_device和std::mt19937组合比rand()更可靠，尤其在多线程或重复调用场景下
• 循环索引从0开始还是1开始？推荐用1-based计数（即第1个元素对应i=1），这样替换概率公式k/i更直观，也避免i=0除零风险
• 当n很大时，i可能接近INT_MAX，但k/i是浮点概率——实际应使用std::uniform_int_distribution<int>(1, i)</int>生成[1,i]随机数，若≤k则替换，避免浮点精度和除法开销

示例片段（抽取k个索引，适用于任意容器）：

std::vector<size_t> reservoir_sample(const std::vector<int>& arr, size_t k) {
    if (k == 0 || arr.empty()) return {};
    if (k >= arr.size()) {
        std::vector<size_t> all(arr.size());
        std::iota(all.begin(), all.end(), 0);
        return all;
    }
    std::vector<size_t> res(k);
    std::random_device rd;
    std::mt19937 gen(rd());
    // 前k个直接填入
    for (size_t i = 0; i  dist(0, i);
        if (dist(gen) 
<p>⚠️ 注意上面代码里有个典型错误：连续两次调用<code>dist(gen)</code>会破坏均匀性。正确做法是只生成一次随机数，再分别用于判断和选位置：</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架"><img
														src="https://img.php.cn/upload/skill/000/000/081/178988956499722.jpg" alt="C++ 算法竞赛自动化测试数据生成与校验框架" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="overflowclass">C++ 算法竞赛自动化测试数据生成与校验框架</a>
													<p class="overflowclass">根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。</p>
												</div>
												<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>
<pre class="brush:php;toolbar:false;">
for (size_t i = k; i  dist(0, i);
    size_t r = dist(gen);  // 一次生成
    if (r 

<h3>如何安全获取抽样后的实际值而非索引</h3>
<p>直接返回索引比返回值更灵活：用户可自行映射到原数组、迭代器或自定义结构体。但如果必须返回值副本，要注意深拷贝成本。</p>

• 对POD类型（如int、double），用std::vector<t></t>存值没问题
• 对大对象（如std::string、自定义类），建议返回std::vector<const t></const>或std::vector<:reference_wrapper t>></:reference_wrapper>避免复制
• 若源容器是临时的或生命周期短于结果，必须深拷贝——此时抽样本身不是瓶颈，内存分配才是

例如安全获取值的简化版（仅适用于小对象）：

std::vector<int> get_sample_values(const std::vector<int>& arr, size_t k) {
    auto indices = reservoir_sample(arr, k);
    std::vector<int> values;
    values.reserve(k);
    for (auto idx : indices) {
        values.push_back(arr[idx]);
    }
    return values;
}
</int></int></int>

性能陷阱：别在循环内反复构造分布对象

std::uniform_int_distribution构造开销虽小，但在外层循环（尤其是n极大时）反复创建仍会拖慢速度。正确做法是将分布对象提到循环外，复用同一个实例。

• 分布对象是轻量级的，状态只保存参数，不记录随机数序列
• 不同范围的分布必须单独声明，不能用一个对象覆盖多个min/max
• 对于固定k和动态i，[0,i]范围每次变，所以必须在循环内重置参数——但可通过dist.param(...)避免重建对象

优化后写法：

std::vector<size_t> reservoir_sample(const std::vector<int>& arr, size_t k) {
    // ... 初始化部分同上
    std::uniform_int_distribution<size_t> dist;
    for (size_t i = k; i ::param_type(0, i));
        size_t r = dist(gen);
        if (r 
<p>真正容易被忽略的是：当k=1时，蓄水池退化为“始终保留当前最优随机候选”，此时连数组都不用存，只需一个变量和一次比较——但很多人仍套用通用模板，白白多开O(k)空间和分支判断。</p></size_t></int></size_t>

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！