读书日记·编程珠玑·第一章

前言

最近在慢慢地读《编程珠玑》这本书，里面的算法比较巧妙、有趣。读的过程中，也是希望自己做一些笔记，一方面帮助自己理解，另一方面可以日后可以快速回顾。也写了一些代码来实现算法，第一章的代码可见github。

直奔问题

书中第一章是讲的这么一个问题：

输入：一个最多包含n正整数的文件，每个数都小于n，其中n为10^7。并且文件中的整数不会有重复。
输出：按照升序排列的输出这些整数。
约束：最多有（大约有）1 MB的内存空间可用，有充足的磁盘空间可用。

我们可以分析出来，这是一个排序问题，内存空间有限。所以一次把数字读到内存中再使用排序算法进行排序行不通啊，得另寻它法。

书中首先提到了两种方法：

多趟排序算法。
基于磁盘文件的归并排序。

以及书后面提到的最优解法，称为位图法。下面容我对这些解决办法徐徐道来。

解决问题

1. 多趟排序算法

在解决问题前，我们首先要做的是理解问题，之后才能想良策啊。

这里因为问题具有一定的特殊性，即它们是不重复的整数，并且最大值为n。每个整数占空间32bit，那么1 MB可以容纳250 000个整数，于是我们可以分40趟来遍历文件中的数字进行排序：

遍历文件排序0至249 000的数字，并写入文件。
遍历文件排序249 000至499 999的数字，并写入文件。
......

依次下去，即可对文件中的数字全部进行排序。

2. 基于磁盘文件的归并排序

归并排序我们都十分熟悉，其用到了分而治之的思想。我们先来熟悉一下它，主要分为了两个过程：

一直拆分下去，直到无法拆分为止。到最后只剩一个元素，只有一个元素当然是有序的。
再对有序的分组二对二的进行往回归并，其归并的过程也十分简单。我们转移到[1,7],[0,2,6]归并那一处,其归并过程如下：

0<1 则 0
1<2 则 0,1
2<7 则 0,1,2
6<7 则 0,1,2,6
最后还剩7 则0,1,2,6,7

图解归并排序过程

哎，上面全是大白话。。。结合图片进行理解哈，问题不大，嘻嘻。回忆完归并排序，我们就进入正题——基于磁盘的归并排序。

我们需要对10^7个不重复的数字进行排序。每个数字占32位，于是1 MB的内存可以存储250000个数字。可以见下图，phoneNumber.txt文件正是存储的待排序的数字。

分四十次，每次从phoneNumber.txt文件中读取250000个数字进行排序，并写入到文件phoneNumber_sort_round1_*.txt文件中。
phoneNumber_sort_round1_0.txt和phoneNumber_sort_round1_1.txt进行归并排序。进行归并排序时，首先向两个文件中各读取一个数字，进行比较并将小的数字写入phoneNumber_sort_round2_0.txt，依次进行下去，最终两个文件会汇合为phoneNumber_sort_round2_0.txt。按照同样的方法，可以生成phoneNumber_sort_round2_*.txt。
同样以步骤2的方法，最后文件会汇合到一个文件phoneNumber_sorted.txt,该文件就是最终的排序结果。

基于磁盘的文件归并排序

位图法

虽然前面的两种方法，都可以达到我们的目标。可是，需要多次对文件进行IO。可见，其并不优秀啊。我们需要一个解决方案，不但能节约内存空间，也能提升排序的时间。

所谓的位图法，我们可以用一个小小例子来进行说明。假设我们现在需要对7,5,2,3,4,0这一串数字进行排序，那么首先申请8 bit的空间，其中其初始状态为：

|--0--|--0--|--0--|--0--|--0--|--0--|--0--|--0--|

第0位即代表数值0, 第1位即代表数值1，第n位即代表数值n......
当bit位为0时，那么表示没有相关的数值；当bit位为1时，代表有相关的数值。

遍历7,5,2,3,4,0，依次将相应的bit位设置为1：

|--1--|--0--|--1--|--1--|--1--|--1--|--0--|--1--|

最后，遍历bit数组，根据第n位即代表数值n，以及1代表有数值的规约，即可输出最后的排序结果：023457。

总结以上排序的步骤：

申请大小合适的bit数组。
遍历待排序数组，将相应bit位设置为1.
遍历bit数组，即可输出最后的排序结果。

可见该方法排序十分高效，可是需要满足的条件是：待排序数组为整数，并且并其中没有重复数字！

补充问题

除了开篇提到的问题之外，书中也补充到了一个问题。

如果那个程序员说的不是每个整数最多出现一次，而是每个整数最多出现10次，那么又该如何解决这个问题呢。

我们只需要调整一下位图法即可解决这个问题，前面的问题我们是第n位即代表数值n。在这里就是每4bit代表一个数值，如下：

|--0--|--0--|--0--|--0--|   |--0--|--0--|--1--|--0--|   |--1--|--0--|--1--|--0--|

上面即代表，数值0未出现，数值1出现了2次，数值2出现了10次。

只要我们按在这个规则来设置结构，最后也可完成排序。

总结

解决问题之前，我们必须得非常熟悉问题，这样才能帮助我们找到最合适的解决方法。另一方面，任何事情没有绝对的一面：这里我们看到了，不一定都是牺牲空间换取时间，或者牺牲时间换取空间。

好把，就介样了，See you !