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

Problem:

代码语言：javascript复制

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

Solutions:

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

代码语言：javascript复制

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 :

代码语言：javascript复制

#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():

f

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.

abstract code it space time

0 人点赞