大数据笔记-外存算法

时间:2022-07-15 09:52:02

4.1外存存储结构与外存算法

分层存储:

大数据笔记-外存算法

大数据笔记-外存算法

大数据笔记-外存算法

做法

大数据笔记-外存算法

可扩展性问题:若程序分散地访问磁盘上的数据,即使是好的操作系统也无法利用数据块存取优势

大数据笔记-外存算法

基本界限:

大数据笔记-外存算法

队列和堆栈:

大数据笔记-外存算法

4.2外存算法示例:外存排序算法

大数据笔记-外存算法

算法的分析1:(多路归并)

M/B路

以块为单位进行调度

1.首先从磁盘里把磁盘块放进内存,在内存中进行排序,每次放M/B块,一共放N/B块。做完后,外存中已经是在大小为M/B的区域里、分别排好序的数据。再分别取M/B-1个这些区域的第一个元素,放入内存中。

2.在内存中,将M/B-1块用于磁盘块的归并,剩余的一块用作缓存

do{

  step1.[取出]M/B-1块中最小的数据,放于缓存中

  step2.(用于缓存的磁盘块未满,step1)||(缓存满后,写出到外存,清空缓存)||(前M/B-1个磁盘块中的数据被取完,加载相应区域的下一个磁盘块)

}while(将所有的磁盘块中的数据都进行了排序)

疑问:如果step1中,排序磁盘块的次数大于M/B-1,那么归并排序时应该怎么做?

(演示的例子里,在内存中排序磁盘块的次数=M/B-1=3)

 

循环停止条件:(k-1代表第k轮)

大数据笔记-外存算法

大数据笔记-外存算法

算法分析2:(快排)

根号(M/B)路

大数据笔记-外存算法

 

M=8,N=24,B=2

(8,16是选择的分点,buffer磁盘块的大小为B,buffer满了以后,将里面的数据写到外存)

大数据笔记-外存算法

此时,写出到外存的三个区域的元素还没进行排序,但是大小已经可以放进内存,接下来将数据放进内存进行排序。若大小仍不能放进内存,则继续上述做法,直到数据块的大小可以放进内存。

复杂度分析:

划分停止条件:

大数据笔记-外存算法

大数据笔记-外存算法

计算分割元素:

大数据笔记-外存算法

存在的问题:大数据笔记-外存算法

解决方法:

大数据笔记-外存算法

改进的算法的步骤:

大数据笔记-外存算法

大数据笔记-外存算法

大数据笔记-外存算法

从而得到每一路归并的元素上限。

 

算法复杂性分析:

大数据笔记-外存算法

其中,步骤二经过根号(M/B)次抽取分割元素,在4N/根号(M/B)的数据(第一次的抽样的结果)内抽取

总结:

大数据笔记-外存算法

它们都是最优的。

 

4.3外存数据结构示例:外存查找树

内存查找树:

大数据笔记-外存算法

外存查找树:

大数据笔记-外存算法

外部搜索树:

大数据笔记-外存算法

存在的问题:使用红黑树维护BFS块

大数据笔记-外存算法

5.1B树

大数据笔记-外存算法

B树上的查询:

大数据笔记-外存算法

为符合需求,B树应该满足的性质:

(a,b)树

大数据笔记-外存算法

“所有的叶子在同一层并且包括a到b个元素”:叶子节点的磁盘块的数量为[a,b]

对(a,b)树进行分析:

大数据笔记-外存算法

(a,b)树中的操作

  插入:

  大数据笔记-外存算法

 

  删除:

大数据笔记-外存算法

注:若最后合并影响了根节点,使根节点的儿子小于a,此时根节点是不变的(参考上文对根节点数量的定义)。然而,若根节点只有一个儿子,则把根节点给删了

B树的结论:

大数据笔记-外存算法

大数据笔记-外存算法

大数据笔记-外存算法

5.2KD树

 大数据笔记-外存算法

大数据笔记-外存算法

查询:

大数据笔记-外存算法

kdB-树

大数据笔记-外存算法

kdB-树的构建:

大数据笔记-外存算法

改进:

大数据笔记-外存算法

大数据笔记-外存算法

复杂度:

大数据笔记-外存算法

动态地改进:

大数据笔记-外存算法

  插入

  大数据笔记-外存算法

  删除

  大数据笔记-外存算法

kdB-树总结:

大数据笔记-外存算法

6.1 表排序及其应用

表排序(List Ranking)

表排序的困难之处:

大数据笔记-外存算法

一种高效的表排序算法:

大数据笔记-外存算法

分析:

大数据笔记-外存算法

目标:对给定的树T,以表L表示,进而让对T的每一种计算可用对L的一种rank来完成

 欧拉回路技术:

大数据笔记-外存算法

 

大数据笔记-外存算法

 应用场景:

1.父子关系判定

大数据笔记-外存算法

2.计算前序计数

大数据笔记-外存算法

3.计算子树大小

大数据笔记-外存算法

 

大数据笔记-外存算法

6.2时间前向处理方法

将图问题表示为有向无环图的估值问题

大数据笔记-外存算法

 

大数据笔记-外存算法

 

处理过程:

大数据笔记-外存算法

 

大数据笔记-外存算法

大数据笔记-外存算法

大数据笔记-外存算法

......

大数据笔记-外存算法

测试:

大数据笔记-外存算法

求最大独立集MIS(贪心法,不一定求得最优解):

大数据笔记-外存算法

(1的入度为0,在I中,选取后面的节点时,若其父亲节点在I中,则该节点不能加入I中):

大数据笔记-外存算法

 

大数据笔记-外存算法

6.3缩图法

大数据笔记-外存算法

即把大的图缩到内存中

求连通性->半外存算法:结点在内存中,边在外存中

大数据笔记-外存算法

算法分析:

大数据笔记-外存算法

M(memory)

|V|>M:  

  大数据笔记-外存算法

  大数据笔记-外存算法

 

  大数据笔记-外存算法

  算法复杂度分析:

  大数据笔记-外存算法

应用:最小生成树

大数据笔记-外存算法

大数据笔记-外存算法

时间复杂度分析:

大数据笔记-外存算法

 

 另一种图算法技术:

大数据笔记-外存算法