可持久化數據結構簡介

簡介

可持久化數據結構 (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 類，支援寫出函數式的語法設計，可提供惰性求值、無限值域等的特殊功能。

參考

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：morris821028
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用