转载

可持久化堆疊 Persistent Stack

在某些情況下，我們想要每次操作都能對應一個新的物件，即使變動當前的數據結構，也不影響前一次的數據結構。「可持久化 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 為主，又細分成好幾種操作。即使運行結果相同，造就的效能與可拓展性也不同，如 reduce 和 collect 的差別，都能將一系列的元素縮合成一個，但是 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 個堆疊，每一個堆疊指向堆頂元素。對於加入一個元素到堆疊，我們就額外多一個節點指向先前的堆疊；相同地，移除堆頂元素時，回傳前一個堆疊結果。

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]

相應的儲存圖

   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/PersistentDataStructure

package persistent.stack;

import persistent.PStack;

/**
*@authormorrisy
*
*@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();
    }
}

原文 http://morris821028.github.io/2019/12/22/mproblem-persistent-stack/

正文到此结束