池中锦鲤的自我修养，聊聊蓄水池算法-EW帮帮网

面试如泡池，蓄水似人生

起初你满怀期待跳进大厂池子，以为自己是天选之子，结果发现池子里早挤满了和你一样的“锦鲤候选人”。HR的渔网一撒，捞谁全看概率——这不就是蓄水池算法的精髓吗？

初入池（i≤k）：前k个幸运儿直接进池，像极了校招提前批的“VIP通道”。
概率博弈（i>k）：第k + 1个候选人开始，以k / i的概率被捞，同时池子里随机一位“前辈”出局。
- “面完三面等消息？恭喜，你进入了k / N的量子纠缠态。”
公平玄学：无论你是第100还是第1000号候选人，最终被捞的概率都是k / N——池子越深，缘分越随机。

所以，下次面试官问你“如何公平抽奖”，请优雅地回答：

“简单，像泡池子一样，先到的不一定稳，后来的未必凉，一切交给蓄水池的数学之美。”

毕竟，泡池子的终极奥义是：
“池中躺平，等一个伯乐；算法加持，信命不认输。”

机器持续吐出编号递增的球（1,2,3…），你有一个容量为k的袋子（k=10），怎么保证机器吐出第N个球时，每个球进入袋子的概率都是k/N？

直接上蓄水池采样规则：

阶段	处理逻辑
前k个球	直接放入袋子（100%保留）
第k+1个球起	对第i个球： - 以k/i概率决定是否保留 - 若保留，随机替换袋中一个球

每个球进入袋子的概率都是k / N的证明：

情况1：前k个球（1 ≤ i ≤ k）的保留概率推导

初始状态：前k个球直接入袋，保留概率为 1。
处理第k+1个球时：
- 第k+1个球入袋的概率为 k/(k+1)；
- 若入袋，随机替换袋中某球的概率为 1/k，即第i号球被淘汰的概率为 (k/(k+1)) × (1/k) = 1/(k+1)；
- 因此，第i号球的保留概率为 1 - 1/(k+1) = k/(k+1)。
处理第k+2个球时：
- 第k+2个球入袋的概率为 k/(k+2)；
- 淘汰第i号球的概率为 (k/(k+2)) × (1/k) = 1/(k+2)；
- 保留概率为 1 - 1/(k+2) = (k+1)/(k+2)。
递推至第N个球：
- 每一步的保留概率依次为 k/(k+1), (k+1)/(k+2), …, (N-1)/N；
- 最终保留概率为各步概率的乘积：
  $\frac{k}{k+1} \times \frac{k+1}{k+2} \times \cdots \times \frac{N-1}{N} = \frac{k}{N}$

情况2：后N-k个球（k < i ≤ N）的保留概率推导

第i号球入袋时：
- 入袋概率为 k/i。
处理第i+1个球时：
- 第i+1个球入袋的概率为 k/(i+1)；
- 淘汰第i号球的概率为 (k/(i+1)) × (1/k) = 1/(i+1)；
- 保留概率为 1 - 1/(i+1) = i/(i+1)。
处理第i+2个球时：
- 保留概率为 (i+1)/(i+2)。
递推至第N个球：
- 每一步的保留概率依次为 i/(i+1), (i+1)/(i+2), …, (N-1)/N；
- 最终保留概率为各步概率的乘积：
  $\frac{k}{i} \times \frac{i}{i+1} \times \frac{i+1}{i+2} \times \cdots \times \frac{N-1}{N} = \frac{k}{N}$

结论
无论球的编号i在哪个区间（1 ≤ i ≤ N），其最终留在蓄水池中的概率均为 k/N，即实现了等概率采样。

C++代码实现（改写左神Java版本）

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

class Pool {
private:
    int size;
    vector<int> bag;

public:
    Pool(int s) : size(s), bag(s) {}

    // 判断是否选择第i号球
    bool pick(int i) {
        return rand() % i < size;
    }

    // 随机选择袋子中的一个位置
    int where() {
        return rand() % size;
    }

    // 处理新进入的球
    void enter(int i) {
        if (i <= size) {
            bag[i - 1] = i;
        } else {
            if (pick(i)) {
                bag[where()] = i;
            }
        }
    }

    // 获取袋子中的球
    vector<int> getBag() {
        return bag;
    }
};

int main() {
    srand(time(NULL)); // 初始化随机数种子
    cout << "测试开始" << endl;
    int n = 41;        // 一共吐出多少球
    int m = 10;        // 袋子大小多少
    int testTimes = 10000; // 进行多少次实验
    vector<int> cnt(n + 1, 0);

    for (int k = 0; k < testTimes; k++) {
        Pool pool(m);
        for (int i = 1; i <= n; i++) {
            pool.enter(i);
        }
        vector<int> bag = pool.getBag();
        for (int num : bag) {
            cnt[num]++;
        }
    }

    cout << "机器吐出到" << n << "号球, " << "袋子大小为" << m << endl;
    cout << "每个球被选中的概率应该接近" << (double)m / n << endl;
    cout << "一共测试" << testTimes << "次" << endl;
    
    for (int i = 1; i <= n; i++) {
        cout << i << "被选中次数 : " << cnt[i] << ", 被选中概率 : " 
             << (double)cnt[i] / testTimes << endl;
    }

    cout << "测试结束" << endl;
    return 0;
}

测试开始
机器吐出到41号球, 袋子大小为10
每个球被选中的概率应该接近0.243902
一共测试10000次
1被选中次数 : 2484, 被选中概率 : 0.2484
2被选中次数 : 2414, 被选中概率 : 0.2414
3被选中次数 : 2445, 被选中概率 : 0.2445
4被选中次数 : 2439, 被选中概率 : 0.2439
5被选中次数 : 2456, 被选中概率 : 0.2456
6被选中次数 : 2434, 被选中概率 : 0.2434
7被选中次数 : 2452, 被选中概率 : 0.2452
8被选中次数 : 2405, 被选中概率 : 0.2405
9被选中次数 : 2385, 被选中概率 : 0.2385
10被选中次数 : 2387, 被选中概率 : 0.2387
11被选中次数 : 2413, 被选中概率 : 0.2413
12被选中次数 : 2463, 被选中概率 : 0.2463
13被选中次数 : 2425, 被选中概率 : 0.2425
14被选中次数 : 2405, 被选中概率 : 0.2405
15被选中次数 : 2463, 被选中概率 : 0.2463
16被选中次数 : 2434, 被选中概率 : 0.2434
17被选中次数 : 2406, 被选中概率 : 0.2406
18被选中次数 : 2456, 被选中概率 : 0.2456
19被选中次数 : 2400, 被选中概率 : 0.24
20被选中次数 : 2467, 被选中概率 : 0.2467
21被选中次数 : 2403, 被选中概率 : 0.2403
22被选中次数 : 2415, 被选中概率 : 0.2415
23被选中次数 : 2432, 被选中概率 : 0.2432
24被选中次数 : 2438, 被选中概率 : 0.2438
25被选中次数 : 2464, 被选中概率 : 0.2464
26被选中次数 : 2514, 被选中概率 : 0.2514
27被选中次数 : 2416, 被选中概率 : 0.2416
28被选中次数 : 2546, 被选中概率 : 0.2546
29被选中次数 : 2440, 被选中概率 : 0.244
30被选中次数 : 2350, 被选中概率 : 0.235
31被选中次数 : 2398, 被选中概率 : 0.2398
32被选中次数 : 2483, 被选中概率 : 0.2483
33被选中次数 : 2405, 被选中概率 : 0.2405
34被选中次数 : 2472, 被选中概率 : 0.2472
35被选中次数 : 2449, 被选中概率 : 0.2449
36被选中次数 : 2431, 被选中概率 : 0.2431
37被选中次数 : 2494, 被选中概率 : 0.2494
38被选中次数 : 2515, 被选中概率 : 0.2515
39被选中次数 : 2507, 被选中概率 : 0.2507
40被选中次数 : 2384, 被选中概率 : 0.2384
41被选中次数 : 2411, 被选中概率 : 0.2411
测试结束

设计抽奖系统，在参与某厂招聘会的学生中，抽取100人送offer

等概率抽取100人，且学生不能重复报名（去重）。维护一个大小为100的蓄水池，只需要判断学生是否首次报名，并确定是第几个参与者即可。第i个首次报名的学生，以100 / i概率决定是否入池，若入选则随机替换池中一人。

✅ 单服务器轻量级维护
✅ 规避多节点数据汇总
✅ 实时性高，无最终计算延迟

蓄水池采样核心

在数据流持续输入且总量未知的情况下，用固定容量的容器维护一个等概率样本集。

典型场景及变种

判断条件：
- 数据流式输入且总量未知；
- 需要等概率采样固定数量样本。
变种处理：
- 动态容量：将固定k改为动态k(i)，概率调整为k(i)/i；
- 分布式：先本地采样再合并二次采样，利用分治保证概率正确性。

日志采样：分布式系统中按1/1000比例抽样百万级日志，保留统计特征；
推荐系统冷启动：维护固定大小的历史交互样本，保证新物品等概率曝光；
实时弹幕过滤：从千万级弹幕中实时抽取固定数量展示；

为什么 MapReduce中要用蓄水池采样？

MapReduce 是一种处理海量数据的编程模型，核心思想是 “分而治之”，就像一群人分工合作完成大任务。

MapReduce 处理的往往是 TB 级甚至 PB 级数据（比如日志、用户行为数据），直接全量采样或分析不现实：
- 全量存储消耗大量内存和磁盘；
- 直接处理所有数据会拖慢计算速度。
- 蓄水池采样能用固定大小的样本（比如 1000 条数据）代表整体特征，大幅减少计算量。
如果采样不均匀（比如总选前 10% 的数据），样本就会失真，无法反映整体特征。
- 蓄水池采样能确保每个数据被选中的概率相等。
- 即使数据是动态流入的（不知道总量 N），也能保证等概率，这对 MapReduce 处理实时或未知总量的数据很关键。
MapReduce 的分布式架构适配蓄水池采样
- Map 阶段：每个节点独立对本地数据做蓄水池采样（比如每个节点存 m 条样本），避免传输全量数据，减少网络开销；
- Reduce 阶段：合并所有节点的样本（总共有 M = 节点数 × m 条），再用蓄水池采样取 m 条作为最终样本，保证全局等概率。

如何等概率采样1个元素，但数据量极大且只能遍历一次？

蓄水池采样的k=1特例，对第i个元素以1/i概率替换当前选中元素。

若数据以链表形式存储，如何高效实现蓄水池采样？

遍历链表时，对第i个节点（i从1开始）用k/i概率决定是否加入蓄水池，维护大小为k的数组，替换时随机选位置，时间复杂度O(n)，空间O(m)。

带权重的蓄水池采样如何实现？

选中概率改为权重之和的比例，元素i权重为w_i，第i步选中概率为w_i/(w₁+w₂+…+w_i)，替换时按权重随机选择对象。

（注：算法公平，但offer未必，建议多投几个池子。）

参考

[1] 程序员代码面试指南
 [2] 算法讲解107【扩展】大厂面试中经常漫聊的有趣算法问题

池中锦鲤的自我修养，聊聊蓄水池算法