首页 > 代码库 > 如何给10^7个数据量的磁盘文件排序

如何给10^7个数据量的磁盘文件排序

2024-07-11 19:15:01   219人阅读

题目：

输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
分析：

    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。

    说明：使用bitset方法必须满足的条件是：不能有重复的数字

 
具体看 http://blog.csdn.net/v_JULY_v/article/details/6451990
#include <assert.h>#include <bitset>#include <iostream>using namespace std;const int maxEachScan = 5000000;const int maxSortNumber = 10000000;void SortBigNumber(){    FILE *fp_unSortFile = fopen("d:\\unSort_data.txt","r+");    FILE *fp_SortFile = fopen("d:\\sort_data.txt", "w+");    assert(fp_unSortFile);    bitset<maxEachScan> bit_map;        //因为数据比较大，分成两次执行,这里相当于定义了一个数组来保存所有结果    bit_map.reset();                                   //置0    int num;    /*第一遍遍历*/    while (fscanf(fp_unSortFile,"%d",&num)!=EOF)    {        if (num < maxEachScan)            bit_map.set(num, 1);                //bitset内部机制,保存在bit_map中    }        for (int i = 0; i < maxEachScan; i++)   //遍历bit_map    {        if (bit_map[i] == 1)            fprintf(fp_SortFile, "%d", i);      //这里就是将数据用bit保存（放在bitmap中），再输出的时候输出其对应的数字        }    /*第二遍遍历*/    bit_map.reset();    fseek(fp_unSortFile,0,SEEK_SET);  //移到文本的开头    while (fscanf(fp_unSortFile,"%d",&num)!=EOF)    {        if (num >= maxEachScan&&num < maxSortNumber)            bit_map.set(num-maxEachScan, 1);     }    for (int i = 0; i < maxEachScan; i++)    {        if (bit_map[i] == 1)            fscanf(fp_SortFile,"%d",i+maxEachScan);    }    fclose(fp_unSortFile);    fclose(fp_SortFile);}

 

 

需要用到的函数：
1.fseek： 用来将指针移到指定位置，本代码主要是移动到文本开头，进行第二次扫描
2.bitset 容器
  bitset:: reset   用来将bit位全部置0
 
  bitset:: set  给bit位置设置0或者1 来表示这个bit有没有元素
// bitset::set#include<iostream>// std::cout#include<bitset>// std::bitsetint main (){std::bitset<4> foo;std::cout << foo.set()<<‘\n‘;// 1111std::cout << foo.set(2,0)<<‘\n‘;// 1011std::cout << foo.set(2)<<‘\n‘;// 1111return0;}Edit&RunOutput:111110111111

 

3.文件的读取
 
fscanf(fp_unSortFile,"%d",&num)!=EOF %d可以限定我们读取的是int类型EOF判断文件尾部
 
 参考：http://blog.csdn.net/v_JULY_v/article/details/6451990
来自为知笔记(Wiz)


联系
我们