蓄水池算法

 1 #include<stdio.h>
 2 #include<time.h>
 3 #include<stdlib.h>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 void swap_a(int *a,int *b)
 8 {
 9     int temp ;
10     temp = *a;
11     *a = *b;
12     *b = temp;
13 
14 }
15 // swap by  xor
16 void swap_b(int *a,int *b)
17 {
18     *a = *a^*b;
19     *b = *a^*b;
20     *a = *a^*b;
21 }
22 void randomint(int a[],int _range,int _length)
23 {
24     if(_length<=0) return;
25     for(int i = 0; i < _range;++i)
26     {
27         a[i]=(rand()%_range);
28     }
29 }
30 int reservoirsampling(int a[],int end)
31 {
32     int i = 1;
33     int ans =a[0];
34     while(a[i]!=end){
35        if(rand()%i==1) ans = a[i];
36        i++;
37     }
38     return ans;
39 
40 }
41 void reservoirsamplingk(int a[],int _length,int _k)
42 {
43     if(_k>_length) return;
44     for(int i = _k; i<_length; i++){
45         int temp = rand()%i;
46         if(temp<_k)
47         {
48             swap_b(&a[i],&a[temp]);
49         }
50     }
51 }
52 int main()
53 {
54     //随机产生了一个长度为1000,范围在10000内的随机数组
55     //其中随机抽取了一个数字作为结束符位置为counts，在
56     //遍历一遍的清况下已概率为1/counts输出结束符之前的
57     //任意一个数字
58     //@蓄水池算法:读入一个随机长度为n的数组或者文件，
59     //遍历一遍，以n分之1输出某一行或者一个数，具体的实
60     //现方法就为以1/i确定是否将当前数（行）作为输出，i
61     //为当前循环次数。
62     //@蓄水池算法应用2：在一个长度为n（n是提前不知道的）
63     //的数组里，以概率为k/n选取k个数。或者说，在一个未
64     //知或者很大样本空间内随机选取n个数：
65     //具体方法：首先前k个数，在下次循环时，以k/i的概率
66     //确定是否与前k个数中的某个数是否与当前数替换
67     int ans,counts,end;
68     int length = 1000;
69     int range = 10000;
70     int *a = new int[1001];
71     randomint(a,length,range);
72     counts = rand()%1000;
73     end = a[counts];
74     ans = reservoirsampling(a,end);
75     cout<<"以概率为"<<counts<<"分之一选取了数字："<<ans<<endl;
76     for(int i=0;i<10;i++)
77         cout<<a[i]<<endl;
78     cout<<"////////////////////////////\n"<<endl;
79     reservoirsamplingk(a,length,10);
80      for(int i=0;i<10;i++)
81         cout<<a[i]<<endl;
82     delete [] a;
83     return 0;
84 }