6.851:Persistent data structure 持久化数据结构(编写与修改中)

——From MIT 6.851 advanced data structure lesson; 《Making Data Structure Persistent》 –James R. Driscall;《Advanced Data Structure》Peter Press; Wikipedia;

要实现 git 的感觉。。。就是。。。要飞起来一样

fortunes-algorithm “Persistent data structure can be useful as a tool for geometric algorithms that perform a sweep”

 

Persistent data structure就像git和log一样,会持续的记录所有信息(在需要范围内),如果能够持续的保存所有信息,那么就可以回到任何时候任何情景下的状态(version)(就像Mac下的Time machine,也就是课程里的time travel)。所以实际上一旦信息被写入其中,理论上就永远不可能被删除掉(immutable),因为每一个操作都不会对原有结构进行更改,而只是添加新的内容(update)。要达到这个目标想一想就得有不少冗余,而Persistent data structure就是要尽可能高效的实现。

先引入一个小结构叫Pointer machine,简单讲就是节点,什么各种线性表也好,各种树也好,各种图也好,其实都是主要由一个个节点组成,每个节点主要有指针部分和数据部分,指针部分用来确定位置与关系,数据部分用来记录。这里定义了几个基本操作:

  1.  x = new Node()
  2.  x = y.field
  3. x.field = y
  4. x = y + z, etc (i.e. data operations)
  5. destroy(x) (if no other pointers to x)

整个大的结构就建立在这些基本的pointer machine上。

在这里介绍了Persistence的四种方式:

  1. Partial Persistence:可以在任何版本上进行query(查询),只能在最近更新过的版本上进行update(更新或者说更改),也就是版本之间的关系是直线型的
  2. Full Persistence:可以在任何版本上进行query和update,也就是一个发散的树形结构
  3. Confluent Persistence:除了基本的query与update操作之外还可以将多个版本结合(是combination不知道为什么不用merge。。。)成新的版本,所以是一个有向无环图(Direct acyclic graph,DAG)结构
  4. Functional Persistence:这种方式取名与一种对象无法更改的函数式编程。每次update都会产生新的节点,只能增加节点而不可以更改节点的内容

这四种方式每种都蕴含(imply)了前一种,也就是说每种都比前一种限制更强

 

  1. Partial Persistence:假设每个节点拥有p<=O(1)(常数个)指向其他节点的pointers,那么我们每次update有O(1)的摊还时间和空间。
    • 每个被指向的节点记录下指向原节点(前缀/父节点……)的pointer。
    • 每个节点允许存储<=2p个mods(version,fields,value)(即更改,modifications)
    • 读取每个节点中node.filed(Vn)(节点中filed成员在Vn版本的值)所需要的时间为O(1),也就是说找到在所有节点中寻找某一版本的时间<=O(V)(也就是板书中的<=V)
    • read(var, v)的过程:在节点中找到满足<=v的“最大”版本w,根据mods中的信息和存储的指针指向的旧版本中的信息确定var在(b)中,找到v1版本下的子节点的值需要根据mods中的update记录;在(c)中,找到v1版本下子节点的值就需要根据指针回溯了(对图中关于mods的存放顺序仍有疑问)
    • write(var, val)的过程:当节点的mods部分不满时直接添加即可,而mods部分被填满时就需要新建一个节点了,并且
      1. 复制最新的状态(已经根据mods更改后)的field以及forward pointer(指向其他节点的指针)至新节点的静态field成员区域
      2. 复制back pointers至新节点(的对应区域)
      3. 对于每个原(old)节点指向的节点,更新这些节点back pointers由指向原节点改为指向新节点(设最多d项)
      4. 对于每个指向原节点的节点,递归调用write(x.p , n’)即更新该节点指针为n’(最多p次调用)
    • Analysis:
      • space:d+p+2p ~ O(1)
      • time:read 需要 O(1);write在最坏情况下需要很长时间,但平摊之后利用势能法(potential function)计算摊还代价 amortized_cost(n) <= c + c – 2cp + p * amortized_cost(x) ,x为指向n的节点,利用递推式的性质可以得到 amortized_cost(n) = 2c (将右侧展开)。故平摊时间也只有O(1)
  2. Full Persistence:Full Persistence是在Partial Persistence的基础上扩展而来,通过将树以线性表表示出来
    • 通过“order maintenance”的数据结构可以实现
      • 将一个item插入到特定元素的前/后面
      • 检查一个item是否在另一个item的“前面”
      • 检查两个item是否有共同祖先
    • 对于每个节点同样存储d项data entries/outer-pointers和p项back pointers,但是允许最多2(d+p+1)项mods
    • read(n.field, version):通过order maintenance结构来找到在mod log中的version与entry的最近祖先
    • write(n.field, value, version):同样,如果在节点中还有空间则直接加入,否则:

 

 

 

 

 

 

 

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注