【编程珠玑】读书笔记第十二章取样问题-白红宇

【编程珠玑】读书笔记第十二章取样问题

阅读量：6157 次

发布时间：2019-06-21

本文共 4757 字，大约阅读时间需要 15 分钟。

2013-07-16 21:51:49

本章介绍生成小于[0,n-1]区间内的m个顺序随机数的三种方法。

总结参考：

1.问题

　　抽象后的问题如下：输入两个整数m和n,(m < n).输出0～n-1范围内的m个随机整数的有序列表，不允许重复。

　　也就是说，要对0~n-1范围内的数字进行选择，每个数字被选中的概率相等.

　　有两点要注意：不允许重复，结果有序；

2.解决方案

　　2.1已有知识

　　利用库函数<stdlib.h>中的rand()函数可以产生0到RAND_MAX范围内的随机整数。

　　 RAND_MAX是在前面头文件中定义的宏，具体大小与实现有关，至少为32767(2^15-1).

　　两个相关函数：

　　产生很大随机整数bigrand()：RAND_MAX *rand() + rand();实际上就是先产生前15位，再产生后15位，也即rand()<<15 | rand();

　　产生指定范围随机整数 randint(l,u): rand()%(u-l+1)+l; 产生的数据在[l,u]之间.

　　(后面对时间复杂度的讨论，都默认rand()需要单位时间）

3.时间效率

RandomGenerateKnuth时间效率：该程序的时间复杂度是与n有关的：O(n),空间上只需要几十个字节。

RandomGenerateUseSet时间效率：set每次插入时间为O(logm),while循环总共进行了m次插入，遍历集合需要O(m).故总时间为O(mlogm).额外的空间需求为set集的大小：O(m).

RandomGenerateUseQsort时间效率：时间上为O(n+mlogm), 一次初始化和排序。空间上也需要O(n).

完整实现代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6   7 const int MaxLength = 10000000;  8   9 //输入合法性检查 10 void CheckInvalid(int array[],int len) 11 { 12     assert(NULL != array && len > 0);  13 } 14  15 //产生大的随机数 16 int BigRandomGenarate() 17 { 18     return ( RAND_MAX * rand() + rand() ); //对C语言，rand()函数需包含头文件#include
         
          ，但在C++中包含iostream即可 19 } 20  21 //产生在[lowBound,upperBound - 1]区间的随机数 22 int RandomIntGenerate(int lowBound, int upperBound) 23 {     24     return (lowBound + (RAND_MAX * rand() + rand()) % (upperBound - lowBound + 1) ); 25 } 26  27 //qsort对int型数据排序所需的笔记函数 28 int IntCompare(const void *_p,const void *_q) 29 {     30     int *p = (int *) _p; 31     int *q= (int *) _q; 32     return (*p - *q); 33 } 34  35 //用Knuth的方法产生随机数，用概率判断数据是否被选择 36 void RandomGenerateKnuth(int randomArray[],const int lengthOfRandom,const int maxRandomNumber) 37 { 38     int i; 39     int selectedNum = lengthOfRandom; 40  41     srand( time(NULL) );    //产生rand()函数的种子 42  43     for (i = 0;i < maxRandomNumber;++i) 44     { 45         if (BigRandomGenarate() % (maxRandomNumber - i) < selectedNum) 46         { 47             randomArray[lengthOfRandom - selectedNum] = i; 48             --selectedNum; 49         } 50     } 51 } 52  53 //产生[0,n-1]区间内的随机数，将不重复的问题利用set容器的唯一性解决 54 void RandomGenerateUseSet(int randomArray[],const int lengthOfRandom,const int maxRandomNumber) 55 { 56     set 
          
            randomSet; 57 int i; 58 59 srand( time(NULL) ); //产生rand()函数的种子 60 61 while (randomSet.size() < lengthOfRandom) 62 { 63 randomSet.insert(BigRandomGenarate() % maxRandomNumber); 64 } 65 66 set 
           
             :: iterator iterSet; 67 i = 0; 68 for (iterSet = randomSet.begin();iterSet != randomSet.end();++iterSet) 69 { 70 randomArray[i++] = *iterSet; 71 } 72 } 73 74 //通过交换保证不重复，但进行排序来保证是顺序的 75 void RandomGenerateUseQsort(int randomArray[],const int lengthOfRandom,const int maxRandomNumber) 76 { 77 int i; 78 int *sequenceArray = new int[maxRandomNumber]; 79 int randomTmp; 80 int tmp; 81 82 srand( time(NULL) ); //产生rand()函数的种子 83 84 for (i = 0;i < maxRandomNumber;++i) 85 { 86 sequenceArray[i] = i; 87 } 88 89 for (i = 0;i < lengthOfRandom;++i) 90 { 91 randomTmp = RandomIntGenerate(i,maxRandomNumber); 92 tmp = sequenceArray[i]; 93 sequenceArray[i] = sequenceArray[randomTmp]; 94 sequenceArray[randomTmp] = tmp; 95 } 96 97 for (i = 0;i < lengthOfRandom;++i) 98 { 99 randomArray[i] = sequenceArray[i];100 }101 102 qsort(randomArray,lengthOfRandom,sizeof(int),IntCompare);103 delete [] sequenceArray; 104 }105 106 //显示数组107 void DisplayArray(int array[],int len)108 {109 CheckInvalid(array,len);110 111 for (int i = 0;i < len;++i)112 {113 cout<
            
             <<"\t";114 }115 cout<
             
              >lengthOfRandom>>maxRandomNumber;140 141 //输入要测试程序的编号142 cout<<"please enter the identifier of the program to test (end with ctrl+z): "<
              
               >programToTest)144 {145 timeStart = clock();146 switch (programToTest)147 {148 case 1: 149 cout<<"Test RandomGenerateKnuth..."<
               
                < lengthOfRandom - 1;++i)172 {173 if (randomArray[i] > randomArray[i + 1])174 {175 cout<<"sort bug i = "<
                <

测试结果:

the identifier of the program is :RandomGenerateKnuth : 1RandomGenerateUseSet : 2RandomGenerateUseQsort : 3please enter the lengthOfRandom and the maxRandomNumber ,end with ctrl+z :1000000 10000000please enter the identifier of the program to test (end with ctrl+z):1Test RandomGenerateKnuth...the time cost to genarate 1000000 random numbers is : 2.764e+006 msplease enter the identifier of the program to test (end with ctrl+z):2Test RandomGenerateUseSet...the time cost to genarate 1000000 random numbers is : 2.5582e+007 msplease enter the identifier of the program to test (end with ctrl+z):3Test RandomGenerateUseQsort...the time cost to genarate 1000000 random numbers is : 3.255e+006 msplease enter the identifier of the program to test (end with ctrl+z):^Z请按任意键继续. . .

转载地址：http://fkafa.baihongyu.com/

你可能感兴趣的文章