怎样给一个磁盘文件排序？

一位程序员曾问我一个很简单的问题：“怎样给一个磁盘文件排序？”想当年我是一上来就犯了错误，现在，在讲这个故事之前，先给大家一个机会，看看能否比我当年做得更好。你会怎样回答上述问题呢？

一次友好的对话

我错就错在马上回答了这个问题。我告诉他一些有关如何在磁盘上实现归并排序的简要思路。我建议他深入研究算法教材，他似乎不太感冒。他更关心如何解决这个问题，而不是深入学习。于是我告诉他在一本流行的程序设计书里有磁盘排序的程序。那个程序有大约200行代码和十几个函数，我估计他最多需要一周时间来实现和测试该代码。

我以为已经解决了他的问题，但是他的踌躇使我返回到了正确的轨道上。其后就有了下面的对话，楷体部分是我的问题。

为什么非要自己编写排序程序呢？为什么不用系统提供的排序功能呢？

我需要在一个大系统中排序。由于不明的技术原因，我不能使用系统中的文件排序程序。

需要排序的内容是什么？文件中有多少条记录？每条记录的格式是什么？

文件最多包含1千万条记录，每条记录都是7位的整数。

等一下，既然文件这么小，何必非要在磁盘上进行排序呢？为什么不在内存里进行排序呢？

尽管机器有许多兆字节的内存，但排序功能只是大系统中的一部分，所以，估计到时只有1 MB的内存可用。

你还能告诉我其他一些与记录相关的信息吗？

每条记录都是7位的正整数，再无其他相关数据。每个整数最多只出现一次。

这番对话让问题更明确了。在美国，电话号码由3位“区号”后再跟7位数字组成。拨打含“免费”区号800（当时只有这一个号码）的电话是不收费的。实际的免费电话号码数据库包含大量的信息：免费电话号码、呼叫实际中转到的号码（有时是几个号码，这时需要一些规则来决定哪些呼叫在什么时间中转到哪里）、主叫用户的姓名和地址等。

这位程序员正在开发这类数据库的处理系统的一小部分，需要排序的整数就是免费电话号码。输入文件是电话号码的列表（已删除所有其他信息），号码重复出现算出错。期望的输出文件是以升序排列的电话号码列表。应用背景同时定义了相应的性能需求。当与系统的会话时间较长时，用户大约每小时请求一次有序文件，并且在排序未完成之前什么都干不了。因此，排序最多只允许执行几分钟，10秒钟是比较理想的运行时间。

准确的问题描述

对程序员来说，这些需求加起来就是：“如何给磁盘文件排序？”在试图解决这个问题之前，先将已知条件组织成一种更客观、更易用的形式。

输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。

输出：按升序排列的输入整数的列表。

约束：最多有（大约）1 MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。

请花上一分钟思考一下该问题的规范说明。现在你打算给程序员什么样的建议呢？

程序设计

显而易见的方法是以一般的基于磁盘的归并排序程序为起点，但是要对其进行调整，因为我们是对整数进行排序。这样就可以将原来的200行程序减少为几十行，同时也使得程序运行得更快，但是完成程序并使之运行可能仍然需要几天的时间。

另一种解决方案更多地利用了该排序问题的特殊性。如果每个号码都使用7个字节来存储，那么在可用的1 MB存储空间里大约可以存143 000个号码。如果每个号码都使用32位整数来表示的话，在1 MB存储空间里就可以存储250 000个号码。因此，可以使用遍历输入文件40趟的程序来完成排序。在第一趟遍历中，将0至249 999之间的任何整数都读入内存，并对这（最多）250 000个整数进行排序，然后写到输出文件中。第二趟遍历排序250 000至499 999之间的整数，依此类推，到第40趟遍历的时候对9 750 000至9 999 999之间的整数进行排序。对内存中的排序来说，快速排序会相当高效，而且仅仅需要20行代码（见第11章）。于是，整个程序就可以通过一两页纸的代码实现。该程序拥有所期望的特性——不必考虑使用中间磁盘文件；但是，为此所付出的代价是要读取输入文件40次。

归并排序读入输入文件一次，然后在工作文件的帮助下完成排序并写入输出文件一次。工作文件需要多次读写。

40趟算法读入输入文件多次，写输出文件仅一次，不使用中间文件。

下图所示的方案更可取。我们结合上述两种方法的优点，读输入文件仅一次，且不使用中间文件。

只有在输入文件中的所有整数都可以在可用的1 MB内存中表示的时候才能够实现该方案。于是问题就归结为是否能够用大约800万个可用位来表示最多1 000万个互异的整数。考虑一种合适的表示方式。

实现概要

由是观之，应该用位图或位向量表示集合。可用一个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。

在我们的实际问题中，每个7位十进制整数表示一个小于1 000万的整数。我们使用一个具有1 000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。（那个程序员后来找到了200万个稀疏位，习题5研究了最大存储空间严格限制为1 MB的情况。）这种表示利用了该问题的三个在排序问题中不常见的属性：输入数据限制在相对较小的范围内；数据没有重复；而且对于每条记录而言，除了单一整数外，没有任何其他关联数据。

若给定表示文件中整数集合的位图数据结构，则可以分三个自然阶段来编写程序。第一阶段将所有的位都置为0，从而将集合初始化为空。第二阶段通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。第三阶段检验每一位，如果该位为1，就输出对应的整数，由此产生有序的输出文件。令n为位向量中的位数（在本例中为10 000 000），程序可以使用伪代码表示如下：

/* phase 1: initialize set to empty */
    for i = [0, n)
        bit[i] = 0/* phase 2: insert present elements into the set */
    for each i in the input file
        bit[i] = 1/* phase 3: write sorted output */
    for i = [0, n)        if bit[i] == 1
            write i on the output file

（回想在前言中所提到的，for i=[0, n)表示在从0至n-1的范围内对i进行迭代。）

这个实现概要已经足以解决那个程序员的问题了。

那个程序员打电话把他的问题告诉我，然后我们花了大约一刻钟时间明确了问题所在，并找到了位图解决方案。他花了几个小时来实现这个几十行代码的程序。该程序远远优于我们在电话刚开始时所担心的需要花费一周时间编写的几百行代码的那个程序。而且程序执行得很快：磁盘上的归并排序可能需要许多分钟的时间，该程序所需的时间只比读取输入和写入输出所需的时间多一点点——大约10秒钟。

从这些事实中可以总结出该实例研究所得到的第一个结论：对小问题的仔细分析有时可以得到明显的实际益处。在该实例中，几分钟的仔细研究可以大幅削减代码的长度、程序员时间和程序运行时间。Chuck Yeager将军（第一个超音速飞行的人）赞扬一架飞机的机械系统时用的词是“结构简单、部件很少、易于维护、非常坚固”，该程序拥有同样的属性。

本文节选自《编程珠玑（第2版•修订版）》

内容简介

本书是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley以其独有的洞察力和创造力，引导读者理解这些问题并学会解决方法，而这些正是程序员实际编程生涯中至关重要的。本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序，对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述，为复杂的编程问题提供了清晰而完备的解决思路。本书对各个层次的程序员都具有很高的阅读价值。

本文转载自异步社区。

原文链接：https://www.epubit.com/articleDetails?id=NC7E3EF92F2600001FE90CAC0F75014F5