编程珠玑——磁盘排序算法1

3610阅读　0评论2013-06-07　梦醒潇湘love
分类：C/C++


    终于开始阅读《编程珠玑》这本书了，期待了好久，不知道是翻译的比较晦涩，还是书籍本身就比较难，看起来那叫一个吃力啊，体会到看中文如此费尽，瞬间觉得对不起语文老师了。
    第一章讲述的是一个磁盘排序算法，问题的具体描述如下所示。
    输入：一个最多包含n个正整数的文件，每个数都小于n，其中n = 10 ^ 7。这n个数字没有重复出现，没有其他数据与该整数相关连。
    输出：按升序排列的输入整数的列表。
    约束：最多有（大约）1MB内存空间可用，有充足的磁盘存储空间可用。运行的时间最多几分钟，运行时间为10秒就不需要再继续优化了。

    文中给出了两种解决方法，一种是多路归并排序，另一种是位图法。
方法一：多路归并排序
    题目中的限制为所有正整数都不重复。这表示：
    假设内存空间正好为1MB，那么一次可以读入内容的整数个数为250 000个，那么我们每次读入25000个数字，然后用内存排序方法进行排序，将排序后的结果保存到相应的临时文件中。
     多路归并排序的思路：
    1、第一次遍历文件，读取文件内的第1到第250 000个数字，进行排序，将排序后的正整数存储在临时的磁盘文件filename1.txt中；
    2、第二次遍历文件，读取文件内的第250 001到底500 000个数字，进行排序，将排序后的正整数存储在临时的磁盘文件filename2.txt中；
    ......
    将文件中的整数分别进行排序后，然后使用多路归并排序进行整合，首先读取40个文件中的第一个数字，查找这40个数字中最小的数字，将其输出到结果文件中result.txt中，然后读取该最小的元素对应的文件中的下一个数字，替代其位置，依次进行，最后得到排序号的文件。
    代码如下所示。
  1. //源自:http://www.cnblogs.com/daoluanxiaozi/archive/2012/03/29/2423087.html
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <string>
  5. #include <fstream>
  6. #include <time.h>
  7. using namespace std;

  9. #define MAX 10000        //总数据量，可修改
  10. #define MAX_ONCE 2500 //内存排序MAX_ONCE个数据
  11. #define FILENAME_LEN 20

  13. //range:范围
  14. //num :个数
  15. void Random(int range, int num)
  16. {
  17.     int *a = new int[range];
  18.     int i, j;

  20.     fstream dist_file;

  22.     //初始化随机数种子
  23.     srand((unsigned)time(NULL));
  24.     for(i = 0; i < range; i++)
  25.     {
  26.         a[i] = i + 1;
  27.     }

  29.     //打表预处理
  30.     for(j = 0; j < range; j++)
  31.     {
  32.         int ii = (rand() * RAND_MAX + rand()) % range;
  33.         int jj = (rand() * RAND_MAX + rand()) % range;
  34.         swap(a[ii], a[jj]);
  35.     }//for

  37.     dist_file.open("data.txt", ios::out);

  39.     //写入文件
  40.     for(i = 0; i < num; i++)
  41.     {
  42.         dist_file << a[i] << " ";
  43.     }
  44.     
  45.     //回收
  46.     delete []a;
  47.     dist_file.close();
  48. }

  50. bool comp(int &a, int &b)
  51. {
  52.     return a < b;
  53. }

  55. //index: 文件的下标
  56. char *create_filename(int index)
  57. {
  58.     char *a = new char[FILENAME_LEN];
  59.     sprintf(a, "data %d.txt", index);
  60.     return a;
  61. }

  63. //num：每次读入内存的数据量
  64. void mem_sort(int num)
  65. {
  66.     fstream fs("data.txt",ios::in);
  67.     int temp[MAX_ONCE];        //内存数据暂存
  68.     int file_index = 0;        //文件下标

  70.     int count;                //实际读入内存数据量
  71.     bool eof_flag = false;    //文件末尾标识

  73.     while(!fs.eof())
  74.     {
  75.         count = 0;
  76.         for(int i = 0; i < MAX_ONCE; i++)
  77.         {
  78.             fs >> temp[count];

  80.             //读入一个数据后判断是否到了末尾
  81.             if(fs.peek() == EOF)
  82.             {
  83.                 eof_flag = true;
  84.                 break;
  85.             }//if

  87.             count++;
  88.         }//for

  90.         if(eof_flag)    //如果到达文件末尾
  91.         {
  92.             break;
  93.         }

  95.         //内存排序
  96.         sort(temp, temp + count, comp);
  97.         
  98.         //写入文件
  99.         char *filename = create_filename(++file_index);
  100.         fstream fs_temp(filename, ios::out);
  101.         for(int i = 0; i < count; i++)
  102.         {
  103.             fs_temp << temp[i] << " ";
  104.         }
  105.         fs_temp.close();
  106.         delete []filename;
  107.     }//while
  108.     
  109.     fs.close();
  110. }

  112. void merge_sort(int filecount)
  113. {
  114.     fstream *fs = new fstream[filecount];
  115.     fstream ret("ret.txt", ios::out);

  117.     int index = 1;
  118.     int temp[MAX_ONCE];
  119.     int eofcount = 0;
  120.     bool *eof_flag = new bool[filecount];
  121.     memset(eof_flag, false, filecount * sizeof(bool));

  123.     for(int i = 0; i < filecount; i++)
  124.     {
  125.         fs[i].open(create_filename(index++), ios::in);
  126.     }

  128.     for(int i = 0; i < filecount; i++)
  129.     {
  130.         fs[i] >> temp[i];
  131.     }

  133.     while(eofcount < filecount)
  134.     {
  135.         int j = 0;

  137.         //找到第一个未结束处理的文件
  138.         while(eof_flag[j])
  139.         {
  140.             j++;
  141.         }

  143.         int min = temp[j];
  144.         int fileindex = 0;
  145.         for(int i = j + 1; i < filecount; i++)
  146.         {
  147.             if(temp[i] < min && !eof_flag[i])
  148.             {
  149.                 min = temp[i];
  150.                 fileindex = i;
  151.             }
  152.         }//for

  154.         ret << min << " ";
  155.         fs[fileindex] >> temp[fileindex];

  157.         //末尾判断
  158.         if(fs[fileindex].peek() == EOF)
  159.         {
  160.             eof_flag[fileindex] = true;
  161.             eofcount++;
  162.         }
  163.     }//while

  165.     delete []fs;
  166.     delete []eof_flag;
  167.     ret.close();
  168. }
  169.     
  170. int _tmain(int argc, _TCHAR* argv[])
  171. {
  172.     Random(MAX, MAX);
  173.     clock_t start = clock();
  174.     mem_sort(MAX);
  175.     merge_sort(4);
  176.     clock_t end = clock();
  177.     
  178.     double cost = (end - start) * 1.0 / CLK_TCK;
  179.     cout << "耗时" << cost << "s" << endl;
  180.     return 0;
  181. }
    多路归并的方法需要多次进行磁盘I/O读写，会增加额外的时间开销，总体来说，该方法的时间复杂度比较高。

方法二：位图法
    位图法适合排序、查询、去除重复和判断数组是否存在重复。判断集合中存在重复是常见的编程任务之一，当集合中的数据量比较大时，通常希望少进行几次扫描。
    位图法比较适合这种情况，它的做法是按照集合中最大元素max创建一个长度为max + 1的新数组，然后再次扫原数组，遇到几就给新数组的第几位置上置1，如遇到5就个新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法，故称为位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。
    对于磁盘文件排序这个问题，使用位图法的思路如下所示。
    1、10000 000个正整数所占用的内存空间大约为1MB；
    2、创建有10000 000个位的字符串，并将其每一位初始化为0；
    3、读取包含正整数的文件，对于每一个正整数，将其对应的位置设置为1；
    4、按位顺序读取字符串，当读取到bit[i]为1时，输出i；
    代码如下所示。
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <time.h>
  4. #include <bitset>
  5. using namespace std;

  7. #define DATA_NUM 10000            //生成的随机数的个数
  8. #define SOURCE "data.txt"        //保存随机数的文件名称
  9. #define RESULT     "result.txt"    //保存排序结果的文件名称

  11. //功能：生成随机数文件
  12. //参数：num 生成随机数的个数
  13. void make_data(int num)
  14. {
  15.     int *temp = new int[DATA_NUM];
  16.     if(temp == NULL)
  17.     {
  18.         cout << "new error in make_data()" << endl;
  19.         return;
  20.     }

  22.     for(int i = 0; i < DATA_NUM; i++)
  23.     {
  24.         temp[i] = i + 1;
  25.     }

  27.     for(int i = 0; i < DATA_NUM; i++)
  28.     {
  29.         int ii = (rand() * RAND_MAX + rand()) % DATA_NUM;
  30.         int jj = (rand() * RAND_MAX + rand()) % DATA_NUM;
  31.         swap(temp[ii], temp[jj]);
  32.     }

  34.     //写入文件
  35.     FILE *fp;
  36.     fp = fopen(SOURCE, "w");
  37.     if(fp == NULL)
  38.     {
  39.         cout << "fopen() error in make_data()." << endl;
  40.     }
  41.     for(int i = 0; i < DATA_NUM; i++)
  42.     {
  43.         fprintf(fp, "%d ", temp[i]);
  44.     }
  45.     fclose(fp);
  46.     cout << "随机数文件生成成功." << endl;
  47. }

  49. void BitMapSort()
  50. {
  51.     //这里对这10000个正整数做如下处理：
  52.     //首先对1-5000之内的数进行处理
  53.     //然后对5001-10000之内的数进行处理
  54.     //这样对文件扫描了两遍，增加了时间开销
  55.     //如果数据不是很大的话，那么可以直接处理的，这里为了防止数据过大，进行多次处理

  57.     bitset<DATA_NUM/2 + 2> bitmap;
  58.     bitmap.reset();

  60.     FILE *fpsrc;
  61.     fpsrc = fopen(SOURCE, "r");
  62.     if(fpsrc == NULL)
  63.     {
  64.         cout << "fopen() error in BitMapSort()" << endl;
  65.         return;
  66.     }

  68.     int data;
  69.     while(fscanf(fpsrc, "%d ", &data) != EOF)
  70.     {
  71.         if(data <= DATA_NUM / 2)
  72.         {
  73.             bitmap.set(data, 1);
  74.         }
  75.     }

  77.     //将排序好的数写入到结果文件中
  78.     FILE *fpdst;
  79.     fpdst = fopen(RESULT, "w");
  80.     if(fpdst == NULL)
  81.     {
  82.         cout << "fopen() error in BitMapSort()." << endl;
  83.         return;
  84.     }

  86.     for(int i = 0; i <= DATA_NUM / 2 + 1; i++)
  87.     {
  88.         if(bitmap[i] == 1)
  89.         {
  90.             fprintf(fpdst, "%d ", i);
  91.         }
  92.     }
  93.     
  94.     //处理剩下的数据
  95.     int res = fseek(fpsrc, 0, SEEK_SET);
  96.     if(res)
  97.     {
  98.         cout << "fseek() error in BitMapSet()." << endl;
  99.         return;
  100.     }
  101.     bitmap.reset();
  102.     while(fscanf(fpsrc, "%d ", &data) != EOF)
  103.     {
  104.         if(data <= DATA_NUM && data > DATA_NUM / 2)
  105.         {
  106.             data = data - DATA_NUM / 2;    //注意：开始时出错了
  107.             bitmap.set(data, 1);
  108.         }
  109.     }

  111.     for(int i = 0; i <= DATA_NUM / 2 + 1; i++)
  112.     {
  113.         if(bitmap[i] == 1)
  114.         {
  115.             fprintf(fpdst, "%d ", i + DATA_NUM / 2);
  116.         }
  117.     }
  118.     cout << "排序成功." << endl;
  119.     fclose(fpdst);
  120.     fclose(fpdst);
  121. }


  124. int _tmain(int argc, _TCHAR* argv[])
  125. {
  126.     make_data(DATA_NUM);

  128.     clock_t start = clock();
  129.     BitMapSort();
  130.     clock_t end = clock();

  132.     cout << "排序所用时间为:" << (end - start) * 1.0 / CLK_TCK << "s" << endl;
  133.     return 0;
  134. }
     产生的随机数文件如下所示。
    
    位图排序后的结果如下所示。
    
    程序运行结果如下所示。
    

    
上一篇：从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的
下一篇：编程珠玑——第一章习题解答