article20201206
大数据 | 大数据基础--算法之外存模型算法：List Ranking
亲爱的读者朋友大家晚上好，上次我们简单介绍了基于外存模型的排序算法，这次我们来介绍另一个有趣的问题\(List\ Ranking\)。
外存模型
到目前为止，按照存储模型，我们学过的算法模型应该分为两种：一种是\(RAM\)模型，也就是我们常用的算法的设计模型，另一种是\(I/O\)模型，内存比数据量小，外存是无限的。
外存访问与内存访问有一些差异：
- 与外存相比，内存的速度更快
- 外存的连续访问比随机访问代价小，也就是说：以块\((block)\)为单位访问，而不是\(elemen\ wise\)
在\(I/O\)模型中，内存的大小为\(M\)，页面大小为\(B\)，外存大小无限，页面大小为\(B\)。
List Ranking
定义
[List Ranking Problem]：给定大小为\(N\)的邻接链表\(L\)，\(L\)存储在数组（连续的外存空间）中，计算每个节点的\(rank\)（在链表中的序号）。
[General List Ranking Problem]：给定大小为\(N\)的邻接链表\(L\)，\(L\)存储在数组（连续的外存空间）中，\(L\)中的每个节点\(v\)上存储权重\(w_v\)，计算每 个节点\(v\)的\(rank\)（从头节点到\(v\)的权重和）。
分析
- 如果合并链表上的子序列为一个节点（也就是页面内部合并，将一个页面当作一个节点），将权重和做为该节点的权重，不影响前后节点的\(rank\) 值。
- 如果链表大小至多为\(M\)，那么利用\(O(M/B)\)次\(I/O\)可解决这个问题，也就是将所有的数据都读入内存，使用内存算法解决这个问题。
我们通过一个图片来看一下对这个问题的直观理解，如下图所示，相关数据为：\(N = 10,B = 2,M = 4\)。最坏的情况下访问代价为\(O(N)\)次\(I/O\) 。
算法
输入大小为\(N\)的外存链表\(L\)
- 寻找\(L\)中的一个顶点独立集 \(X\)
- 将\(X\)中的节点“跳过”，构建新的、更小的外存链表\(L'\)
- 递归地求解\(L'\)
- 将\(X\)中的节点“回填”，根据\(L′\)的\(rank\)构建\(L\)的\(rank\)
第1.2.4步骤都可以在\(O(sort) = O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })\) 次\(I/O\)求解，则构建如下递归方程：
\(T(N) = T((1-\alpha)N) + O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })\)，解方程得：\(T(N) = O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })\)。
step~1
按照节点的ID顺序，分为\(forward(f)\)链表和\(backward(b)\)链表，将\(f\)链表按照\(red,blue\)间隔染色，将\(b\)链表按照\(green,blue\)间隔染色。注意这里的\(f\)链表和\(b\)链表指的是链表的一个连续段，该段内的数据的\(ID\)顺序关系要么全部与内存中的位置一致，要么正好相反。显然，一个链表中有多个\(f\)链表和\(b\)链表。
这一步的实现只需要进行一个外存排序即可实现，因此时间代价为\(O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })\)。
step~2,4
- \(\tilde{L} = copy(L)\)
- 将链表\(L\)按照后继节点的地址排序，排序的同时进行如下操作
- 在step~2，将后继节点属于\(X\)的节点指针和权重重写
- 在step~4，将后继节点属于\(X\)的节点指针和权重重写，将属于\(X\)的节点权重重写
- 将\(L\)重新按照地址排序
总结
以上就是关于外存模型下的\(List\ Ranking\)问题。到这里大数据基础的算法部分就解决了，从下周开始我会对大数据系统进行分析，这部分分为：大数据计算系统和大数据管理系统，敬请期待~