

Introduction

简介¶

可持久化数据结构 (Persistent data structure) 总是可以保留每一个历史版本，并且支持操作的不可变特性 (immutable)。

可持久化分类¶

部分可持久化 (Partially Persistent)¶

所有版本都可以访问，但是只有最新版本可以修改。

完全可持久化 (Fully Persistent)¶

所有版本都既可以访问又可以修改。

若支持将两个历史版本合并，则又称为 Confluently Persistent

实际应用¶

几何计算¶

在几何计算中有许多离线算法，如扫描线算法一次扫过去回答所有询问，在时间复杂度分析上相当优异。但强迫在线的情况下，每一次都扫描一次，询问操作的时间复杂度就从对数时间降成线性。为了解决这一种情况，持久化技术给了另一种思维，我们将扫描线的时间轴作为一个变动依据，持久化相关的结构，只要我们能将询问在对数时间内穿梭于这个时间轴，必能动态解决先前的问题。

字串处理¶

为了达到非常高效率的合并操作，防止大量重复性字串的生成伴随的效能退化，使得各方面的操作都能远低于线性操作。如 C++ rope 就是一个持久化的数据结构。不只是字串操作，若处理类型有大量重复的情况，持久化的概念便能派上用场。

版本回溯¶

实际上就是对应大部分的应用软体中的 redo/undo。如果资料库/操作变动为了高效率操作而会配上复杂的结构（并不像 hash, set 反转操作只需要常数或对数时间），那么为了快速回推变动结果，持久化结构就是要减少 redo/undo 的花费。

资料库本身可以常数回推，纪录变动的部分情况即可。而应用层的计算，大部分实作都是砍掉快取，并且重新计算出一份新的结构，有时候回推的变动大小为 m，为了重新计算结构而消耗了 n+m，如果 n 和 m 的差距非常大，那连续回推的体感就很糟糕。

函数式编程¶

函数式编程需要特别的数据结构以符合语言特性，其中不可变的性质更为重要，以利于并行环境与除错。如面向对象编程的 Java 8 后引入 stream 类，支援写出函数式的语法设计，可提供惰性求值、无限值域等的特殊功能。

参考¶

Last update and/or translate time of this article，Check the history
Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
Contributor of this article morris821028
Translator of this article Visit the original article!
The article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.