一、可持久化数据结构简介
可持久化数据结构(Persistent data structure)总是可以保留每一个历史版本,并且支持操作的不可改变性(immutable)。
二、可持久化分类
1.部分可持久化 (Partially Persistent)
所有的版本均可访问,但是只有最新版本可以修改
2.完全可持久化 (Fully Persistent)
所有版本均可即访问又修改。
若支持将两个历史版本合并,则又称为汇合可持久化 (Confluently Persistent)。
三、实际应用
1.几何计算
在几何计算中有许多离线算法,例如悬线扫描法,其基本策略是一次扫描后给出所有询问的回答,在时间复杂度分析相当优秀。但在强迫在线的情况下,每次都要进行一次悬线扫描,询问操作的时间复杂度就从对数时间降为线性。
为了解决时间复杂度上的问题,在这里可以引入可持久化的思维。我们将扫描线的时间轴作为一个变动依据,持久化相关的结构,只要我们能将询问在对数时间内穿梭于这个时间轴,必能动态解决先前的问题。
2.字串处理
为了达到非常高效率的合并操作,防止大量重复性字串的生成伴随的效能退化,使得各方面的操作都能远低于线性操作。如C++中的rope就是一个可持久化的数据结构。不只是字串操作。若处理类型有大量重复操作,均可以考虑将数据结构进行可持久化处理,以达到压缩时间开支的效果。
3.版本回溯
实际上就是对应大部分的应用软体中的redo/undo。如果资料库/操作变动为了高效率操作而会配上复杂的结构(并不像 hash, set 反转操作只需要常数或对数时间),那么为了快速回推变动结果,持久化结构就是要减少 redo/undo 的花费。
资料库本身可以常数回推,纪录变动的部分情况即可。而应用层的计算,大部分实作都是砍掉快取,并且重新计算出一份新的结构,有时候回推的变动大小为 m,为了重新计算结构而消耗了 ,如果 和