工作應用/可持久化

可持久化堆疊 操作 Persistent Stack Operators

contents

  1. 1. 串接 Append
  2. 2. 提取 Take
  3. 3. 移除 Drop
  4. 4. 反轉 Rev
  5. 5. 參考資料
  6. 6. 來點題目 《記憶中的堆疊》
    1. 6.1. 題目描述
    2. 6.2. 範例輸入
    3. 6.3. 範例輸出

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

串接 Append

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

$$\begin{aligned} \left [ \; \right ]_{\textit{append}} &= \left \langle \left [ \; \right ], \left [ \; \right ] \right \rangle \\ \\ |\left \langle T, \; B \right \rangle | &= |T| + |B| \\ \\ \textit{push} \; (\textit{e}, \left \langle T, \; B \right \rangle) &= \left \langle e : T, \; B \right \rangle \\ \\ \textit{pop} \; (\left \langle T, \; B \right \rangle) &= \left \langle \text{hd} \; T, \left \langle \text{tl} \; T, \; B \right \rangle \right \rangle & \{ |T| > 0 \} \\ &= \left \langle \text{hd} \; B, \text{tl} \; B \right \rangle & \{ |T| = 0 \} \end{aligned}$$

串接兩個堆疊 $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)$

$$\begin{aligned} \left [ \; \right ]_{\textit{take}} &= \left \langle 0, X \right \rangle \\ \\ |\left \langle n, X \right \rangle | &= n \\ \\ \textit{push} \; (\textit{e}, \left \langle n, X \right \rangle) &= \text{Append}(e,\; \left \langle n, X \right \rangle) \\ \\ \textit{pop} \; (\left \langle n, X \right \rangle) &= \left [ \; \right ] & \{ n = 1 \} \\ &= \left \langle \text{hd} \; X, \left \langle n-1, \text{tl} \; X \right \rangle \right \rangle & \{ n > 1 \} \end{aligned}$$

只提取堆頂的前 $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)$

$$\begin{aligned} \text{Drop} \; (n, X) &= X & \{ n = 0 \} \\ &= \text{Drop} \; (n-1, X) & \{ n > 1\} \end{aligned}$$

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

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

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

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

反轉 Rev

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

$$\begin{aligned} \text{Rev} \; (X) &= \text{Rev}'(X, \left [ \; \right ]) & \\ \\ \text{Rev}'(X, A) &= A & \{ |X| = 0\} \\ &= \text{Rev}' \; (\text{tl} \; X, \text{hd} \; X : A) & \{ |X| > 0\} \end{aligned}$$

將整個堆疊 $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 ]