可持久化應用雜談

contents

  1. 1. 函數式編程
  2. 2. 離線算法
    1. 2.1. 幾何計算
  3. 3. 統計方法
  4. 4. 字串處理
  5. 5. 版本回溯
  6. 6. 其他

可持久化的實際用途到底有哪些?這麼複雜的概念大部分場景都用不上?

函數式編程

其不可變的需求,造就了持久化的使用。如果是可變的特性,函數式展開的一對多操作時,就會造成操作失效,除蟲大概是一輩子的痛。以 Java 的 Stream 為例

1
2
3
4
paths.stream()
.flatMap(path -> {
return Stream.of(path.add(a), path.add(b));
});

這樣的函數還算清晰好懂,一旦包了好幾層函數下去,就不曉得 path 到底是能不能被修改。如果不可被修改,意味著每一次都要回傳一個實例,那麼可想而知效能一定不會太高 (大部分的代碼都是整個數據複製)。別去想什麼黑魔法可以在常數時間解決、相信未來人可以穿越時空幫你完成即時計算。請面對現實,計算機終究還是一行一行去執行的。

在編程概念的分支中,函數式編程本身需要這一種技術,達到其函數定義的規範。這一種寫法的效能不好,能理解的人也不多,其一原因學校沒有強制要求去學,一開始都是從程序式、命令式、物件導向式著手居多,所以到工作階段也不太可能遇到大型程式的需求,不過一旦遇到就無可取代。

離線算法

將離線版本切換成強制在線,不用特別去構造一個全新的資料結構來解決問題,只需要預處理一部份的資料,並犧牲更多的記憶體空間來完成。

幾何計算

在幾何計算中,有很多離線算法很容易被找到,一個掃描線掃過去回答所有問題,在時間複雜度分析上總是相當優異的。那如何強迫在線的情況下,每一次都掃描一次,詢問操作的時間複雜度就從對數時間降成線性。為了解決這一種情況,持久化技術給了另一種思維,我們將掃描線的時間軸作為一個變動依據,持久化相關的結構,只要我們能將詢問在對數時間內穿梭於這個時間軸,必能動態解決先前的問題。

統計方法

在 OI 界的經典問題,區間 K 大、攤平成一維陣列的相關計算,問題本身不帶修改操作,只詢問統計於此的統計操作。通常可以透過持久化結構來完成,區間就相當於時間軸,我們能針對兩個時間戳記之間的差異變化來完成統計。

字串處理

為了達到非常高效率的合併操作,防止大量重複性字串的生成伴隨的效能退化,使得各方面的操作都能遠低於線性操作。如 C++ rope 就是一個持久化的資料結構,

不只是字串操作,若處理類型有大量重複的情況,持久化的概念便能派上用場。

版本回溯

實際上就是對應大部分的應用軟體中的 redo/undo。如果資料庫/操作變動為了高效率操作而會配上複雜的結構 (並不像 hash, set 反轉操作只需要常數或對數時間),那麼為了快速回推變動結果,持久化結構就是要減少 redo/undo 的花費。

根據工作上遇到的經驗,資料庫本身可以常數回推,紀錄變動的部分情況即可。而應用層的計算,大部分實作都是砍掉快取,並且重新計算出一份新的結構,有時候回推的變動大小為 m,為了重新計算結構而消耗了 n+m,如果 n 和 m 的差距非常大,那連續回推的體感就很糟糕。

其他

更強硬一點的叫做 Confluent Persistence,可以讓兩個不同的版本合併一個版本,感覺起來就相當於兩個平行宇宙要合併,實際的應用更少一些,大部分應該是在兩個資料結構的合併,如兩個堆如何合併,兩棵伸展樹的合併 … 等的底層定義所需。