磁盘文件排序问题
如何给磁盘文件排序
问题描述：
输入：一个最多含有n个不相同的正整数的文件，其中每个数都小于等于n，且n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。
分析：下面咱们来一步一步的解决这个问题，
1、归并排序。你可能会想到把磁盘文件进行归并排序，但题目要求中，你只有1MB的内存空间可用，所以，归并排序这个方法不行。
2、位图方案。熟悉位图的朋友可能会想到用位图来表示这个文件集合。例如正如编程珠玑一书上所述，用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，边框用如下字符串来表示集合{1,2,3,5,8,13}：
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
上述集合中各数对应的位置则置1，没有对应的数的位置则置0。
参考编程珠玑一书上的位图方案，针对我们的10^7个数据量的磁盘文件排序问题，我们可以这么考虑，由于每个7位十进制整数表示一个小于1000万的整数。我们可以使用一个具有1000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。采取这个位图的方案是因为我们面对的这个问题的特殊性：1、输入数据限制在相对较小的范围内，2、数据没有重复，3、其中的每条记录都是单一的整数，没有任何其它与之关联的数据。
所以，此问题用位图的方案分为以下三步进行解决：
第一步，将所有的位都置为0，从而将集合初始化为空。
第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。
第三步，检验每一位，如果该位为1，就输出对应的整数。
经过以上三步后，产生有序的输出文件。令n为位图向量中的位数（本例中为1000 0000），程序可以用伪代码表示如下：
//copyright@ yansha//July、updated，2011.05.28。#include <iostream>#include <string>#include <algorithm>#include <time.h>using namespace std;int sort_num = 10000000;int memory_size = 250000; //每次只对250k个小数据量进行排序int read_data(FILE *fp, int *space){int index = 0;while (index < memory_size && fscanf(fp, "%d ", &space[index]) != EOF)index++;return index;}void write_data(FILE *fp, int *space, int num){int index = 0;while (index < num){fprintf(fp, "%d ", space[index]);index++;}}// check the file pointer whether valid or not.void check_fp(FILE *fp){if (fp == NULL){cout << "The file pointer is invalid!" << endl;exit(1);}}int compare(const void *first_num, const void *second_num){return *(int *)first_num - *(int *)second_num;}string new_file_name(int n){char file_name[20];sprintf(file_name, "data%d.txt", n);return file_name;}int memory_sort(){// open the target file.FILE *fp_in_file = fopen("data.txt", "r");check_fp(fp_in_file);int counter = 0;while (true){// allocate space to store data read from file.int *space = new int[memory_size];int num = read_data(fp_in_file, space);// the memory sort have finished if not numbers any more.if (num == 0)break;// quick sort.qsort(space, num, sizeof(int), compare);// create a new auxiliary file name.string file_name = new_file_name(++counter);FILE *fp_aux_file = fopen(file_name.c_str(), "w");check_fp(fp_aux_file);// write the orderly numbers into auxiliary file.write_data(fp_aux_file, space, num);fclose(fp_aux_file);delete []space;}fclose(fp_in_file);// return the number of auxiliary files.return counter;}void merge_sort(int file_num){if (file_num <= 0)return;// create a new file to store result.FILE *fp_out_file = fopen("result.txt", "w");check_fp(fp_out_file);// allocate a array to store the file pointer.FILE **fp_array = new FILE *[file_num];int i;for (i = 0; i < file_num; i++){string file_name = new_file_name(i + 1);fp_array[i] = fopen(file_name.c_str(), "r");check_fp(fp_array[i]);}int *first_data = new int[file_num]; //new出个大小为0.1亿/250k数组，由指针first_data指示数组首地址bool *finish = new bool[file_num];memset(finish, false, sizeof(bool) * file_num);// read the first number of every auxiliary file.for (i = 0; i < file_num; i++)fscanf(fp_array[i], "%d ", &first_data[i]);while (true){int index = 0;while (index < file_num && finish[index])index++;// the finish condition of the merge sort.//要保证所有文件都读完，必须使得finish[0]...finish[40]都为真if (index >= file_num)break;int min_data = first_data[index];// choose the relative minimum in the array of first_data.for (i = index + 1; i < file_num; i++){if (min_data > first_data[i] && !finish[i]) //一旦发现比min_data更小的数据first_data[i]{min_data = first_data[i]; //则置min_data<-first_data[i]index = i; //把下标i 赋给index。}}// write the orderly result to file.fprintf(fp_out_file, "%d ", min_data);if (fscanf(fp_array[index], "%d ", &first_data[index]) == EOF)finish[index] = true;}fclose(fp_out_file);delete []finish;delete []first_data;for (i = 0; i < file_num; i++)fclose(fp_array[i]);delete [] fp_array;}int main(){clock_t start_memory_sort = clock();int aux_file_num = memory_sort();clock_t end_memory_sort = clock();cout << "The time needs in memory sort: " << end_memory_sort - start_memory_sort << endl;clock_t start_merge_sort = clock();merge_sort(aux_file_num);clock_t end_merge_sort = clock();cout << "The time needs in merge sort: " << end_merge_sort - start_merge_sort << endl;system("pause");return 0;}其中，生成数据文件data.txt的代码如下：//purpose:生成测试数据//copyright@ 2011.04.19 yansha#include <iostream>#include <time.h>#include <assert.h>using namespace std;int main(){int n;cin >> n;FILE *fp = fopen("data.txt", "w");assert(fp);srand((unsigned)time(NULL));while (n--)fprintf(fp, "%d ", (rand() * RAND_MAX + rand()) % 10000000);fclose(fp);return 0;}