可持久化隊列 Persistent Queue 續

contents

  1. 1. 預先評估隊列 (Pre-Evaluation)
    1. 1.1. 初階定義
  2. 2. 進階定義
  3. 3. Java 實作代碼

接續前一篇 《可持久化隊列 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|$

$$\begin{aligned} \left [ \; \right ]_{q} &= \left \langle \left [ \; \right ], \left [ \; \right ] \right \rangle \\ \\ |\left \langle L, \; R \right \rangle | &= |L| + |R| \\ \\ \textit{insert} \; (e, \left \langle L, \; R \right \rangle) &= \textit{makeq} \; (L, \; e : R) \\ \\ \textit{remove} \left \langle L, \; R \right \rangle &= \left \langle \text{hd} \; L, \textit{makeq} \; (\text{tl} \; L, \; R) \right \rangle \\ \\ \textit{makeq} \left \langle L, \; R \right \rangle &= \left \langle L, \; R \right \rangle &\{ |R| \le |L|\} \\ &= \left \langle \textit{rot}(L, R, \left [ \; \right ]), \left [ \; \right ] \right \rangle &\{ |R| = |L| + 1\}\\ \\ \textit{rot}(L, R, A) &= \text{hd} \; R : A & \{ |L| = 0 \} \\ &= \text{hd} \; L : \textit{rot}(\text{tl} \; L, \text{tl} \; R, \text{hd} \; R : A) & \{ |L| > 0 \} \end{aligned}$$

看到這一大串的語法樹,就要開始構思曾經在編譯器學到的 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|$

$$\begin{aligned} \left [ \; \right ]_{q} &= \left \langle \left [ \; \right ], \left [ \; \right ], \left [ \; \right ] \right \rangle \\ \\ |\left \langle L, \; R, \; \hat{L} \right \rangle | &= |L| + |R| \\ \\ \textit{insert} \; (e, \left \langle L, \; R, \; \hat{L} \right \rangle) &= \textit{makeq} \; (L, \; e : R, \hat{L}) \\ \\ \textit{remove} \left \langle L, \; R, \; \hat{L} \right \rangle &= \left \langle \text{hd} \; L, \textit{makeq} \; (\text{tl} \; L, \; R, \hat{L}) \right \rangle \\ \\ \textit{makeq} \left \langle L, \; R, \; \hat{L} \right \rangle &= \left \langle L, \; R, \; \text{tl} \; \hat{L} \right \rangle &\{ |\hat{L}| > 0\} \\ &= \left \langle L', \left [ \; \right ], L' \right \rangle, \; \text{let} \; L' = \textit{rot}(L, R, \left [ \; \right]) &\{ |\hat{L}| = 0\}\\ \\ \textit{rot}(L, R, A) &= \text{hd} \; R : A & \{ |L| = 0 \} \\ &= \text{hd} \; L : \textit{rot}(\text{tl} \; L, \text{tl} \; R, \text{hd} \; R : A) & \{ |L| > 0 \} \end{aligned}$$

透過額外的 $\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