蓄水池抽样算法可公平地从未知大小的数据流中随机选取k个样本，每个元素被选中的概率均为k/n。首先将前k个元素存入蓄水池，随后对第i个元素（i>k），以k/i的概率决定是否将其加入，并随机替换池中一个元素。C++实现时推荐使用<random>库提升随机性质量，适用于内存受限或实时数据流场景，空间复杂度O(k)，时间复杂度O(n)。
在处理未知大小的数据流时，如果需要从中随机抽取 k 个样本，并保证每个元素被选中的概率相等，可以使用蓄水池抽样算法（Reservoir Sampling）。C++ 实现这个算法非常高效且简洁，尤其适合大数据流或内存受限的场景。
蓄水池抽样算法原理
假设数据流总共有 n 个元素（n 未知），我们要从中随机选取 k 个元素，使得每个元素被选中的概率都是 k/n。
算法步骤如下：
- 先将前 k 个元素放入“蓄水池”（比如一个数组或 vector）。
- 从第 k+1 个元素开始，对每个元素进行判断：以一定概率决定是否将其放入蓄水池，并随机替换掉池中一个已有元素。
- 具体地，处理第 i 个元素时（i > k），它被选中的概率是 k/i，然后从蓄水池中随机选择一个位置替换。
C++ 实现代码示例
// 蓄水池抽样：从数据流中随机选取 k 个元素 #include <vector> #include <iostream> #include <cstdlib> #include <ctime>std::vector<int> reservoirSampling(const std::vector<int>& stream, int k) { std::vector<int> reservoir(k); int n = stream.size();
// 检查 k 是否合法
if (k > n) {
return stream; // 或抛出异常
}
// 初始化：前 k 个元素直接放入蓄水池
for (int i = 0; i < k; ++i) {
reservoir[i] = stream[i];
}
// 随机种子
std::srand(static_cast<unsigned int>(std::time(nullptr)));
// 从第 k+1 个元素开始处理
for (int i = k; i < n; ++i) {
// 生成 [0, i] 之间的随机数
int j = std::rand() % (i + 1);
// 如果随机数小于 k，则用当前元素替换蓄水池中索引为 j 的元素
if (j < k) {
reservoir[j] = stream[i];
}
}
return reservoir;}
立即学习“C++免费学习笔记（深入）”；
// 使用示例 int main() { std::vector<int> dataStream = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 模拟数据流 int k = 3;
std::vector<int> sample = reservoirSampling(dataStream, k);
std::cout << "随机抽取的 " << k << " 个样本：";
for (int val : sample) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;}
关键点说明
为什么这个算法是公平的？
- 对于前 k 个元素：它们一开始就在池中，后续每个新元素都有机会替换它们。数学上可以证明，最终每个元素留在池中的概率恰好是 k/n。
- 对于第 i 个元素（i > k）：它被选中的概率是 k/i，而一旦被选中，它会等概率替换池中某个元素。
适用于真实数据流吗？
当然。上面的例子用了 vector 模拟数据流，实际中你可以将算法改造成边读边处理的形式，比如从文件、网络或传感器实时读取数据，不需要保存全部数据。
改进版本：使用现代 C++ 随机库
建议使用 <random> 替代 rand()，更安全、分布更均匀。
#include <random>std::vector<int> reservoirSamplingModern(const std::vector<int>& stream, int k) { std::vector<int> reservoir(k); int n = stream.size();
if (k >= n) {
return stream;
}
for (int i = 0; i < k; ++i) {
reservoir[i] = stream[i];
}
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, k - 1); // 用于选择替换位置
for (int i = k; i < n; ++i) {
std::uniform_int_distribution<> dis_i(0, i);
if (dis_i(gen) < k) {
reservoir[dis(gen)] = stream[i];
}
}
return reservoir;}
基本上就这些。蓄水池抽样是一个经典而实用的算法，C++ 实现简单，空间复杂度 O(k)，时间复杂度 O(n)，适合处理大规模或未知长度的数据流。关键是理解替换的概率机制，确保采样公平。不复杂但容易忽略细节，比如随机数范围和边界条件。
