大数据计算基础——算法部分（上）_外存链表

壹、外存计算模型（I/O模型）

一、一些知识点

        在I/O模型中，主要涉及CPU、内存和外存三部分。内存与外存的数据交换以大小为B的块为单位，在模型中通常认为内存的容量M>，且外存容量近乎无限。

        I/O模型上的算法目标——最小化数据传输量，即内存与外存的块交换量。因为CPU访问外存需先将数据写入内存，慢于访问内存的速度。

        如块大小为B，待传输的数据量为N，则扫描数据的代价为O(N/B)，而不是O(N)。一方面B在不同场景中可能有不同取值，另一方面由于I/O模型中访问外存1次就具有较大的代价，因此B带来的实际影响是不可忽视的，故将其保留。

        下面介绍一些外存上的数据结构。

二. 外存栈

        内存维护大小为2B的数组，存放栈顶的k个元素，k<=2B。

        压栈：若内存数组中数据少于2B，则直接内存压栈；否则往外存写入B个数据，再内存压栈。

        弹栈：若内存数组非空，则内存弹栈；否则从外存读入最新写入的B个数据，再内存弹栈。

        均摊代价（最坏的平均情况）：O(1/B)，相邻的两次I/O之间至少需要B次PUSH或POP操作。

三. 外存队列

        内存维护2个大小为B的数组A和B，一个用于出队，一个用于入队。

        入队：若B未满，则往B入队；否则将B中数据写入外存，再入队。

        出队：若A非空，则从A出队；否则从外存读入最早写入的B个数据，再出队。

        均摊代价（最坏的平均情况）：O(1/B)，相邻的两次I/O之间至少需要B次入队或出队操作。

四. 外存链表

        这里考虑定义在链表上的三种操作——插入节点、删除节点、遍历第k个节点。

4.1 数据结构

        对于外存链表，由于涉及节点的插入和删除，如果每个块中都装满数据，那么这两种操作的代价是很大的。需要指出，外存上的“指针”通过偏移量来表示。

        为了降低I/O次数，一种可能的想法是让块“半满”。每次进行插入删除操作后，若超过块上限，则平均分成两块；若少于一半，则与邻居合并（优先选择能放下的邻居），合并后如超过B则同样进行均分。

4.2 代价分析

        对于遍历操作，最坏的情况是每个块都只有B/2个数据，此时块数最多，一共需要取k/(B/2)=2k/B个块才能找到第k个节点。

        对于N次连续插入操作，平均每B/2次插入操作后发生一次I/O。

        对于N次连续删除操作，则会复杂一些。如下图所示，发生第1次I/O时删去1个节点，第2次删去B/4个节点，第3次删去B/8个节点，如此持续下去，则直到两块都只剩B/2个数据，最多有O()次I/O，平均每次删除操作有O()的代价，故N次删除的平摊代价也可得知。

4.3 2/3满的链表

        如果要求相邻的两个快至少包含2/3B的数据，则代价有所变化。

        此时连续删除的代价会变得简单，每B/3次删除有一次I/O。

五. B+树

        与正常的B+树一致，通常B+树的节点存储在内存，而数据部分存储在外存。

        需要掌握节点的插入、删除、查找过程。

六. 外存排序

        以大小M为一组，共N/M组，每组M/B块。

        每次可以归并M/B个分组，共层，每层代价都是O(N/B)，得到如下的总代价。

贰、亚线性空间算法

一、概述

        在有的场景下，由于数据量太大，即使遍历一遍数据的代价O(N)都是不可承受的，例如路由器。此时需要寻找logN甚至loglogN级别空间复杂度的算法。

 二、近似计数

2.1 流模型

        我们希望在数据流中统计各个值出现的次数，这在普通的场景下是个司空见惯的问题，但在大数据场景下会遇到很大的麻烦。

         若最大值为n，则需要logn的空间复杂度，在n很大的时候这个代价依然很高。为此，可以牺牲一定的准确度，引入概率，求解一定误差范围内的计数结果。

 2.2 Morris算法

         Morris算法过程如下，以一定的概率对计数进行更新。

         其中均值的计算过程如下，方差我也忘记怎么算的了。

                 根据琴生不等式，可以得到此时存储X的空间代价为loglogn。

2.3 Morris+算法

        对Morris算法进行一定的改进，进行k次取平均，能够缩小方差。并通过控制k的取值，可以控制空间代价。

        Morris++算法没听懂，这里就不放出来了。

三、不重复元素数

3.1 FM算法

         设Z为z的随机变量，对Z的均值、方差求解过程如下，利用到了所取的hash函数的性质。

        在均值方差的基础上，进行一定得到放缩，就能够得到如下的不等式（D为X的均值），这表明误差能够控制在一个较小的范围内，即FM算法是有效的。 

3.2 FM+算法

        在FM算法的基础上多次运行，能够得到更小的方差。通过选择合适的次数k，就能控制最后的误差。

         FM++不太懂。

3.3 Pratical FM算法

        前面都是基于我们能够存储实数的假设展开的，事实上计算机只能存储二进制数，没办法精确存储实数。为此进行一定的改进。

        这里选取一个2-相对独立哈希函数进行随机化处理，然后记录最长的后缀0个数。

 ​

        简单分析下均值。

        对于Xrj，代表第j个数的哈希值末尾0个数是否达到r，只要后r位全是0即为1，故概率就是后r位全0的概率，即1/2^r。

        对于Yr，代表哈希值末尾0个数达到r的个数，其均值可以简单理解为D个数中Xrj的总和，故为D*E[X]。

         对定理1.12的证明过程如下，用到了切比雪夫不等式、马尔科夫不等式以及Yr的性质。

 3.4 BJKST算法

        忘了。。。

四、固定大小采样

        这块没听课。

        

 五、Bloom Filter

        成员问题：给定一个元素，欲判断其是否在集合内。

        用哈希表可以实现常数级别的时间复杂度，但空间复杂度较高。解决的办法是进行一定的放松——可错杀，不可放过。确保在集合中的元素都能正确判断出来，不在集合中的元素允许有一定误差。

         若h(i)=1，说明该i的等价类中有元素被选中；若h(i)=0，则i必未被选中。i的等价类中至多n/m个元素，故能控制错误率。

         同时运行k个，能够降低这种错误。