编程珠玑-磁盘文件排序

问题

假设现在有一个包含有 5000000（500万）个整数型的数据列表，其中的数据范围为 0 — 9999999，并且无重复数据。现在，我们想对这个列表进行排序，该如何去做呢？

答案似乎很简单，无论是最简单的冒泡排序，选择排序到稍微复杂点的快速排序、归并排序，甚至许多编程语言都内置了相关的排序算法，都能简单的解决这个问题。

那么，如果再加上一点限定条件呢？比如说这些数据存在于磁盘中的一个文件中，我们需要将这个文件内的数据排序后输出到另一个文件中，又该怎么做呢？

我们知道，一个 int 型的数据在绝大多数编程语言中占 4 个字节，即 4B ，那么500万个整型数据就是2千万个字节，大概是 19M，即这个文件的大小大概在 19M 左右。

无论上述的各种排序算法性能如何，都有一个共同的特点：所有的操作都是在内存中完成的。也就是说，我们如果想使用以上所述的排序算法，所做的第一件事便是读取文件，将文件中的所有数据读入到一个内存中，然后再通过以上算法进行排序运算，最后输出到一个文件中。

听起来似乎很简单，我们要做的无非是三步：

1、读取文件，将数据存入一个500万大小的数组中；

2、对这个数组进行排序；

3、将排序后的数组中的数据输出到一个文件中。

本文肯定不会讨论如此简单的问题。那么，让我们再做点有难度的事情。

上面我们计算过，500万个整型数据，需要开辟一个500万大小的整型数组，大概需要 19M 的内存。那么，我们再加一点限定条件：整个系统只有 2M 内存可供使用，也就是说，我们所能使用的内存不能超过 2M。

事情似乎变得有趣起来，我们该如何使用 2M 的内存，来读取大概 19M 的数据，然后对其进行排序呢？

上面我们所说的几种排序算法似乎面对这种情况有些无能为力，那么我们就要思考其他的方法了。

首先我么考虑下， 2M 内存有多大，能够做些什么？

2M 内存，能够存储 524288 个整型数据，即大概52万个数据。显然距离我们的500万个数据规模相差甚远。

既然一次读不完，那么我们是否能够分批对这个文件进行读取处理呢？

我们似乎看到了曙光。500万个数据，我们每次加入只读取50万个数据进行处理，那么只需要10次处理就行了，那还等什么，让我们开始动手吧！

分批排序

首先，我们先创建一个包含500万个不重复的 0 - 9999999 之间的整数列表，并将其写入到一个文本文件中。

sampleList = random.sample(range(0, 9999999), 5000000)
with open("./磁盘排序_sample.txt", "w") as file:
    for i in range(0, len(sampleList)):
        if i < len(sampleList) - 1:
            file.writelines(str(sampleList[i]) + "\n")
        else:
            file.writelines(str(sampleList[i]))

文本内容如下：

现在，让我们开始吧！

batch = [0 for i in range(0,500000)]
with open("./磁盘排序_sample.txt", "r") as read:
    index = 0
    for readLine in read:
        batch[index] = int(readLine)
        index += 1
        if index == len(batch):
            with open("./磁盘排序_sorted.txt", "a") as write:
                batch.sort()
                for i in range(0, len(batch)):
                    write.writelines(str(batch[i]) + "\n")
            index = 0

让我们打开排序后的文本文件看一下内容：

似乎看起来成功了！

等一下，我们再详细看一下文本：

情况似乎有些不对，让我们来分析下我们这个方法：

通过示意图，我们可以看到：我们将样本数据分为 10 个 batch 来处理，对每个 batch 进行排序后输出到文件中去，我们只能保证的是，在样本数据的 10 个 batch 中的每个 batch 内部，数据是有序的，也就是说，batch1 中的数据是有序的，batch2 中的数据也是有序的，但是，batch1 和 batch2 内的数据是有序的吗？

并不是，因为我们的排序的数据只局限于每个 batch 中，batch 之间并没有进行过排序操作，因此无法保证分批处理后，得到的所有数据都是有序的。

这个方法失败了，似乎分批的想法行不通，那么该怎么办呢？

别急，我们换个角度思考。让我们再审一边问题：

假设现在有一个包含有 5000000（500万）个整数型的数据列表，其中的数据范围为 0 — 9999999，并且无重复数据。现在，我们想对这个列表进行排序，并且使用的内存不能超过 2M，该如何去做呢？

既然将数据分批的思路行不通，那么我们是否能够将样本数据的数据范围进行分批操作呢？

由问题可知，样本数据的范围是 0 — 9999999，即样本中的每个数据都是1000万内的数字，我们可以使用的内存是 2M ，大概能够记录 50 万个数据。现在，我们把 0—9999999 ，分成 0—499999，500000—999999 …… 9500000—9999999，共20组，我们每次只读取样本数据中的一组数值范围内的数据，并进行排序操作，然后写入文件中去，如下所示：

batchSize = 500000
batch = [0 for i in range(0, batchSize)]
batchCount = int(10000000 / batchSize)
for i in range(0, batchCount):
    low = i * batchSize
    height = low + batchSize
    index = 0
    with open("./磁盘排序_sample.txt", "r") as read:
        for line in read:
            if int(line) >= low and int(line) < height:
                batch[index] = int(line)
                index += 1
    with open("./磁盘排序_sorted.txt", "a") as write:
        for value in sorted(batch[0 : index]):
            write.writelines(str(value) + "\n")

看一下运算结果：

可以看到，这个方法成功得在限定条件内完成了对样本数据的排序。

那么，我们看一下这个方法的运行消耗：

我们可以看到，500万个样本数据，总共读取了20次，相当于总共在磁盘中读取了20 x 500万，即1亿个数据。我们知道，电脑对磁盘的读写速度是远不如对内存读写的速度的。虽然我们成功将数据进行了排序，但是其运行速度十分缓慢，绝大部份时间都消耗在对磁盘数据的读写。

那么，还有没有更好的方法（更快的方法）完成对磁盘文件的读写呢？让我们继续往下看。

位向量

我们设想一种方法，能够最少次数地读取样本文件，能够最少次数的写入结果文件，同时，其排序部分有尽量小的耗时。

我们再观察一遍问题：

假设现在有一个包含有 5000000（500万）个整数型的数据列表，其中的数据范围为 0 — 9999999，并且无重复数据。现在，我们想对这个列表进行排序，并且使用的内存不能超过 2M，该如何去做呢？

我们之前所关注的重点是：

1、500万个整型数据；

2、数据分布范围为 0 —9999999；

3、内存不能超过 2M。

我们似乎忽略了一个重要的点：

> 1、无重复数据

这个要点能否帮助我们完成我们期待的算法呢？

我们来看一个简单的例子，假如我们有一组数据：

0 ，9，4，7，3

我们该如何将这组数据通过一种简单的方法进行排序呢？

假如我们有10个桶，每个桶只有两种状态：空和满，给这十个桶写上编号，分别是 0 ，1 ，2 …… 9:

现在，10个桶都是空的，我们把这组数据按照其元素的值的大小，放入编号与值相同的桶中，如 9 放入编号为 9 的桶里，3 放入编号为 3 的桶里。

现在，我们的10个桶里总共有5个桶是满的，我们只要从头遍历这10个桶，遇到满的桶就将其编号记录下来：

0 ，3 ，4 ，7 ，9

我们似乎已经得到了排序好的数据。那么，我们是否能用这个方法来解决我们最初的问题呢？

首先，我们来分析一下上面方法能够使用的条件：

1、要有足够多的桶（桶的编号要能包含样本数据中所有元素的可能值）；

2、样本数据不重复；

我们来看我们的题目是否满足以上两点要求：

1、要有足够多的桶：

我们的样本数据范围是 0 — 9999999 ，那么我们就需要 1000万个桶，假如我们定义一个 int 型数组来当作桶，那么这个数组的大小应该是 int a[10000000]；很容易算出来，a 的大小应该是 10000000 x 4 / 1024 /1024 = 38.15M ，但是我们能够使用的内存只有 2M，不满足条件。

2、数据不重复：

由题目可知，我们的样本数据无重复数据，因此是满足条件的。

似乎又陷入了僵局，还是内存大小不满足条件，那我们真的没有别的办法了吗？

等一下，我们知道，一个 int 型数据占 4 个字节，而一个字节是 8 个比特位，我们能否用一个比特位来当作一个桶呢？

稍微计算一下，1000万个桶就是1000万个比特位 = 1.2M，比问题中要求的要小，似乎是可行的！

我们来尝试一下（1000万比特位是 312500 个 int 型数组的大小）：

bucketCount = 312500
buckets = [0 for i in range(0, bucketCount)]
with open("./磁盘排序_sample.txt", "r") as read:
    for line in read:
        bucketIndex = int(int(line) / 32)
        byteIndex = int(line) % 32
        buckets[bucketIndex] = buckets[bucketIndex] | (1 << byteIndex)
        
with open("./磁盘排序_sorted.txt", "a") as write:
    for i in range(0, bucketCount):
        for j in range(0, 32):
            if buckets[i] & (1 << j) != 0:
                write.writelines(str(i * 32 + j) + "\n")

查看运行结果：

成功！

引申1

如果我们再加一个限定条件，所使用内存不能超过 1M，那我们这个算法还适用吗？

答案显而易见，我们想要使用这个算法，最少需要使用大概 1.2M 的内存空间，因此这个算法就不能适用了。那我们该怎么办呢？

会想下我们最开始的做法，我们只要将样本数据的数据范围 0—9999999 分为两批：

0—4999999

5000000—9999999

然后将这两种算法相结合，便能满足我们的需求。

引申2

如果样本数据中的数据是可以重复的，但是每个数据的重复次数不超过10次，那么这个算法还能适用吗？

这种情况下，我们只需要将算法进行稍微的变动。我们原本的做法是将 1 个比特位当作一个桶，现在，我们将 4 个比特位当作一个桶，那么，一个桶的状态便有 16 种情况，即一个桶可以表示 0—15 的数据，我们只要将重复的数据塞到同一个桶里，同时，这个桶通过其本身的 4 比特位进行计数。读取完毕后，再反过来遍历桶，便能达到我们的目的。

如果将 4b 当作一个桶，我们需要的内存大概是 4.7M，超出了 2M 的内存大小，这事，我们便可以将样本数据的范围进行分批处理，同样能够满足问题的要求。