工作應用/可持久化

可持久化應用雜談

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，可以讓兩個不同的版本合併一個版本，感覺起來就相當於兩個平行宇宙要合併，實際的應用更少一些，大部分應該是在兩個資料結構的合併，如兩個堆如何合併，兩棵伸展樹的合併 … 等的底層定義所需。