水塘抽样算法能从未知长度数据流中等概率抽取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 的概率保留它作为当前结果。
立即学习“C++免费学习笔记（深入）”；
#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 > num) { reservoir[i++] = num; } // 处理后续元素 int count = k; while (std::cin >> num) { ++count; int j = rand() % count; if (j < k) { reservoir[j] = num; } } return reservoir;}
使用建议与注意事项
实际应用中注意以下几点：
确保随机数生成器已正确初始化（如使用 srand 或 C++11 的 random 库更佳）对于重复调用场景，避免频繁重置随机种子若需更高精度随机性，推荐使用 头文件中的分布类数据流可以是文件、网络包、传感器输入等任意顺序源算法不要求知道总长度，适合实时处理基本上就这些。水塘抽样结构简单但逻辑精巧，是处理大数据随机抽样的经典解法。
以上就是C++怎么实现一个水塘抽样算法_C++大数据流随机抽样问题的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485397.html
微信扫一扫 
支付宝扫一扫 
