2013-07-10 18:39:25

【编程珠玑】读书笔记第一章

　　本书以一个排序的问题开篇，讨论了排序的最佳方法，并引入了位图排序的算法。实际上，此处的位图排序本质就是计数排序（关于计数排序，此处不再赘述），只不过由于此处问题的特殊性——数据没有重复，可使用更加节省空间的方法，对每一个数据，使用1bit的空间进行计数。

　　书中还给出了用标准库函数qsort、以及模板类set排序的提议，以与位图排序的性能进行比较，下面给出了几中排序方法，包括：

1. 使用模板类bitset作为计数数组实现位图排序，具体实现见代码中BitmapSort_1函数；
2. 用int型数据模拟bit型的操作实现位图排序，具体实现见下面代码中BitmapSort_2函数，该函数可在C语言下实现；
3. 用标准库函数qsort实现排序，具体实现见下面代码中main函数中qsort；
4. 用C++的模板类set或multiset实现排序；

　　上面几种方法，方法2是书中的方法，且可以用C语言实现，qsort也可用C语言实现，而其他两种方法必须用C++实现。使用前2中方法会受到用位图排序的使用场合的限制，而后面两种则没有限制。

　　下面给出上述4中方法的源代码实现，以及性能分析。

注意，性能分析部分的代码相对于前面的是有改动的，以性能分析部分的代码为最终的。

---

 

位图排序以及使用标准库函数qsort的排序

用位图排序的使用场合以及限制条件：

1. 待排序数组为非负数；

2. 输入数据限制在相对较小的范围内；

3. 数组元素不重复，若有重复，排序后数组会丢弃重复的元素；

上面已经提到过位图排序本质就是计数排序，而计数排序要准备一个用于计数的数组，对于位图，就是bit类型的数组。

在C++中，可以使用模板类bitset作为计数数组，具体实现见代码中BitmapSort_1函数。但在C语言中没有该类型的数据的，书中给出了一种用int型数据模拟bit型的操作，具体实现见下面代码中BitmapSort_2函数。

位图排序的实现，注意几点：

1. 在使用必须确保计数数组初初始化为全0：对于用C++中模板类bitset实现的位图排序的BitmapSort_1函数，即：Bitmap.reset();对于用int型数组模拟位图的BitmapSort_2函数，即BitmapArray[1 + N/BitsPerInt] = {0};
2. 注意语句 int BitmapArray[1 + N/BitsPerInt] = {0};   将会初始化数组所有元素，而不只是第一个；

对qsort，注意：

1. comp函数的参数类型必须为const类型，这是由qsort函数中参数cmp的类型决定的。

int comp(void *_p,void *_q)    //提示cannot convert parameter 4 from 'int (__cdecl *)(void *,void *)' to 'int (__cdecl *)(const void *,const void *)'

int comp(const void *_p,const void *_q)

用int型模拟位图的关键在与如何实现每个bit的置位、清零以及判断是否为1，书中给出了一种用位运算的方法，如下：

1 //用int型模拟位图，实现的位图排序 2 const int BitsPerInt = 32; 3 const int Div32Shift = 5; 4 const int Mod32Mask = 0x1F; 5  6 //BitmapSort_2:用位运算实现置位、清零、判断是否为1 7 void SetBit(int BitmapArray[],const int BitToSet) 8 { 9     //BitmapArray[ (BitToSet >> Div32Shift) ] | = ( 1 << (BitToSet & Mod32Mask) );  //error C2059: syntax error : '='10     BitmapArray[ (BitToSet >> Div32Shift) ] = BitmapArray[ (BitToSet >> Div32Shift) ] 11     | ( 1 << (BitToSet & Mod32Mask) ); 12 }13 14 void ClearBit(int BitmapArray[],const int BitToClear)15 {16     BitmapArray[ (BitToClear >> Div32Shift) ] = BitmapArray[ (BitToClear >> Div32Shift) ] 17     & ~( 1 << (BitToClear & Mod32Mask) ); 18 }19 20 //bool IsBitSet(int BitmapArray[],const int BitToSet)21 bool IsBitSet(const int BitmapArray[],const int BitToCheck)  //定义为const类型，在不小心改变时，会给出报错信息22 {23     return ( BitmapArray[ (BitToCheck >> Div32Shift) ] & ( 1 << (BitToCheck & Mod32Mask) ) ); 24 }

 

位图排序完整代码：

 

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 using namespace std;  5 #define N 10  6   7 //BitmapSort_1:用C++中模板类bitset实现的位图排序  8 void BitmapSort_1(int ArrayUnsorted[],int n)  9 { 10     bitset 
        
          Bitmap; 11     int * ArraySorted = new int[n]; 12     int cnt = 0; 13     Bitmap.reset();        //清零，保证使用之前全部为0 14  15     int i ; 16     for (i = 0;i < n;++i)     //标记各个位置 17     { 18         Bitmap.set(ArrayUnsorted[i]); 19     } 20  21     for (i = 0;i < n;++i)   22     { 23         if ( Bitmap[i] )   //如果位置i为1，则说明i在数组ArraySorted中出现，且为排序后的第cnt个 24         { 25             ArrayUnsorted[cnt++] = i; 26         } 27     } 28 } 29  30 //用int型模拟位图，实现的位图排序 31 const int BitsPerInt = 32; 32 const int Div32Shift = 5; 33 const int Mod32Mask = 0x1F; 34  35 //BitmapSort_2:用位运算实现置位、清零、判断是否为1 36 void SetBit(int BitmapArray[],const int BitToSet) 37 { 38     //BitmapArray[ (BitToSet >> Div32Shift) ] | = ( 1 << (BitToSet & Mod32Mask) );  //error C2059: syntax error : '=' 39     BitmapArray[ (BitToSet >> Div32Shift) ] = BitmapArray[ (BitToSet >> Div32Shift) ]  40     | ( 1 << (BitToSet & Mod32Mask) );  41 } 42  43 void ClearBit(int BitmapArray[],const int BitToClear) 44 { 45     BitmapArray[ (BitToClear >> Div32Shift) ] = BitmapArray[ (BitToClear >> Div32Shift) ]  46     & ~( 1 << (BitToClear & Mod32Mask) );  47 } 48  49 //bool IsBitSet(int BitmapArray[],const int BitToSet) 50 bool IsBitSet(const int BitmapArray[],const int BitToCheck)  //定义为const类型，在不小心改变时，会给出报错信息 51 { 52     return ( BitmapArray[ (BitToCheck >> Div32Shift) ] & ( 1 << (BitToCheck & Mod32Mask) ) );  53 } 54  55 void BitmapSort_2(int ArrayUnsorted[],const int n) 56 { 57     int BitmapArray[1 + N/BitsPerInt] = {
   0};   //将会初始化数组所有元素，而不只是第一个 58     int i ; 59     int cnt = 0; 60  61     for (i = 0;i < n;++i) 62     { 63         SetBit(BitmapArray,ArrayUnsorted[i]); 64     } 65  66     for (i = 0;i < n;++i) 67     { 68         if ( IsBitSet(BitmapArray,i) ) 69         { 70             ArrayUnsorted[cnt++] = i; 71             cout<
         
          < n;++i) 90     { 91         BitmapArray[i] = 0; 92     } 93 } 94  95 //显示数组元素 96 void DisplayArray(int ArrayUnsorted[],int n) 97 { 98     for (int i = 0;i < n;++i) 99     {100         cout<
          
           <<"\t";101 }102 cout<
          
         
        
       
      
     

 

 

---

使用C++ STL中的标准关联容器set排序

set 是一个容器，它用于储存数据并且能从一个数据集合中取出数据。它的每个元素的值必须惟一，而且系统会根据该值来自动将数据排序。每个元素的值不能直接被改变。

multiset与set的不同之处就是key可以重复，以及erase（key）的时候会删除multiset里面所有的key并且返回删除的个数。

 注意几点：

 iterator不支持运算<，因此不能用下面的方式控制循环

for (iter = SetForSort.begin();iter < SetForSort.end();++iter)

而应采用如下方式：

for (iter = SetForSort.begin();iter != SetForSort.end();++iter)

 会给出出错信息如下：

binary '<' : 'std::_Tree_const_iterator<_Mytree>' does not define this operator or a conversion to a type acceptable to the predefined operator

 

用下面的方式将排序结果输出到ArrayUnsorted数组，在元素有重复时，容器访问会发生越界，因为容器中元素个数小于n

1 for (i = 0;i < n;++i)   2 3 {4   ArrayUnsorted[i] = *iter++;5  }

因为排序后的数组是在容器中存放的，所以直接采用容器的begin与end控制比较好，如下：

1 for (iter = SetForSort.begin();iter != SetForSort.end();++iter)2     {3         ArrayUnsorted[cnt++] = *iter;4     }

 

完整代码：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 #define N 10 5  6 //没有加入合法性检查以及出错处理，只是实现了函数的功能 7 //使用C++ STL中的标准关联容器set排序 8 void SetContainerSort(int ArrayUnsorted[],int n) 9 {10     //set 
       
         SetForSort;            //使用set，元素不可重复11     //set 
        
          :: const_iterator iter = SetForSort.begin();12     multiset 
         
           SetForSort;        //使用multiset，元素可重复13     multiset 
          
            :: const_iterator iter = SetForSort.begin();14 int i;15 int cnt = 0;16 17 for (i = 0;i < n;++i)18 {19 SetForSort.insert(ArrayUnsorted[i]);20 }21 22 for (iter = SetForSort.begin();iter != SetForSort.end();++iter)23 {24 ArrayUnsorted[cnt++] = *iter;25 }26 }27 28 //显示数组元素29 void DisplayArray(int ArrayUnsorted[],int n)30 {31 for (int i = 0;i < n;++i)32 {33 cout<
           
            <<"\t";34 }35 cout<
           
          
         
        
       
      
     

使用set或multiset容器，都可对不同类型的数进行排序，当然也可对含有负数的int数组排序。

因为set容器中的元素必须唯一，元素重复时会被忽略，所以使用set容器时，若输入元素有重复，利用set排序的结果会有丢失，在main中测试用第二行的数组时，运行结果如下：

the unsorted array is :7       9       2       3       4       5       2       8       7       6Test SetContainerSort...the sorted array is :2       3       4       5       6       7       8       9       7       6请按任意键继续. . .

可以看到，set容器忽略了重复的元素，输出的7、6是原数组的元素。

若将使用的容器改为multiset，可正确排序，运行结果如下：

the unsorted array is :7       9       2       3       4       5       2       8       7       6Test SetContainerSort...the sorted array is :2       2       3       4       5       6       7       7       8       9请按任意键继续. . .

 

 

---

 

 

 性能分析

结论：

BitmapSort_1是最快的，在数组长度为10,0000时，其速度比BitmapSort_2大概快一倍，应该是利用了STL中的bitset的优势，对bit的操作更快；

BitmapSort_2速度次之，qsort更次，而用set容器是最慢的，在数组成都为1000,0000时，性能的差别更为明显。

注意几点：

用clock()函数计时，分析时间性能，如下：

sortStartTime = clock();

 BitmapSort_2(ArrayUnsorted,numberOfRandomInt);

 TimeCost = 1e6 * ( clock() - sortStartTime ) / CLOCKS_PER_SEC;

通过程序运行前后的时间差，得到程序的运行时间。

栈内存是有限的，本程序中若数组长度为1000,0000如果在使用栈内存，程序运行时崩溃，单步跟踪，则会提示栈溢出，如下：

 

 

因此，在使用空间较大时，应在堆上分配内存，对于BitmapSort_2，将

int BitmapArray[1 + MaxRandomInt/BitsPerInt] = {0}; 

改为int *BitmapArray = new int[1 + MaxRandomInt/BitsPerInt]; 

并注意加上数组的初始化。

另外，对于位图排序，还应注意，最后for循环的结束条件是i < MaxRandomInt，而不是i < n,如下：

1 for (i = 0;i < MaxRandomInt;++i)  //不是for (i = 0;i < n;++i)2     {3         if ( IsBitSet(BitmapArray,i) )4         {5             ArrayUnsorted[cnt++] = i;6         }7     }

 

时间开销分析完整代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6   7 const int MaxRandomInt = 10000000;  8 const int NumberToSort = 1000000;  9  10 //产生在区间[lowerBound,upperBound]内的一个随机数 11 int RandomInt(const int lowerBound,const int upperBound) 12 { 13     return ( lowerBound + ( RAND_MAX * rand() + rand() ) % (upperBound - lowerBound + 1) ); 14 } 15  16 //产生在[0,maxOfRandomInt]范围内的numberOfRandomInt个随机数 17 //结果存入数组randomInt中 18 void RandomIntGen(const int numberOfRandomInt,const int maxOfRandomInt,int randomInt[]) 19 { 20     int i; 21     int tmp; 22     int randomTmp; 23     int *sequenceInt = new int[maxOfRandomInt]; 24  25     srand((unsigned) time(NULL)); 26  27     for (i = 0; i < maxOfRandomInt; i++) 28     { 29         sequenceInt[i] = i;     30     } 31  32     for (i = 0; i < numberOfRandomInt; i++)  33     { 34         randomTmp = RandomInt(i, maxOfRandomInt - 1); 35         tmp = sequenceInt[randomTmp]; 36         sequenceInt[randomTmp] = sequenceInt[i]; 37         sequenceInt[i] = tmp; 38         randomInt[i] = sequenceInt[i];    //随机数保存在数组中 39     } 40  41     delete [] sequenceInt;   //释放内存 42 } 43  44 //BitmapSort_1:用C++中模板类bitset实现的位图排序 45 void BitmapSort_1(int ArrayUnsorted[],int n) 46 { 47     bitset 
         
           Bitmap; 48     int * ArraySorted = new int[n]; 49     int cnt = 0; 50     Bitmap.reset();        //清零，保证使用之前全部为0 51  52     int i ; 53     for (i = 0;i < n;++i)     //标记各个位置 54     { 55         Bitmap.set(ArrayUnsorted[i]); 56     } 57  58     for (i = 0;i < n;++i)   59     { 60         if ( Bitmap[i] )   //如果位置i为1，则说明i在数组ArraySorted中出现，且为排序后的第cnt个 61         { 62             ArrayUnsorted[cnt++] = i; 63         } 64     } 65 } 66  67 //不需要写初始化函数，因为在定义的时候可以初始化 68 void Init(int BitmapArray[],const int n) 69 { 70     for (int i = 0;i < n;++i) 71     { 72         BitmapArray[i] = 0; 73     } 74 } 75  76 //用int型模拟位图，实现的位图排序 77 const int BitsPerInt = 32; 78 const int Div32Shift = 5; 79 const int Mod32Mask = 0x1F; 80  81 //BitmapSort_2:用位运算实现置位、清零、判断是否为1 82 void SetBit(int BitmapArray[],const int BitToSet) 83 { 84     //BitmapArray[ (BitToSet >> Div32Shift) ] | = ( 1 << (BitToSet & Mod32Mask) );  //error C2059: syntax error : '=' 85     BitmapArray[ (BitToSet >> Div32Shift) ] = BitmapArray[ (BitToSet >> Div32Shift) ]  86     | ( 1 << (BitToSet & Mod32Mask) );  87 } 88  89 void ClearBit(int BitmapArray[],const int BitToClear) 90 { 91     BitmapArray[ (BitToClear >> Div32Shift) ] = BitmapArray[ (BitToClear >> Div32Shift) ]  92     & ~( 1 << (BitToClear & Mod32Mask) );  93 } 94  95 //bool IsBitSet(int BitmapArray[],const int BitToSet) 96 bool IsBitSet(const int BitmapArray[],const int BitToCheck)  //定义为const类型，在不小心改变时，会给出报错信息 97 { 98     return ( BitmapArray[ (BitToCheck >> Div32Shift) ] & ( 1 << (BitToCheck & Mod32Mask) ) );  99 }100 101 void BitmapSort_2(int ArrayUnsorted[],const int n)102 {103     int i ;104     int cnt = 0;105     //int BitmapArray[1 + MaxRandomInt/BitsPerInt] = {0};   //将会初始化数组所有元素，而不只是第一个106     int *BitmapArray = new int[1 + MaxRandomInt/BitsPerInt];   //当MaxRandomInt较大时，必须从对上分配内存，否则内存不够用，导致出错107     108     if (NULL == BitmapArray)109     {110         cout<<"memory allocation error !"<
          
           < n;++i)117 {118 SetBit(BitmapArray,ArrayUnsorted[i]);119 }120 121 /*for (i = 0;i < n;++i)122 {123 if ( IsBitSet(BitmapArray,i) )124 {125 ArrayUnsorted[cnt++] = i;126 }127 }*/128 129 for (i = 0;i < MaxRandomInt;++i)130 {131 if ( IsBitSet(BitmapArray,i) )132 {133 ArrayUnsorted[cnt++] = i;134 }135 }136 137 delete [] BitmapArray;138 }139 140 //没有加入合法性检查以及出错处理，只是实现了函数的功能141 //使用C++ STL中的标准关联容器set排序142 void SetContainerSort(int ArrayUnsorted[],int n)143 {144 //set 
           
             SetForSort; //使用set，元素不可重复145 //set 
            
              :: const_iterator iter = SetForSort.begin();146 multiset 
             
               SetForSort; //使用multiset，元素可重复147 multiset 
              
                :: const_iterator iter = SetForSort.begin();148 int i;149 int cnt = 0;150 151 for (i = 0;i < n;++i)152 {153 SetForSort.insert(ArrayUnsorted[i]);154 }155 156 for (iter = SetForSort.begin();iter != SetForSort.end();++iter)157 {158 ArrayUnsorted[cnt++] = *iter;159 }160 }161 162 163 //注意参数必须为const类型164 //int comp(void *_p,void *_q) //提示cannot convert parameter 4 from 'int (__cdecl *)(void *,void *)' to 'int (__cdecl *)(const void *,const void *)'165 int comp(const void *_p,const void *_q)166 {167 int *p = (int *)_p;168 int *q = (int *)_q;169 return (*p - *q);170 }171 172 //显示数组元素173 void DisplayArray(int ArrayUnsorted[],int n)174 {175 for (int i = 0;i < n;++i)176 {177 cout<
               
                <<"\t";178 }179 cout<
                
                 < n;i++) 198 {199 fprintf(fout,"%d\n",array[i]);200 }201 202 fclose(fout); 203 }204 205 void WriteArrayToSortedTxt(int array[],int n)206 {207 FILE *fout;208 int i;209 210 fout = fopen("array_sorted.txt","wt");211 212 if(fout == NULL)213 {214 printf("forward_i.txt open error!\n");215 exit(0);216 }217 218 printf("file open success!\n");219 220 for (i = 0;i < n;i++) 221 {222 fprintf(fout,"%d\n",array[i]);223 }224 225 fclose(fout); 226 }227 228 //测试程序229 int main()230 {231 const int numberOfRandomInt = NumberToSort;232 const int maxOfRandomInt = MaxRandomInt;233 int *ArrayUnsorted = new int[NumberToSort];234 int sortStartTime = 0;235 int TimeCost = 0;236 237 cout<<"the number of integer to sort is : "<
                 
                  <
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 对于用bitset容器的位图排序方法，由于bitset <MaxRandomInt> Bitmap;定义的Bitmap是在栈上的，当待排序数组长度为100,0000时，程序出错，提示栈溢出，因此采用数据个数为10，0000，分析，运行结果如下：

the number of integer to sort is : 100000file open success!Test BitmapSort_1...the time cost of BitmapSort_1 is : 65000msfile open success!Test BitmapSort_2...the time cost of BitmapSort_2 is : 120000msfile open success!Test SetContainerSort...the time cost of SetContainerSort is : 4027000msfile open success!Test qsort...the time cost of qsort is : 131000msfile open success!请按任意键继续. . .

 

对于其他三种方法，因为空间可以在堆上，待排序数组长度为1000,0000时，内存分配也不会出错，运行结果如下：

the number of integer to sort is : 1000000file open success!Test BitmapSort_2...the time cost of BitmapSort_2 is : 869000msfile open success!Test SetContainerSort...the time cost of SetContainerSort is : 39168000msfile open success!Test qsort...the time cost of qsort is : 2200000msfile open success!请按任意键继续. . .

 

可以看到，BitmapSort_1是最快的，在数组长度为10,0000时，其速度比BitmapSort_2大概快一倍，应该是利用了STL中的bitset的优势，对bit的操作更快；

BitmapSort_2速度次之，qsort更次，而用set容器是最慢的，在数组成都为1000,0000时，性能的差别更为明显。