问题描述：
给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出这组数据的k个概率相等的均匀抽样。
要求：
（1）仅扫描数据一次。
（2）空间复杂度为O(K)。空间复杂度与整个数据量无关，只与抽样大小有关。
（3）扫描到数据的前n 个数据时（n>k）,保存当前已扫描数据的k个均匀抽样。
根据要求，首先体积很大内存一次装不下，不能直接不能直接取N内的k个随机数，因为N的长度是未知的。此外也不能采用不能先遍历一遍，然后分块存储数据，再随机选取。最后要求是数据选取绝对随机的保证。
解法：采用水塘抽样算法（Reservoir Sampling）
代码非常简单，如下
/***
*
* @param input 模拟的原始数组
* @param k 采样的的个数
* @return 返回采样的数据
*/publicstaticint[]sample(int[]input,int k){Random random=newRandom();int[]ret=newint[k];for(int i=0;i<input.length;i++){if(i<k){ret[i]=input[i];//先取，前k个数字放在数组里面}else{//如果i>k，在1-i之间，取一个随机数字，如果这个随机数字小于k，就替换数组，否则就继续遍历，知道结束int rand=random.nextInt(i);//if(rand<k){ret[rand]=input[i];}}}returnret;}
算法思路如下：
（1）如果接受的数据量小于k，则依次放入采样数组中
（2）当接收到第i个数据，i大于等于k时，在[0,i]的范围内取一个随机数d 如果d落在了[0,k-1]的范围内，则取接收到的第i个数据替换采样数组中下标等于d位置上的值。
（3）重复步骤2。
该算法的精妙之处在于，当处理到数据源里面第n个数据时，采样数组里面的数据，总是均匀的抽样。
推导证明：
（1）第一步初始化。出现在水库中的前k个元素，直接保存在数组A中。前k个数被选中的概率都是一致的，都是1。 （2）第二步。在处理第k+1个元素时分两种情况：
情况1：第k+1个元素未被选中，数组中没有元素被替换；此时，数组中每个元素的出现概率肯定是一样的，这很显然。但具体是多少呢？就是第k+1个元素未被选中的概率：1-P(第k+1个元素被选中)=1-k/(k+1)=1/(k+1)。（由于第k+1个元素被选中的概率是k/(k+1)（根据公式k/i））
情况2：第k+1个元素被选中，数组中某个元素被第k+1个元素替换掉。第k+1个元素被选中的概率是k/(k+1)（根据公式k/i），所以这个新元素在水库中出现的概率就一定是k/(k+1)（不管它替换掉哪个元素）。下面来看水库中原有元素最终还能留在水库中的概率，水库中原有数据被替换的几率都相等为1/k。水库中任意一个元素被替换掉的概率是：(k/k+1)*(1/k)=1/(k+1)，意即首先要第k+1个元素被选中，然后该元素在k个元素中被选中。那它未被替换的概率就是1-1/(k+1)=k/(k+1)。可以看出来，旧元素和新元素出现的概率是相等的。
（3）第k+1之后面每个元素都重复第二步，即第i （i>k+1）个元素以k/i的概率决定是否将它放入蓄水池，最终所有元素出现在水库中的概率相等。
总结：
其实，这种算法的能保证概率相等的前提就是： 当数据总量加1的时候，都会在当前总量的范围内，进行生成随机数，这样就能保证范围内的所有的数字出现概率都是相等的，然后根据概率均等随机数字来判断，是否落在了我们采样数组的边界中，如果落到了就替换原来数组中相同的位置的值，如果没有落到，就继续遍历选取，直到所有的数据处理完毕。
网友评论