可持久化雙向隊列 Persistent Deque 序

contents

  1. 1. 即時雙向隊列 (Realtime)
    1. 1.1. 定義
    2. 1.2. 轉移狀態
    3. 1.3. 隊列操作說明
  2. 2. Java 實作代碼

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

沿用可持久化隊列的思路。在隊列時,我們評估情況為前後各一半,預估反轉的結果,均攤每一個操作費用,一旦前半部為空,立即使用反轉完的結果。而雙向的情況更為複雜,我們若按照隊列的方式,那麼在 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$。需滿足

$$\begin{aligned} |B| \ge |S| \ge 1, \; \text{and} \; 3|S| \ge |B| \end{aligned}$$

若違反上述條件,立即進入 轉移狀態,將三分之一的 $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