回顧

幾年前，跟 liouzhou101 一起搞了很多記憶中系列題目，有一題與陣列很相似，但操作更複雜一些。陣列的操作只有下列幾種

• get(index): 回傳索引為 index 的元素，其中 $\text{index} \in \left [0, n-1 \right ]$
• set(index, value): 修改 index 上的元素
• pushBack(value): 陣列尾端後接一個新的元素
• popBack(): 移除陣列尾端的最後一個元素

從演算法課程中，我們學到 C++ 中的 std::vector 可以做到均攤 $\mathcal{O}(1)$，其大致的做法為陣列快填滿容量時，倍增其大小後轉移原先的所有元素到新的容器上，均攤計算為每次增加的元素都需要預先支付未來轉移自己、轉移對應的另一個元素、移除自己、移除對應的另一個元素的花費，因此均攤花費為常數。

而這樣子的均攤操作在可持久化卻是不利的，因為單一操作的最慘複雜度為 $\mathcal{O}(n)$，意味著可能在同一個操作上，使用 $m$ 次持久化會造成時間複雜度退化成 $\mathcal{O}(mn)$。因此，我們需要最小化最慘時間複雜度的結構。

當年初學者的我，切入觀點有二元樹 (binary tree)、塊狀表 (unrolled linked list)，前者讓操作必為 $\mathcal{\Theta}(\log n)$、後者為 $\mathcal{\Theta}(\sqrt{n})$，從理論分析上一定優先選擇前者實作，但如果操作有特別的比例問題，如 get(index)、pushBack() … 等，這時候快取能力好的塊狀表反而有優勢，二元樹因指標的使用導致整體的內存使用率不高，透過 2-3 tree 那一種將節點儲存多個元素的設計，就相當於把塊狀表拉成樹狀，其效果也不錯，但在計算上會更需要耗費工夫。

塊狀表 (Unrolled Linked List)

任何操作皆為 $\mathcal{\Theta}(\sqrt{n})$，修改操作皆需要複製整個節點。在可持久化情況時，預先每一個塊的大小較為不可行，故做不到動態調整塊狀大小。

二元樹 (Binary Tree)

利用二元樹建立可持久化的情況有很多種編碼，以及紀錄節點的優化方式，這將會影響到我們的效率。盡可能地不在節點中儲存欄位 size 即可達到索引。若二元樹節點定義為

1
2
3
4
5
6

class Node<T> {
    Node *lson;
    Node *rson;
    int size;
    T value;
}

葉與內部節點皆帶有元素值，那麼在陣列的新增刪除尾端的操作，我們可以透過類似 heap 的方式，將其設計成不用旋轉操作、不用紀錄樹大小的編碼。當節點編碼為 $k$，則兩個子節點 $2k$ 和 $2k+1$，實作時只需要紀錄整體大小，接著在走訪過程中，採用位元運算得到其子樹大小作為操作依據。

1
2
3
4
5
6
7

      1
     / \
    2   3
   / \ / \
  4  5 6 7
 /
8

這樣的編碼問題，對於陣列實作時，發現 push/set(index, value) 時，時間複雜度為 $\mathcal{\Theta}(\log \text{index})$，那動態將 $n$ 個元素推入的時間必為 $\mathcal{\Theta}(n \log n)$，靜態建造則為 $\mathcal{\Theta}(n)$。索引值越大的元素，其操作花費越高。

設計函數庫時，我們通常希望盡可能地讓複雜度對稱，也就是兩端的索引速度不會差太多，即使是亂數也好，因為演算法設計、真實生活中的應用大多都會偏向一方，很可能總是觸發最慘情況。

Braun Tree

另一種編碼設計，對於每一個節點皆滿足右子樹大小最多比左子樹大小多一個，由於每一個節點都滿足，按照插入順序，可以得到下圖

1
2
3
4

          1
     2         3
 4     6    5     7
8 10 12 14 9 11 13 15

明顯地，如同霍夫曼編碼一樣，這一個 1-indexed 的情況，最低位 0 則往左子樹、反之為右子樹。每一個操作皆為對稱的，但複雜度如同一般的二元搜尋樹，作為陣列操作也不滿足期待。

若用於可持久化陣列的基底，代碼量非常少，遞迴定義使得操作簡單，我們甚至可以連整體大小都不用儲存，透過其遞迴定義可在 $\mathcal{O}(\log^2 n)$ 得到，但大部分陣列使用都是會希望 A.size() 是可以在 $\mathcal{O}(1)$ 完成的。這樣的設計在優先隊列 (priority queue) 更友善，因為鮮少需要去拿到 size，只需要回傳這個優先隊列是否為空。

同樣地，這依舊不是實作可持久化陣列的首選。

線段樹 (Segment Tree)

線段樹的設計有一個缺點，大部分的情況總是預先知道大小，然後再代入修改操作。

如果要做到動態的增加大小，則採用 top-down 的展開節點方法。如根節點一開始設計範圍為 $\left [0, 2^{32} \right ]$，當我們 push 一個新的元素至尾端時，相當於開出一個葉節點為 index = size，同理 pop 操作。一開始預設最大上限 $M$，單一操作的時間複雜度必為 $\mathcal{\Theta}(\log M)$。

以上述的狀況，每一次操作複雜度必為 $32$，作為函數庫的設計而言，這樣的寫法沒有彈性，而且要是未來超出指定大小，修改就非常的緩慢，更因為在持久化的環境下，不可能在對數時間內轉移其架構。

Leftist Leaf Tree

其概念類似二項堆積 (binomial heap)，我們將使用 $\log n$ 棵樹表示整個序列。將內容放置於葉節點上，並且每一個樹皆為完美樹，無須額外紀錄子樹大小。

例如：當 n = dec(11) = bin(1011) 時，用三棵大小分別為 8, 2, 1 的樹表示之。當 push 一個新的元素至尾端時，與最右邊的子樹 1 合併成大小為 2 的樹，再與左邊的子樹合併成大小為 4 的子樹，最後成為 n' = dec(12) = bin(1100)，用兩棵子樹表示之。同理 pop 操作，模擬二進制的退位。

每一個操作皆為 $\mathcal{O}(\log n)$，且分布較為一般的二元樹均勻。並解決一開始我們在二元樹上遇到的問題，動態將 $n$ 個元素推入的時間，整體複雜度為 $\mathcal{\Theta}(n)$。因此，這是目前實作可持久化隊列的首選。

其他

函數式理論複雜度最好的結構為 finger tree，實作複雜度相當高，卻具備了合併兩個陣列的特殊操作，這是以上結構皆不具有操作。實際的效能無法預測，通常常數過大而無法使用。有朝一日，我們再來挑戰這偉大的結構吧。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

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

函數式編程

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

1
2
3
4

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

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

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

離線算法

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

幾何計算

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

• 參考資料 MIT 6.854 Advanced Algorithms - Persistent Data Structures Notes

統計方法

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

字串處理

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

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

版本回溯

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

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

其他

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

接續前一篇 《可持久化雙向隊列 Persistent Deque 序》，同樣的概念，Okasaki 用了他那精妙的公式描述了前一篇採用的策略只不過是常數 $c = 3$ 的情況，實際上可以根據需求去改變常數 $c$，先決條件 $c \ge 2$。

預先評估雙向隊列 (Pre-Evaluation)

• SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

同樣地，雙向隊列為兩個堆疊表示，並限制其中一個大小不能大於另一個的 $c$ 倍，如果發生了用另一種方式表示部分翻轉的結果。

Invariants

Functional Definition

放眼望去共計 15 條式子，而一半都是對稱操作。唯獨在式 12 到 式 15 較為特別，相當於前一篇的反轉操作，只是我們透過額外的定義來描述它，實作時相當多一個類別。不管是記憶體分析、還是時間複雜度分析，原則上與前一篇是相同的。

公式裡描述了一堆的 $\hat{L}, \; \hat{R}$，我們卻沒有在任何的條件式中使用，只作為我們去理解操作的含意。因此，實作時只在 $makedq$ 區域變數中作用，並不會成為一個必要紀錄的值。

特別注意到建構子中，令 $R' = \textit{rot1}(n, R, L)$，這個操作可能直接成為 $\textit{rot2}(L, \textit{drop}(n, R), \left [ \; \right ])$，思維必須往前看一步去轉化所有實際的類別，否則很容易在相關操作退化。因為 $L, \; R$ 都是作為 rot1 或者是 rot2 後的產物，盡可能地使之成為最簡單的表達式。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

完成了一般隊列，接下來就是雙向隊列，這個時候操作就沒有強烈的單調方向性質，需要同時維護兩種入隊、出隊的情況。

沿用可持久化隊列的思路。在隊列時，我們評估情況為前後各一半，預估反轉的結果，均攤每一個操作費用，一旦前半部為空，立即使用反轉完的結果。而雙向的情況更為複雜，我們若按照隊列的方式，那麼在 pop-back 的時候，預估的結果反而成為了阻礙，因為要再反轉一次回來。為此調整鬆弛反轉的限制。

即時雙向隊列 (Realtime)

• REAL-TIME DEQUES, MULTIHEAD TURING MACHINES and PURELY FUNCTIONAL PROGRAMMING, Tyng-Runey Chuang and Benjamin Goldberg, 1993

定義

定義雙向隊列為 $Q = \left \langle L, \; R \right \rangle$

在操作過程中，可以鏡像狀態，令較大的那一個為 $B$，較小的為 $S$，意即 $\left \langle B, \; S \right \rangle = \left \langle L, \; R \right \rangle$ 或者 $\left \langle B, \; S \right \rangle = \left \langle R, \; L \right \rangle$。需滿足

若違反上述條件，立即進入 轉移狀態，將三分之一的 $B$ 搬入 $S$，此時兩者具有近似的大小。在轉移中，我們可能在過程中將其中一方增減，完成轉移後必要滿足條件式。

轉移狀態

令起始轉移狀態為 $\left \langle S, \; B \right \rangle$，其中

• $S = (p_1, p_2, \cdots, p_m)^\triangleleft$
• $B = (q_1, q_2, \cdots, q_{3m+k})^\triangleright$
• $k \in \left \{ 1, 2, 3\right \}$

目標狀態 $\left \langle \textit{new}S, \; \textit{new}B \right \rangle$

• $\textit{new}S = (p_1, p_2, \cdots, p_m, q_1, q_2, \cdots, q_{m+1})^\triangleleft$
• $\textit{new}B = (q_{m+2}, q_{m+3}, \cdots, q_{3m+k})^\triangleright$

必須均攤在 $m$ 次操作內完成，而舊有的 $S$ 可能在轉移中被 pop 到空集合，需要標記複製成功的次數，直到 $\textit{new}S$ 已經匹配了前半部的 $S$。

1. $B = (q_1, q_2, \cdots, q_{3m+k})^\triangleright$ 拆分成
   $B = (q_1, q_2, \cdots, q_{m+1})^\triangleright$ 和 $\textit{aux}B = (q_{m+2}, q_{m+2}, \cdots, q_{3m+k})^\triangleleft$
2. $\textit{new}S = (p_1, p_2, \cdots, p_m)^\triangleleft$ 反轉成
   $S = ()^\triangleleft$ 和 $\textit{aux}S = (p_1, p_2, \cdots, p_m)^\triangleright$
3. $\textit{aux}B = (q_{m+2}, q_{m+2}, \cdots, q_{3m+k})^\triangleleft$ 反轉成
   $\textit{aux}B = ()^\triangleleft$ 和 $\textit{new}B = (q_{m+2}, q_{m+2}, \cdots, q_{3m+k})^\triangleright$
4. $B = (q_1, q_2, \cdots, q_{m+1})^\triangleright$ 放入為
   $\textit{new}S = (q_1, q_2, \cdots, q_{m+1})^\triangleleft$ 和 $B = ()^\triangleright$
5. $\textit{aux}S = (p_1, p_2, \cdots, p_m)^\triangleright$ 也放入為
   $\textit{new}S = (p_1, p_2, \cdots, p_m, q_1, q_2, \cdots, q_{m+1})^\triangleleft$ 和 $\textit{aux}S = ()^\triangleright$

步驟 1 和 2 同時操作，總數至多為 $2m+3$。步驟 3 可以和 4 或 5 其中一種同時操作，總數至多為 $2m+3$，因此操作數為 $4m+6$。均攤在 $m$ 次操作內，得到常數因子為 4。

隊列操作說明

即使說明了轉移方程，主要的問題還是卡在做到 push/pop

• pushFront/pushBack 若計算完的雙向隊列大小小於等於 4 時，採用攤平的方式操作，強制不進入上述轉移條件。反之，直接在相應的堆疊上操作。
• popFront/popBack 若計算完的雙向隊列大小小於 4 時，採用攤平的方式操作，強制不進入上述轉移條件。反之，直接在相應的堆疊上操作。

額外維護的指針告訴我們複製的 $S$ 狀態，而 $B$ 也會在過程中被 pop 出去，因此 $\textit{new}B$ 有時會需要代入 $\text{Take}$ 操作。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

接續前一篇 《可持久化隊列 Persistent Queue 序》，開始搬運論文的內容，就當作個翻譯吧

預先評估隊列 (Pre-Evaluation)

• SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

初階定義

定義：隊列 $Q = \left \langle L, \; R \right \rangle$ 且滿足 $|R| \le |L|$

看到這一大串的語法樹，就要開始構思曾經在編譯器學到的 LL Parser，操作完之後仍然是一個隊列，為了找到隊列的頭，我們要去完成 LL(1) 的計算，使用向前探查 (lookahead) 問第一個元素為何。

不幸地，上述語法的 $\textit{remove}$ 為 $\mathcal{O}(\log n)$，其他操作為 $\mathcal{O}(1)$。原因很簡單，當我們不斷地 $\textit{insert}$ 進去時，根據語法樹會不斷地構造長度為 $1,\; 2,\; 4, \cdots, 2^n$ 長度的 $\textit{rot}$ 堆疊，這時候若要看第一個元素為何，運算量就等同於遞迴深度。

縱使我們在每個堆疊建構時，預先計算出 front() 的結果，那麼在 pop() 回傳的時候，仍需要付出代價，而我們更不能在建構子中預先計算出 pop() ，這違反遞迴定義，更會落入退化成線性操作，而不是想要的惰性操作。當瞭解上述的問題後，接下來要想辦法把 $\textit{remove}$ 變成 $\mathcal{O}(1)$ 操作。

進階定義

定義：隊列 $Q = \left \langle L, \; R, \; \hat{L} \right \rangle$ 且滿足 $|R| \le |L| \wedge |\hat{L}| = |L| - |R|$

透過額外的 $\hat{L}$，避開了 LL Parser 和 lookahead 造成的遞迴定義，如此一來每一個操作複雜度皆為 $\mathcal{O}(1)$。其概念也很簡單，為了維持條件 $|R| \le |L|$，我們將 $\hat{L}$ 定義為其差值，為即將地部分 $R$ 反轉到變成 $L$ 計數做準備。

特別注意到，在 $\text{makeq}$ 的時候，同步移除掉了一部分的 $\hat{L}$，而在長度 $|\hat{L}| = 0$ 觸發反轉。實作上，可以當作一個長度數值去看待，而在可持久化概念上，它們實際上共享同一塊內存，所以也就沒有太大的差別。

概念與前一篇的 Realtime Queue 構造方式類同。只不過，我們預先將答案放置於 $\textit{rot}$ 堆疊定義中的 $A$ 中，而重複使用了 $\hat{L}$ 找到完成時刻。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

前言

我們完成了持久化堆疊後，必然要去完成隊列 (Queue)。難度遠比想像中的高，很多人的第一個反應是用兩個指標去完成持久化隊列，分別指向最前和最後的兩個元素。不幸地，直覺無法套用在不同的領域上。

下述為一個例子，假定每一個節點都往後指到下一次會被 pop 的節點，則我們無法同時描述 B 和 C。如果每一個節點都往前指到前一個加入的節點，則無法解決隊列的 pop 操作。上述的兩種設計都無法滿足可持久化的定義，則得到用兩個指標是無法完成可持久化隊列。

1
2
3
4

A = empty().push(1); // [1]
B = A.push(2);       // [1, 2]
C = A.push(3);       // [1, 3]
D = B.pop();         // [2]

攤銷分析的錯誤

定義：可持久化隊列 $Q = \left \langle L, \; R \right \rangle$

在沒有持久化的要求下，我們的確可以用兩個堆疊 $L, \; R$ 去實作隊列 $Q$。當 $|L| = 0$ 時，令 $L' = \text{Rev}(R), \; R' = \left [ \; \right ]$，每一個操作的時間複雜度為 $\text{amortized} \; \mathcal{O}(1)$。

然而，對於可持久化的場合中，這種忽大忽小的成本是不切實際的，因為持久化會複製整體的攤銷成本，而獨立於前一個狀態。達到真正的即時 (realtime)，必須保證每一個操作 $\mathcal{\Theta}(1)$，才能防止攤銷最慘情況不會發生。

即時隊列 (Realtime)

• REAL-TIME QUEUE OPERATIONS IN PURE LISP, Robert HOOD and Robert MEVILL, 1981

這快三十年前的論文，給了我們設計函數式的另一種啟發。不透過函數式語言的語法結構，我們可以很直觀地用傳統算法去模擬可持久化隊列。好比 C++ 中的 vector<T> 或者是 Java 中 的ArrayList<T>，每當快滿的時候，我們變將元素複製到兩倍大的容器裡。那可持久化就好比背景程式一般，在每一次操作的過程中，就開始準備好抽換的兩倍容器，直到真的要替換的時候，就可以常數搬移。

定義：隊列 $Q = \left \langle O^{\triangleleft}, I^{\triangleright} \right \rangle$ 且滿足 $|O^{\triangleleft}| \ge |I^{\triangleright}|$

• $O^{\triangleleft}$ 表示出隊的堆疊
• $I^{\triangleright}$ 表示入隊的堆疊

當發生 $|O^{\triangleleft}| = n, \; |I^{\triangleright}| = n+1$ 時，我們標記這個隊列為 轉移中 (transferring)，此時開始可不滿足上述 $|O^{\triangleleft}| \ge |I^{\triangleright}|$ 的規定。接著，我們將預期在下一次 $|O^{\triangleleft}| = 0$ 的 pop 操作前，變換成 $Q = \left \langle (OI)^{\triangleleft}, \left [ \; \right ] \right \rangle$。因此這中間至少有 $n$ 次的 push/pop 操作，讓我們將轉移中隊列變成正規隊列。

需要以下操作：

1. 將 $I^{\triangleright}$ 的所有元素 pop 至 $I_\text{aux} = I^{\triangleleft}$，需 $n+2$ 步。
2. 將 $O^{\triangleleft}$ 的所有元素 pop 至 $O_\text{aux} = O^{\triangleright}$，需 $n+1$ 步。
3. 將 $O_\text{aux}$ 的所有元素 pop 至 $I_\text{aux}$，$O_\text{new}= (OI)^{\triangleleft}$，需 $n+1$ 步。

共計 $3n+4$ 步。平均在 $n$ 次操作內完成。變成 轉移中 狀態的那一瞬間，操作 $7$ 次，隨後的每一個 push/pop 完成 $3$ 次操作。 確保了每一步在常數時間內完成。

在轉移過程中，若進行 push 操作，直接在清空完後的 $I^{\triangleright}$ 上操作、或者 $I_\text{extra}^{\triangleright}$ 。若進行 pop 操作時，步驟 3 的最後幾個會成為多餘操作，故需要額外的計數器統計總共完成了幾個 $O_\text{aux}$ 複製，當完成數量等於當前數量 $|O|$ 便停止轉移，並標記為正規隊列 $Q = \left \langle O_\text{new}^{\triangleleft}, I^{\triangleright} \right \rangle$、或者 $Q = \left \langle O_\text{new}^{\triangleleft}, I_\text{extra}^{\triangleright} \right \rangle$

宣告不可變物件的類別時，以 Java 為例相當棘手，展開代碼會造成進入 HotSpot 的機會變低，傳遞這個多的參數進行轉移卻要用在回傳值上額外宣告變數來接取。因此，透過平均 $3$ 次，可能會需要額外宣告 3 次變數，這對 GC 的壓力非同小可。貪心一點，用常數 4 取代，這麼一來可讀性不會下降太多，代碼也能更明確一點，呼叫 2 次的 2 個操作。

實作時，一個可持久化隊列除了一開始的 2 個堆疊，還要維護轉移狀態 5~6 的狀態空間，因此一個隊列需要 7~8 個欄位。

預先評估隊列 (Pre-Evaluation)

• SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

這是另一種設計方法，上述方法用了 7~8 欄位來表示一個隊列，作為一個函數式定義太複雜了，這一概念將只使用 3 個，其他的塞在別的定義中，讓其他函數式定義也能夠共享，下一篇文章再來細說。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

效能評比

以 Java 實作，Realtime 與 Pre-Evaluation 效能差不多，但以 OOP 的角度看來 Realtime 很像當初打比賽的精明能幹，Pre-Evaluation 則是代碼量巨大，擴充概念性高。

接續前一篇 《可持久化堆疊 Persistent Stack》，接下來要探討可持久化堆疊相互操作，如何照常在常數複雜度內完成。這一連貫的定義，將在後續的隊列、雙向隊列中使用。

串接 Append

定義：串接堆疊 $A = \text{Append} \; (T, B)$

串接兩個堆疊 $T, \; B$，並且 $T$ 放置於頂首、$B$ 放置於末端，這時候串接也可以被視為一個堆疊結構。由於我們只在意堆疊的接口，完成這三項基礎操作並不是難事。皆可以在 $\mathcal{O}(1)$ 內完成。

對於大小這一個計算，要特別小心一個錯誤，如果直接以回傳值 $|T| + |B|$ 撰寫，將在遞迴使用時，其一方也為串接定義出的堆疊而退化成 $\mathcal{O}(n)$ 的計算。因此在宣告時，紀錄大小是很重要的。

此外，我們也很容易遞迴定義出 Append，如果 $T$ 本身也是 Append 出來的結果，那麼 pop 時會付出遞迴深度的代價，按照使用的演算法，這種情況會使得時間複雜度為 $\mathcal{O}(\log n)$。構造時，如果 $T \in \text{Append}$，拆解成 $\text{Append}(T.l, \; \text{Append}(T.r, \; B))$ 可以避免。

我們透過簡單的工廠模式 (Factory Design Pattern)，防止額外的空間宣告，當 $T$ 或者 $B$ 其一為空時，直接回傳其中一方。接著就能保證 $|T| > 0, \; |B| > 0$，操作就能簡化許多。

提取 Take

定義：提取堆疊 $A = \text{Take} \; (n, X)$

只提取堆頂的前 $n$ 個元素，剩餘的都不需要。無疑地，提取堆疊也是可持久化的，並且在 $\mathcal{O}(1)$ 時間內完成所有堆疊操作。但是在 push 操作時，將使用串接操作。

發生遞迴定義時，意即 $X \in \text{Take}$，則必須提取成 $A = \text{Take}(n, \; X.x)$ 防止退化成 $\mathcal{O}(\log n)$

移除 Drop

定義：移除堆疊 $A = \text{Drop} \; (n, X)$

相反於提取，忽略堆頂的前 $n$ 個元素，從 $n+1$ 個開始算。

這裡僅提供遞迴定義，由於移除操作並非完全的常數操作，一旦需要拿到堆頂的第一個元素時，勢必要運行 $n$ 次。唯有在運行操作中，若 $n \le c$ 小於某個常數定值時，這時候才能把移除操作視為常數且可持久化的堆疊，否則將視為一般的攤平操作。

爾後，我們將提及一些算法的定義 $c = 3$，使用這一個 Drop 操作。實作時要特別小心，同時 X 也是一個移除堆疊，那麼在建構前，必然要將 X 攤平，意即把 n 弄成 0 的表示法。防止 pop 操作時，意外地發生 stack overflow 的慘劇。

或許有人會問為什麼不一開始就攤平，早就是常數操作？其實，這就要看理論目標的最壞情況最小化，常數要怎麼分配到不同操作中。在可持久化的領域中，每一個常數操作的大小是每個操作的最大值，而非加總起來，完全不同於一般算法設計攤銷分析，因此優化的思維要有所轉變。

反轉 Rev

定義：反轉堆疊 $A = \text{Rev} \; (X)$

將整個堆疊 $X$ 反轉後置放成一個堆疊 $A$。

同樣地，若沒有定義 $|X| \le c$，反轉操作也無法在常數時間內完成。網路上許多實作號稱常數、攤銷持久化，實際上若牽涉到回傳反轉的過程，即使做了快取答案，也可以輕易地將它效能擊破。只需要不斷地呼叫反轉那一瞬間的的操作，或者倒退版本再推進一個版本去觸發攤銷的反轉操作，複雜度就會落入 $\mathcal{O}(n)$。

參考資料

• SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

來點題目 《記憶中的堆疊》

題目描述

不斷地進行「思想實驗」的妮可，終於讓大腦演進到平行思考。假想在腦海裡，我們把狀態以堆疊 (Stack) 的方式儲存，當走投無路的時候，就會退回到上一個狀態，再把新的分支因素堆疊上去。正在全力計算的妮可無法細說每一個思維狀態，而我們可以操作戳記，反推出當前狀態。

操作有以下三種：

• 0 v: 退回版本 v
• 1 x: 在當前堆疊，push x 到堆頂
• 2: 印出當前堆疊狀態

起始版本編號為 0，第 $i$ 次操作版本編號為 $i$。

範例輸入

1
2
3
4
5
6
7
8
9

1 1
1 2
2
0 1
2
1 3
2
0 3
2

範例輸出

1
2
3
4

2 1 ]
1 ]
3 1 ]
2 1 ]

起因

在某些情況下，我們想要每次操作都能對應一個新的物件，即使變動當前的數據結構，也不影響前一次的數據結構。「可持久化 Persistent」一詞用來描述在這一段時間內，保存所有操作狀態的方法。若用在資料庫儲存概念中，「持久化 Persistence」則是用來描述將內存數據對照寫入檔案的可行性，兩者的意思不盡相同。

在工作發現許多語言開始支援函數式設計，也就是 $\lambda$ 計算 (lambda function)，以現在手上的 Java 開發，主要發生幾個常見的效能問題：

• 惰性求值 (Lazy Evaluation)：
  每一個惰性求值是需要的時候再計算，然而有些歷史代碼並不是這麼回事，導致一部分函數回傳整個串列，因此消耗了至少為 $\mathcal{O}(n)$ 的時間，而非函數式所需要的 $\mathcal{O}(1)$。如果一個函數只針對前 10 個數值感興趣，大部分的資料都會被捨棄掉，在未來使用這些函數接口時，都還要去檢查每一個相關實作是否為真惰性，而非假性惰性。請參閱 Java Stream 串流實作細節。

• 不可變物件 (Immutable Object)：
  對於某些中間表達式，如檔案系統路徑。若要列出一個資料夾下的所有檔案路徑，在上述的惰性求值中，樸素的實作將會把路徑之間的重複不斷複製。正如同經典的字串問題，每串接一個字串，必然會複製一份，倘若複製的順序相反，時間複雜度將從 $\mathcal{O}(n)$ 變成 $\mathcal{O}(n^2)$。

串流操作 Stream 以 functional-style operation 為主，又細分成好幾種操作。即使運行結果相同，造就的效能與可拓展性也不同，如 reduce 和 collect 的差別，都能將一系列的元素縮合成一個，但是 reduce 採用二合一，容易在合成操作上退化成 $\mathcal{O}(n^2)$，對不可變物件操作，其空間消耗量大，唯一個優勢是平行加速的擴充性。相反地，collect 則是逐一將元素納入一個集合，這樣一個簡單的合併操作，是沒辦法并行處理的，好處則是不會產生太多額外使用空間。

為了達到具拓展性且不失效能的設計，函數式編程那些獨特的數據結構和算法，或許能解決我們的問題。

堆疊定義

堆疊 Stack，主要有兩個操作：

• $\textit{push} \; (\textit{value})$：將一個元素 $\textit{value}$ 放置到堆頂
• $\textit{pop} \; ()$：將堆頂元素移除

課堂上總是會教資料結構，使用鏈結串列 (Linked List) 或者是陣列 (Array) 來實作，每一個操作皆為 $\mathcal{O}(1)$ 常數。而持久化一個堆疊，我們將要針對改變結構內容的操作進行複製。

可持久化堆疊定義

可持久化堆疊 Stack 定義：

• $[\;]_{\textit{stack}} = \left \langle [\;] \right \rangle$
• $|\left \langle A \right \rangle| = |\left \langle \text{hd} \; A \right \rangle| + |\left \langle \text{tl} \; A \right \rangle|$
• $\textit{push} \; (\textit{e}, A) = \left \langle e : A \right \rangle$
• $\textit{pop} \; (A) = \left \langle \text{hd} \; A, \left \langle \text{tl} \; A \right \rangle \right \rangle$

上述的數學式

• $\text{hd}$ 為堆疊的首元素。另一個使用術語為 $\textit{car}$。
• $\text{tl}$ 為剔除首元素之後的結果。另一個使用術語為 $\textit{cdr}$。從堆疊來看，即為回傳指向前一個節點的位置。
• $:$ 為串接操作。

這一簡單結構，又被稱作為 list。只允許對堆頂操作的串列，這麼說很混淆，但在函數式設計中，他們通用的 list 就是這麼構造的，在後續的算法中，我們都用可持久化堆疊來表示 list。

以下述的例子，我們構造 4 個堆疊，每一個堆疊指向堆頂元素。對於加入一個元素到堆疊，我們就額外多一個節點指向先前的堆疊；相同地，移除堆頂元素時，回傳前一個堆疊結果。

1
2
3
4

A = empty.push(X)    // [X]
B = A.push(Y)        // [X, Y]
C = B.push(Z)        // [X, Y, Z]
D = B.push(W)        // [X, Y, W]

相應的儲存圖

1
2
3
4
5
6
7
8
9

   A         B         C
+--+-+    +--+-+    +--+-+
|  |X<----+  |Y<----+  |Z|
+--+-+    +--+^+    +--+-+
              |
              |        D
              |     +--+-+
              +-----+  |W|
                    +--+-+

此時，$D$ 進行 $\textit{pop}$ 操作，回傳值為 $\left \langle W, B \right \rangle$。

最後，對於每一個操作在 $\mathcal{O}(1)$ 時間內完成，需要額外的 $\mathcal{O}(1)$ 空間。對於沒有垃圾回收 (Garbage Collection) 的語言實作上，需要維護參照數量 reference counter 來回收沒有用到的堆疊節點。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

package persistent.stack;
import persistent.PStack;
/**
 * @author morrisy
 *
 * @param <T> The type of element
 */
public class PersistStack<T> extends PStack<T> {
    @SuppressWarnings("rawtypes")
    private static final PersistStack<?> EMPTY = new PersistStack();
    @SuppressWarnings("unchecked")
    public static <T> PersistStack<T> create() {
        return (PersistStack<T>) EMPTY;
    }
    private final T value;
    private final PersistStack<T> next;
    private final int size;
    private PersistStack() {
        this(null, null, 0);
    }
    private PersistStack(T value, PersistStack<T> next, int size) {
        this.value = value;
        this.next = next;
        this.size = size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public int size() {
        return size;
    }
    public PersistStack<T> clear() {
        return create();
    }
    public T top() {
        if (isEmpty())
            return null;
        return value;
    }
    public PersistStack<T> push(T value) {
        return new PersistStack<>(value, this, size + 1);
    }
    public PersistStack<T> pop() {
        return next != null ? next : create();
    }
}