编程珠玑II C12笔记: rand num generator

Problem:

given m<n, generate random numbers of m within range(0..n).

Solutions:

a Knuth’s solution of O(log n) time :

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

But when n was large, it meets bootleneck. Improve with:

a solution of O(m log m) time using :

#include <iostream>
#include <cstdlib>
#include <set>
using namespace std;
void gensets(int m, int n){
    set<int> S;
    while(S.size()<m){
        S.insert(std::rand() % n);
        set<int>::iterator i;
        for (i = S.begin(); i!=S.end(); ++i){
            cout<< *i << endl;
        }
    }
}
int main(){
    gensets(1000000, 10000000);
    return 0;
}

shuffle solution O():

Principles

Understand the Perceived Problem

talk to user

Specify an Abstract Problem

get a clean, crisp problem statement.

Explore the Desgn Space

think for a day and code for a min rather than per contra

Implmnt One Solution

choose the best

Retrospect

Polya’s delightful How to Solve It can help programmer become a better problem solver.