程序员编程艺术（算法卷）：第十章、如何给10^7个数据量的磁盘文件排序

前奏

经过几天的痛苦沉思，最终决定，把原程序员面试题狂想曲系列正式更名为程序员编程艺术系列，同时，狂想曲创作组更名为编程艺术室。之所以要改名，我们考虑到三点：1、为面试服务不能成为我们最终或最主要的目的，2、我更愿把解答一道道面试题，ACM题等各类程序设计题目的过程，当做一种艺术来看待，3、艺术的提炼本身是一个非常非常艰难的过程，但我们乐意接受这个挑战。

同时，本系列程序编程艺术-算法卷，大致分为三个部分：第一部分--程序设计，大凡如面试题目/ACM题目/poj的题目等各类程序设计的题，只要是好的，值得设计或深究的题目，我们都不拒绝。同时，紧扣实际，不断寻找更高效的算法解决实际问题。第二部分--算法研究，主要以我个人此前写的原创作品-十三个经典算法研究系列为题材，力争通俗易懂，详略得当的剖析各类经典的算法，并予以编程实现。第三部分--编码素养，主要包括程序员编码过程中一些编码规范等各类及其需要注意的问题。

如果有可能的话，此TAOPP系列将采取TAOCP那样的形式，出第一卷、第二卷、...。编程艺术来自哪里?编程采取合适的数据结构?寻求更高效的算法?或者，好的编码规范?希望，本TAOPP系列最终能给你一个完整的答复。

ok，如果任何人对本编程艺术系列有任何意见，或发现了本编程艺术系列任何问题，漏洞，bug，欢迎随时提出，我们将虚心接受并感激不尽，以为他人创造更好的价值，更好的服务。

第一节、如何给磁盘文件排序
问题描述：
输入：一个最多含有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），程序可以用伪代码表示如下：
view plaincopy to clipboardprint?
//磁盘文件排序位图方案的伪代码
//copyright@ Jon Bentley
//July、updated，2011.05.29。
//第一步，将所有的位都初始化为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
//磁盘文件排序位图方案的伪代码
//copyright@ Jon Bentley
//July、updated，2011.05.29。
//第一步，将所有的位都初始化为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

上面只是为了简单介绍下位图算法的伪代码之抽象级描述。显然，咱们面对的问题，可不是这么简单。下面，我们试着针对这个要分两趟给磁盘文件排序的具体问题编写完整代码，如下。

view plaincopy to clipboardprint?
//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++)

补充：软件开发 , C语言 ,