本文主要是介绍面试题80：海量数据等概论抽样（蓄水池问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
从N个元素中随机抽取K个元素，N的个数不确定，要求保证每个数字被抽中的概率相等。
解读：
这种应用的场景一般是数据流的情况下，由于数据只能被读取一次，而且数据量很大，并不能全部保存，因此数据量N是无法在抽样开始时确定的；但又要保证概率相等。
解决：
解决方案就是蓄水池抽样。主要思想就是保持一个集合（这个集合最终的数字就是被抽中的数字）。依次遍历所有数据的时候以一定的概率替换掉这个蓄水池中的数字。
其伪代码为：
Init : a reservoir with the size： k //初始化蓄水池为前K个数for i= k+1 to N M=random(1, i);if( M < k)SWAP the Mth value and ith valueend for证明概率相等：
首先要明白，如果最终K个元素确定，则这K个元素出现的概率都是K/N。
下面来证明当读到第i个元素时，水库中每个元素出现的概率是K/i。
1）初始情况：出现在水库中的K个元素出现的概率都是1.
2）第一步：处理第K+1个元素的情况。分为两种情况：水库中元素都没有被替换；水库中某个元素被第K+1个元素替换掉。
对于情况2：第K+1个元素被选中的概率是K/(K+1)，所以这个新元素在水库中出现的概率就一定是K/(K+1)。下面看水库中剩余的元素出现的概率。水库中人一个元素被替换的概率是1/(K+1)，那它出现在水库中的概率就是K/(K+1)。可以看出新元素和旧元素出现的概率是相等的。
对于情况1：当元素全部都没有替换掉的时候，每个元素的出现概率肯定是一样的，这很显然。但具体是多少呢？就是1-P(第k+1个元素被选中)=1-1/(k+1)=K/(k+1)。
即i=K+1的时候满足
3）归纳法：重复上面的过程，只要证明第i步到第i+1步，所有元素出现的概率相等即可。
假设第i个元素也满足水库中每个元素出现的概率是K/i，则当第i+1个元素时：
第i+1个元素出现在水池中的概率为K/(i+1)，很容易得到水库中其他元素出现的概率也是K/(i+1)。
下面利用上面的方法从1-100之间选出3个数：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;const int N = 100;
const int poolN = 3;int Random(int min, int max)
{return min + rand() % (max - min + 1);
}void Draw()
{int source[N];int re[poolN];for (int i = 0; i < N; i++) source[i] = i + 1;for (int i = 0; i < poolN; i++) re[i] = source[i];for (int k = poolN; k < N; k++){int temp = Random(0, k-1);if (temp < poolN) swap(re[temp], source[k]);}for (int i = 0; i < poolN; i++)cout << re[i] << " ";cout << endl;
}int main()
{srand((unsigned int)time(NULL));for (int i = 0; i < 100;i++)Draw();return 0;
}这篇关于面试题80：海量数据等概论抽样（蓄水池问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
