2019-12-24

可持久化隊列 Persistent Queue 序

1. 前言
1. 1.1. 攤銷分析的錯誤
2. 即時隊列 (Realtime)
3. 預先評估隊列 (Pre-Evaluation)
4. Java 實作代碼
5. 效能評比

前言

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

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

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 操作，讓我們將轉移中隊列變成正規隊列。

需要以下操作：

將 $I^{\triangleright}$ 的所有元素 pop 至 $I_\text{aux} = I^{\triangleleft}$，需 $n+2$ 步。
將 $O^{\triangleleft}$ 的所有元素 pop 至 $O_\text{aux} = O^{\triangleright}$，需 $n+1$ 步。
將 $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 則是代碼量巨大，擴充概念性高。

Morris' Blog