C++怎么实现一个水塘抽样算法_C++大数据流随机抽样问题

下次还敢 2025-11-22 00:00:00 次阅读

水塘抽样算法能从未知长度数据流中等概率抽取k个样本。初始化大小为k的数组存储前k个元素，第i个后续元素以k/i概率入池并随机替换旧元素，确保最终每个元素被选概率均为k/N。

水塘抽样（Reservoir Sampling）是一种用于从大量或未知长度的数据流中随机抽取样本的算法。特别适合处理无法一次性加载进内存的大数据流场景。C++实现时，核心是使用一个固定大小的“水塘”数组，并在遍历过程中动态维护样本的均匀性。

基本原理：如何保证等概率

假设要从数据流中随机选取 k 个元素，且每个元素被选中的概率相等。算法的关键在于：当读取到第 n 个元素时（n ≥ k），以 k/n 的概率决定是否将其放入水塘。若放入，则随机替换水塘中的一个已有元素。

这样能确保在整个流程结束后，每个元素出现在最终样本中的概率都是 k/N（N为总数量）。

单样本水塘抽样（k=1）

适用于只需抽取一个元素的场景，空间复杂度 O(1)，时间复杂度 O(n)。

遍历时，对第 i 个元素，以 1/i 的概率保留它作为当前结果。

#include 
#include 

int reservoirSamplingSingle() {
    int reservoir = 0;
    int i = 1;
    int num;

    srand(time(nullptr));

    while (std::cin >> num) { // 假设输入是数据流
        if (rand() % i == 0) {
            reservoir = num;
        }
        ++i;
    }

    return reservoir;
}

多样本水塘抽样（k > 1）

抽取 k 个不同元素，需维护大小为 k 的数组。

前 k 个元素直接存入水塘；从第 k+1 个元素开始，对第 i 个元素，生成 [0, i) 范围内的随机数 j，如果 j

#include 
#include 
#include 
#include 

std::vector reservoirSamplingMultiple(int k) {
    std::vector reservoir(k);
    int num;
    int i = 0;

    srand(time(nullptr));

    // 前 k 个元素直接填入
    while (i < k && std::cin >> num) {
        reservoir[i++] = num;
    }

    // 处理后续元素
    int count = k;
    while (std::cin >> num) {
        ++count;
        int j = rand() % count;
        if (j < k) {
            reservoir[j] = num;
        }
    }

    return reservoir;
}