“设计者确定其设计已经达到了完美的标准不是不能再添加任何问题,而是不能再减少任何问题”,程序员应该以此为标准。。。 怎样给一个磁盘文件排序? 问题描述: 输入:一个最多含有n个不相同的正整数的文件,其中每个数都小于等于n,且n=10^7。 分析如下:如何在1MB的空间里对10000000个整数进行排序?而且每个数都小于10000000。实际上这个需要1.25MB的内存空间(此时考虑的是用位图表示法时,每一位代表一个数,那么10000000/(1024*1024*8))≈1.25MB)。1MB有1024*8=8192位,所以应该可以在1MB内存范围内进行排序。下面提出两种方法: (1)基于磁盘的归并排序 归并排序属于外部排序。外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装人内存的部分,分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行归并排序。 内存空间只给了1MB,如果使用归并排序,内存不够。。所以行不通。(耗时间) 每个号码采用32位整数存储的话,1MB大约可以存储250 000 个号码,需要读取文件40趟才能把全部整数排序。(耗时间) (2)位图或位向量 采用一个1千万位的字符串表示每个数,比如{0,2,3}表示为 1 0 1 1 0 0 0 0 。(说明:左边第一位表示 0 第二位表示1 第三位表示 2 。如果有则表示为1,否则为0)遍历每一个整数,有则标记为1,否则标记为0。然后按顺序输出每个整数。这种方法实际需要1.25MB内存,如果可以方便弄到内存的话可以采用此种方法。 参考《编程珠玑》一书上的位图方案,针对10^7个数据量的磁盘文件排序问题,可以这么考虑,由于每个7位十进制整数表示一个小于1000万的整数。可以使用一个具有1000万个位的字符串来表示这个文件,其中,当且仅当整数i在文件中存在时,第i位为1。采取这个位图的方案是因为我们面对的这个问题的特殊性:1、输入数据限制在相对较小的范围内,2、数据没有重复,3、其中的每条记录都是单一的正整数,没有任何其它与之关联的数据。所以,此问题用位图的方案分为以下三步进行解决: 第一步,将所有的位都置为0,从而将集合初始化为空。 //第一步,将所有的位都初始化为0 for i ={0,....n} bit[i]=0; //第二步,通过读入文件中的每个整数来建立集合,将每个对应的位都置为1。 for each i in the input file bit[i]=1; //第三步,检验每一位,如果该位为1,就输出对应的整数。 for i={0...n} if bit[i]==1 write i on the output file 不过很快,我们就将意识到,用此位图方法,严格说来还是不太行,空间消耗10^7/8还是大于1M(1M=1024*1024空间,小于10^7/8)。 既然如果用位图方案的话,我们需要约1.25MB(若每条记录是8位的正整数的话,则10000000/(1024*1024*8) ~= 1.2M)的空间,而现在只有1MB的可用存储空间,那么究竟该作何处理呢?可以多次使用位图进行排序。 假如严格限制为1MB,可以采用的策略:两次遍历或者除去第一位为0或1的整数。 #include <stdio.h> #include <stdlib.h> #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 + N/32]; void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); } void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); } int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); } int main() { int i = 0; //int top = 1 + N/BITSPERWORD; //memset(a, 0, sizeof(a)*sizeof(int)); while (scanf("%d", &i)) set(i); for (i = 0; i < N; i++) if (test(i)) printf("%d\n", i); return 0; } #include <stdio.h> #include <string> #include <time.h> #define MAX 10000000 #define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F int a[1 + MAX / BITSPERWORD]; void clr(int i){a[i>>SHIFT] &= ~(1<<(i & MASK));} void set(int i){a[i>>SHIFT] |= (1<<(i & MASK));} int test(int i){return a[i>>SHIFT] & (1<<(i & MASK));} int main() { int i; for (i = 0; i < MAX; i++) { //clear bit number to 0 clr(i); } char line[10]; FILE *fp; time_t startTime = clock(); time_t endTime; fp = fopen("number.txt", "r"); if (fp) { while (fgets(line,10,fp) != NULL) { i = atoi(line); set(i); } } for (i = 0; i < MAX; i++) { if(test(i)) { printf("%d\n",i); } } endTime = clock(); printf("Total time : %d",endTime - startTime); getchar(); return 0; }
即多路归并:把这个文件分为若干大小的几块,然后分别对每一块进行排序,最后完成整个过程的排序。k趟算法可以在kn的时间开销内和n/k的空间开销内完成对最多n个小于n的无重复正整数的排序。比如可分为2块(k=2,1趟反正占用的内存只有1.25/2=0.625M),1~4999999,和5000000~9999999先遍历一趟,处理1~4999999的数据块(用5000000/8=625000个字的存储空间来排序0~4999999之间的整数),然后再第二趟,对5000001~1000000这一数据块处理。 针对这个要分两趟给磁盘文件排序的具体问题编写完整代码,如下: //copyright@ yansha //July、2010.05.30。 //位图方案解决10^7个数据量的文件的排序问题 //如果有重复的数据,那么只能显示其中一个 其他的将被忽略 #include <iostream> #include <bitset> #include <assert.h> #include <time.h> using namespace std; const int max_each_scan = 5000000; int main() { clock_t begin = clock(); bitset<max_each_scan> bit_map; bit_map.reset(); // open the file with the unsorted data FILE *fp_unsort_file = fopen("data.txt", "r"); assert(fp_unsort_file); int num; // the first time scan to sort the data between 0 - 4999999 while (fscanf(fp_unsort_file, "%d ", &num) != EOF) { if (num < max_each_scan) bit_map.set(num, 1); } FILE *fp_sort_file = fopen("sort.txt", "w"); assert(fp_sort_file); int i; // write the sorted data into file for (i = 0; i < max_each_scan; i++) { if (bit_map[i] == 1) fprintf(fp_sort_file, "%d ", i); } // the second time scan to sort the data between 5000000 - 9999999 int result = fseek(fp_unsort_file, 0, SEEK_SET); if (result) cout << "fseek failed!" << endl; else { bit_map.reset(); while (fscanf(fp_unsort_file, "%d ", &num) != EOF) { if (num >= max_each_scan && num < 10000000) { num -= max_each_scan; bit_map.set(num, 1); } } for (i = 0; i < max_each_scan; i++) { if (bit_map[i] == 1) fprintf(fp_sort_file, "%d ", i + max_each_scan); } } clock_t end = clock(); cout<<"用位图的方法,耗时:"<<endl; cout << (end - begin) / CLK_TCK << "s" << endl; fclose(fp_sort_file); fclose(fp_unsort_file); return 0; } 述的位图方案,共需要扫描输入数据两次,具体执行步骤如下: 磁盘文件排序的C实现 1、内排序 2、多路归并排序 完整代码如下: //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; } 测试数据:生成1000万个不重复的正整数 //生成随机的不重复的测试数据 #include <iostream> #include <time.h> #include <assert.h> using namespace std; //产生[l,u]区间的随机数 int randint(int l, int u) { return l+(RAND_MAX*rand()+rand())%(u-l+1); } //1000W的int,大约4M的数据,如果放在mian内,在我的机子上好像是栈溢出了,放在全局空间就没问题 const int size = 10000000; int num[size]; int main() { int i, j; FILE *fp = fopen("data.txt", "w"); assert(fp); for (i = 0; i < size; i++) num[i] = i+1; srand((unsigned)time(NULL)); for (i = 0; i < size; i++) { j = randint(i, size-1); int t = num[i]; num[i] = num[j]; num[j] = t; //swap(num[i], num[j]); } for (i = 0; i < size; i++) fprintf(fp, "%d ", num[i]); fclose(fp); return 0; } 代码说明
|
|