C++如何实现高效的数组元素随机抽样 (蓄水池采样算法)-C++-PHP中文网

c++oding="utf-8" ?>

蓄水池采样适用于无法预知数据长度且仅能单次遍历的场景，如流式数据、文件逐行读取或前向迭代器；其空间复杂度o(k)、时间复杂度o(n)，std::sample在非随机访问迭代器下自动退化为该策略。

c++如何实现高效的数组元素随机抽样 (蓄水池采样算法)

蓄水池采样适合什么场景

当你无法预知数组长度（比如数据来自流、文件逐行读取、或迭代器只允许单次遍历），又需要等概率随机抽取 k 个元素时，std::random_shuffle 或先转 std::vector 再用 std::sample 就不适用了。蓄水池采样（Reservoir Sampling）正是为此设计：空间复杂度 O(k)，时间复杂度 O(n)，且只需遍历一次。

标准库已有实现但要注意版本

C++17 引入了 std::sample，它底层可使用蓄水池逻辑（标准未强制实现方式，但主流 STL 实现如 libstdc++ 和 libc++ 对输入迭代器类型会自动退化为蓄水池策略）。关键看你的迭代器是否满足 RandomAccessIterator：

如果是 std::vector::iterator（支持随机访问），std::sample 可能用更高效的洗牌+截断，不是严格蓄水池
如果是 std::istream_iterator、std::forward_list::iterator 等仅前向迭代器，std::sample 必须用蓄水池逻辑，且行为符合算法要求

示例（安全用于任意流）：

#include <algorithm>
#include <vector>
#include <iterator>
#include <random>

std::vector<int> reservoir(k);
std::sample(istream_iter, std::istream_iterator<int>{},
            reservoir.begin(), reservoir.end(),
            std::mt19937{std::random_device{}()});
</int></int></random></iterator></vector></algorithm>

手写蓄水池要避开的三个坑

自己实现时常见错误集中在边界、随机数范围和状态更新上：

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

第 i 个元素（从 0 开始计数）被选中的概率必须是 k / (i + 1)，不是 k / i（i=0 会除零）
生成随机索引时，要用 std::uniform_int_distribution<int>(0, i)</int>，而非 (0, i-1) —— 否则第 i 个元素永远没机会替换自己
替换操作必须在判定“是否入选”后立即完成，不能延迟到循环外；否则当 i 时，应无条件填满蓄水池，而不是跳过

正确片段（k=1 简化版）：

int sample = 0;
int count = 0;
for (int x : data_stream) {
    if (++count == 1) sample = x;
    else {
        std::uniform_int_distribution<int> dist(1, count);
        if (dist(gen) == count) sample = x;
    }
}
</int>