每周学点大数据 | No.28 表排序

No.28期

表排序

Mr. 王：前面我们讨论了一些基础磁盘算法，现在我们来讨论一些关于磁盘中图算法的问题。

通过对基础磁盘算法的学习，我们可以很容易地想到，之所以需要设计外存的图算法，是因为如果内存无法存储全部的数据的话，我们就要尝试将数据存放在外存中；图也是一样的，当需要表示的图很大时，内存无法存下全部的图节点或者边时，我们就要尝试将数据保存在外存中，仅当需要对图的某一部分进行处理时，才加载到内存中来。

图算法的体系是比较庞大的，对图的操作和研究的算法也是非常多的，在开始研究一些比较复杂的图算法之间，我们先来讨论一个基础的算法，叫作“表排序”。

小可：排序？是对一张表里面的数据进行排序吗？用前面的归并排序法可以解决吗？

Mr. 王：这里的排序和前面的不太一样，我们称前面的排序为“sort”，称现在要讲的这种排序为“ranking”。

小可：这个ranking 具体是做什么的呢？

Mr. 王：链表的ranking，求解的是在一个链表中，某个节点到表头节点的距离。

小可：如果是这样的话，那么第一个节点就是1，第二个节点就是2，第n 个节点就是n 呗？

Mr. 王：如果节点没有权值的话，的确是这样的。但是当我们要应用它时，往往情况更加复杂，链表中的每个节点往往都带有一个权值，计算时要带上这个权值。

就比如上面这个图，它的每个节点都带有一个权值，那么第一个节点的ranking 就是3，第二个节点的ranking 就是3+1=4，第三个节点的ranking 就是3+1+5=9……

小可：原来是这样的排序啊，但是也太容易了。我只要从头至尾进行一次扫描，添加一个前面的距离已经达到多少的计数器不就可以了吗？

Mr. 王：没错，如果该链表可以全部放入内存中的话，这个问题确实非常简单，进行一次扫描就可以完成。但是如果这个链表中的节点很多，并且节点很大，每个磁盘块只能容纳几个节点的话，我们就要把这些节点存放在外存中；而且如果节点是随机存储的，也就是它们在磁盘中存放的物理位置与其在链表中的逻辑位置没有明显的关系，情况就会比较复杂。

比如每个磁盘块可以存下4 个节点，内存中可以放置2 个磁盘块，磁盘块上面的数字表示其在链表中的顺序，就像下面的图一样。我们模拟运行一下看看会出现什么样的问题。

第1 步：我们访问节点1，将它所在的1 号磁盘块加载进内存中。

第2 步：我们访问节点2，将2 号磁盘块放进内存中。

第3 步：我们访问节点3，这时内存中存放着1 号和2 号磁盘块，已经被填满，必须换出一些磁盘块，腾出一些内存空间以加载新的磁盘块。假设我们采用先进先出的策略，将1 号磁盘块从内存中删除，然后加载3 号磁盘块。

结果就是：

第4 步：我们访问节点4，内存依然是满的，将2 号磁盘块从内存中删除，然后加载4 号磁盘块。

通过算法的第3 步和第4 步就可以看出，从内存被填满的下一步开始，每一次访问都要调入一个磁盘块并丢弃一个磁盘块。这也意味着每处理一个节点都要进行一次磁盘I/O，如果按照这样的方法访问下去的话，在整个算法的运行过程中，磁盘I/O 的次数已经接近了节点的总量N。也就是说，算法的最坏情况的I/O 数为W(N)。

小可：嗯，这么大的I/O 数肯定会导致程序运行的速度特别慢，用户肯定无法接受。

Mr. 王：现在看来，表排序这个问题并没有那么简单了吧。所以我们需要想一个面向外存的办法来解决这个问题。这里给出一个高效的表排序算法。

这个算法是这样做的：首先，我们取一个独立集，这个独立集的大小至少是N/3。

小可：什么是独立集呢？

Mr. 王：一个图中的独立集，是一些两两之间不存在边的点的集合。独立集怎么获得，我们之后再去讨论。现在假设我们有一种方法来获得这样一个独立集。

比如我们取这样一个链表，找出区中一个独立集为5 和3 这两个节点。然后，去掉独立集中的点，对剩下的这个子链表的ID 进行排序。将排序结果放在连续的磁盘块中，而将独立集中的元素按照其后继节点（也就是它们后面的那个节点）的ID 进行排序，放在一组连续的磁盘块中，这样这两部分都按照ID 有序地放置在连续的磁盘块中了。想想看，这样做有利于接下来进行一个什么样的操作？

小可：两组有序的表，还是整个链表的片段，那么就可以进行归并？

Mr. 王：非常好，的确，这样做的目的就是非常有利于实现归并操作。另外，对独立子集中的部分我们按照其后继节点的ID 进行排序的好处是，方便将它的权值加到其后继节点中。

此时，我们已经将独立集中的节点所带有的5 和3 这两个权值加入到了它们的后继节点2和1 中，这两个节点的权值变成了7 和4。这样我们就得到了一个独立集中的节点被去掉，但却不影响最终ranking 数值结果的链表片段。

现在我们就可以在这样的链表片段中做ranking 操作。求出的结果是：

最后我们再做一个工作，就是把独立集加回来，加回来这个工作就是按照ID 进行归并排序。原来的链表片段中的ranking 已经不用动了，因为我们考虑了独立集中的值，所以它们的值的结果是正确的，此时只需要相应地更新一下独立集里的ranking 就可以了。

这个操作非常简单，只需要将其前驱节点的ranking 加上节点值即可。这样做的好处主要是达到了压缩L 的目的，极大地降低了I/O 复杂度。

内容来源：灯塔大数据