Sampling - Programming Pearls

http://www.hawstein.com/posts/make-thiner-programming-pearls.html
取样问题

问题：对于整数m和n，其中m<n，输出0~n-1范围内m个随机整数的有序列表， 不允许重复。

比如m=3, n=5，那么一种可能输出是0，2，3(要求有序)。实现1来自Knuth的TAOCP， 时间复杂度O(n)：

void GenKnuth(int m, int n) {
    for(int i=0; i<n; ++i) {
        if((bigrand()%(n-i)) < m) {
            cout<<i<<endl;
            --m;
        }
    }
}

其中，bigrand()的作用是返回一个很大的随机整数。

实现2：在一个初始为空的集合里面插入随机整数，直到个数足够。代码如下：

void GenSets(int m, int n) {
    set<int> s;
    while(s.size() < m)
        s.insert(bigrand() % n);
    set<int>::iterator i;
    for(i=s.begin(); i!=s.end(); ++i)
        cout<<*i<<endl;
}

实现3：把包含整数0～n-1的数组顺序打乱，然后把前m个元素排序输出。 该方法的性能通常不如Knuth的算法。代码如下：

void GenShuf(int m, int n) {
    int x[n];
    for(int i=0; i<n; ++i)
        x[i] = i;
    for(int i=0; i<m; ++i) {
        int j = randint(i, n-1);
        swap(x[i], x[j]);
    }
    sort(x, x+m);
    for(int i=0; i<m; ++i)
        cout<<x[i]<<endl;
}

http://dongxicheng.org/data-mining/hadoop-sampling/

(1) 第一种方法来自Knuth的《The art of Computer Programming, Volume 2: Seminumerical Algorithms》

伪代码是：

1 2 3 4 5 6 7 8 9 10 11 12 13

select = m   remaining = n   for I = [0 n )     if (bigrand() % remaining) < select       print i       select—     remaining—

只要m<=n，程序选出来的整数就恰为m个。

C++的实现如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void genKnuth(int m, int n) {     for( int i = 0; i < n; i++) {      if(bigrand() % (n - i) < m） {       cout <<i << endl;       m--;      }     }   }

该算法非常节省空间，但需要全部扫描n个数，当n很多时，效率不高。

（2）第二种方法的复杂度只与m有关，采用了set（实际上是红黑树）节省时间。代码如下：

1 2 3 4 5 6 7 8 9 10 11 12 13

void gensets(int m, int n) {     set<int> S;     while(S.size() < m) {      S.insert(bigrand() % n);     }     // print S   }

该方法每次插入均在O(log m)时间内完成，但需要的空间开销很大。

（3）第三种方法克服了（2）的缺点，代码如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

void genshuf(int m, int n) {     int i, j;     int *x = new int[n];     for(i = 0; i < n; i++) {      x[i] = i;     }     for(i = 0; i < m; i++) {      j = randint(i, n-1);      int t = x[i]; x[i] = x[j]; x[j] = x;     }     sort(x, x+m);     //print result   }

该算法需要n个元素的内存空间和O(n+mlogm)的时间，其性能通常不吐Knuth的算法。

（4）当m接近n时，基于集合的算法生成的很多随机数都要丢掉，因为之前的数已经存在于集合中了，为了改进这一点，算法如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

void genfloyd(int m, int n)   {     set<int> S;     set<int>::iterator i;     for(int j=n-m; j < n; j++) {      int t = bigrand()%（j+1);      if(S.find(t) == S.end()){      S.insert(t); // t not in S     } else {      S.insert(j); // t in S     }    }     //print results   }