蓄水池随机抽样检测
一、蓄水池抽样
收到一堆的数据包,数据包数量N很大,且N直到处理完所有数据之前都不可知,
请问如何在只遍历一遍数据(O(N))的情况下,能够随机选取出m个不重复的数据?
场景包含3个前提条件
1、数据包数量N很大,不可知,所以不能直接在N个数据包中取随机数
2、时间复杂度O(N),只能遍历一遍。
3、随机选取m个数,每个数呗选中的概率为m/N,绝对随机
C++代码实现如下:
include
#include
using namespase std;
void Reservoir(int *dataStream,int m,int N)
int *reservoir=new int[m]; //声明蓄水池
for(int i=0;i reservoir[i]=dataStream[i]; for(int i=m ; i srand((unsigned int)(time(0))); int position=rand()%i; //生成0~i之间的随机数 if(position reservoir[position]=dataStream[i]; for(int i=0;i cout<<"蓄水池中第"<
void main() int N=12; int m=4; int *array =new int[N]; for(int i=0;i array[i]=i; Reservoir(array,m,N); 算法思路: 1)如果接受的数据量小于m,则依次存入蓄水池中 2)当接收到第i个数据包时,i>=m,在[0, i]范围内取以随机数position,若position的落在[0, m-1]范围内,则用接收到的第i个数据替换蓄水池中的第position个数据。 3)重复直至结束。 二、分布式蓄水池抽样