编程珠玑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():

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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

hdu------1281 棋盘游戏(最小覆盖点)

棋盘游戏 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java...

31840
来自专栏菩提树下的杨过

Flash/Flex学习笔记(23):运动学原理

先写一个公用的小球类Ball: package{ import flash.display.Sprite; //小球 类 public class B...

312100
来自专栏蜕变

#哆啦A梦

write('by dongdong', font=("Bradley Hand ITC", 30, "bold"))

11300
来自专栏生信技能树

使用ESTIMATE来对转录组表达数据根据stromal和immune细胞比例估算肿瘤纯度

ESTIMATE (Estimation of STromal and Immune cells in MAlignant Tumor tissues usin...

55320
来自专栏非著名程序员

Palette让你的应用风格统一,绚丽多彩

今天这个是Android Material Design系列之Palette,Material Design系列的第五篇文章了,由于最近这个系列文章浏览量比较低...

19180
来自专栏Android点滴积累

Android高效内存2:让图片占用尽可能少的内存

Android高效内存:让图片占用尽可能少的内存 一、让你的图片最小化 1.1 大图小图内存使用情况对比 大图:440 * 336    小图:220 * 16...

315110
来自专栏生信宝典

一文教会你查找基因的启动子、UTR、TSS等区域以及预测转录因子结合位点

本文授权转载自科研小助手(ID:SciRes)斜体小一号字体为生信宝典的备注或校正。

12.1K30
来自专栏落影的专栏

OpenGL ES实践教程(二)摄像头采集数据和渲染

教程 这一篇教程是摄像头采集数据和渲染,包括了三部分内容,渲染部分-OpenGL ES,摄像头采集图像部分-AVFoundation和图像数据创建纹理部分-G...

46850
来自专栏用户2442861的专栏

Python-OpenCV 处理图像(二):滤镜和图像运算

喜欢自拍的人肯定都知道滤镜了,下面代码尝试使用一些简单的滤镜,包括图片的平滑处理、灰度化、二值化等:

24210
来自专栏小樱的经验随笔

HDU 1874 畅通工程续【Floyd算法实现】

畅通工程续 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

291100

扫码关注云+社区

领取腾讯云代金券