可持久化堆疊 Persistent Stack

contents

  1. 1. 起因
  2. 2. 堆疊定義
  3. 3. 可持久化堆疊定義
  4. 4. Java 實作代碼

起因

在某些情況下,我們想要每次操作都能對應一個新的物件,即使變動當前的數據結構,也不影響前一次的數據結構。「可持久化 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 為主,又細分成好幾種操作。即使運行結果相同,造就的效能與可拓展性也不同,如 reducecollect 的差別,都能將一系列的元素縮合成一個,但是 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();
}
}