这个问题就是一个蓄水池抽样(Reservoir Sampling),算法可以如下描述:
网上有人给出了证明,先转过来: 【转】 证明: 每次都是以 k/i 的概率来选择 对于抽样问题,最近看见了一些方法,做个总结: 问题:要求从1,2,3..n中,以等概率的方式,抽取m个元素 1、使用上面的蓄水池抽样 void sample_pool(const int N, const int m) { int i, tmp,rd; int* x = new int[N]; for(i = 0 ; i < N ; i ++) x[i] = i + 1; for(i = m ; i < N; i ++ ) { rd = rand()%i; if(rd < m) swap(x[i],x[rd]); } for(i = 0 ; i < m; i ++) cout<<x[i]<<" "; delete []x; x = NULL; }空间和时间均为O(N) 2 、从N个中选取m个, 可以先确定一个后,然后从身下的N-1个中选取m-1个出来。 void sample_rand(const int N,const int m) { int select = m,i,rd; int remain = N; for(i = 0; i < N ; i++) { rd = rand()%remain; if(rd < select) { cout<< i<<" "; select--; } remaining--; } } 3、将抽样的看成是一个集合,则要从N中选择出m个不同的元素,存入到集合中,可用set来完成 利用STL中的set来完成这个功能。 void sample_set(const int N,const int m) { set<int>s; while(s.size()<m) { s.insert(rand()%n); } for(set<int>::iterator it = s.begin();it!=s.end();it++) cout<<*it<<" "; } 4、扰乱一个递增序列。 for i =[0,N) swap(x[i],x[rand(i,n-1)]; 有人证明,只要扰乱前m个就可以。 void sample_shuf(const int N,const int m) { int i, j; int *x = new int[N]; for(i = 0 ; i <N; i++) for(i = 0 ; i < m ; i ++) { j = rand(i,n-1); swap(x[i],x[j]); } sort(x,x+m); Print(x,m); delete []x;x= NULL; } 关于采样的几个问题: 1、Given a random number generator which can generate the number in rang(1,5)uniformly, how can u use it to build a random number generator which can generate the number in range(1,7) uniformly? 解答:利用拒绝采样定理 五进制表示: 11 12 13 14 15 21 22 23 24 25 31 32 33 34 35 41 42 43 44 45 51 52 53 54 55 2、Generate a random permutation for a deck of cards 解答: for k=N:1 end for k = 1:N end 3、Given a long log file ,pick 1000items evenly from them. |
|
来自: suiqianying > 《ACM》