Company Ghost Story 公司鬼故事 2

C/C++

Overprotection

1
2
3
4
5
bool find_intersect(list<shape> a, tree b, shape c) {
if (b == null)
b = new tree(a);
return b.find_intersect(c);
}

過度保護,造成最後沒人知道 a 和 b 的關係。結果有時候 b 不是由 a 建立的,整串都不知道在做什麼。

Evil Comma

1
2
if (str[0] == '-');
str = str.substr(1);

排版已經告訴你可能發生了問題,但看起來還是救不了下面那一行。似乎沒有發生意外,但是非常恐怖。

Export

1
2
3
4
string x = "";
for (int i = 0; i < n; i++)
x = x + pts[i].str();
// x += pts[i].str();

組成不是大問題,串起來就崩潰 $O(n^2)$。請善用 in-place 的串接。

Test Script

1
2
3
4
// testXXX.cpp
int main() {
... // 100,000+ lines
}
1
g++ testXXX.cpp -O3

浪費生命從編譯時間著手,拜託開 -O0 就好,這樣就近乎線性時間的編譯速度。開到 -O3 會有平方層級的編譯時間,$(10^5)^2$ 雖然也不是很多,但突然從幾秒變成幾個小時是有可能的。

Algorithm

List vs Hash

List 比 Hash 快,不用計算雜湊值,直接比對更快。

數量一大是不是要平行去找了啊,小伙子。

Math

Degree vs Radian

1
2
3
double rotate90(double deg) {
return Math.toRadian(deg + 90) % 90;
}

不會弧度記算沒關係,晚點我們再檢查一下還有哪一段混著算吧。希望都沒事。

Git

linter

不要 format code,因為 git blame 不好看。

1
2
3
4
5
6
7
8
9
for (int i = 0; i < n; i++) {
try
{
Data rowData = data.getRow(i);
}
catch (Exception e)
{
}
}

心靜自然涼,再多的 try-catch 我也可以接受。沒事,我不會受到傷害。

Windows

Set Env Variable

1
2
1. 我的電腦 > 內容 > 進階內容設定 > 環境變數
2. 重新開機 // ?????

在大部分情況是不用重新開機,重新開啟 shell 即可。

Jenkins

Build Artifacts

每一次建置結果都保存下來,用定時刪除。

大部分的建置結果只需要保留進 25 次就差不多,如果每一次建置就要耗掉 1 GB 的硬碟空間,那在一天內上傳了好幾次,就會看到 1 TB 硬碟直接死去。

請不要說買硬碟解決問題,這並沒有解決根本問題。

Build Pipeline

充分運用硬體資源,全部平行。

有些工作是需要整台伺服器的計算資源,如果安排兩個以上的工作時,會造成另一個工作結果不穩定。而有些工作會需要大量的硬碟 IO,兩個以上甚至會造成卡死的狀態。

請不要說買更多的機器或 CPU 解決問題,這只要開一個有平行工作,另一個工作沒設計好就會自動失敗。

Read More +

Company Ghost Story 公司鬼故事 1

以下出現的問題,都是在公司遇到的事件,以類比的方式來描述遇到的狀況。

Java

Unique

1
2
3
4
5
6
class DbObj {
@Override
public boolean equals(Object obj) {
return this.compareTo((DbObj) obj) == 0;
}
}

對於唯一存在的物件,別用 compareTo() 來實作 equals(),它們可以直接用 == 判定。而且大部分的 compareTo 是比較慢的線性實作。如下述的物件

1
2
3
4
class MyString {
@Override
public boolean equals(Object obj) {...}; // possible O(n)
}

結果就是變得超慢。

toString in Comparison

1
2
3
4
5
6
class CompositeClass implements Comparable<CompositeClass> {
@Override
public int compareTo(CompositeClass other) {
return toString().compareTo(other.toString()); // ???????
}
}

千萬別這麼幹,當我們對類別增加成員時,同時修改 toString() 後,運行結果也不同。這也會帶來嚴重的效能問題,試想著排序的時候,產生一大堆的字串用於比較,那麼垃圾回收就會佔有大部分的時間。

toString() in Key

當需要對 enum 或者其他相關物件進行反序列時,避開 toString(),因為這個函數很容易被其他人覆寫。

1
2
3
4
5
6
7
8
enum SomeType {
@Override
public String toString() {
return super.toString() + "...";
}
}
SomeType.valueOf(type.toString()); // ?????

有人會說這個函數不該被覆寫,但能操作就可能出事。

It is not in C++

1
2
3
boolean sameLocation(Point a, Point b) {
return a == b; // ?????, Objects.equals(a, b)
}

抱歉,您使用的是 Java,並沒有 operator== 的語法,所有的 == 都是比較相同物件,並不會實作對應的 equals()

Numeric Comparison

1
2
static final Comparator<Point> compareX =
(a, b) -> a.getX() - b.getX(); // X, Long.compare(a.getX(), b.getX());

這種容易發生 overflow/underflow 的寫法,並不建議模仿 C/C++ 的習慣,請多用內建的函數比較。

this in Constructor

1
2
3
4
5
6
7
8
9
10
public Point {
Point(long x, long y) {
mX = x;
mY = y;
}
Point() {
mX = 0; // X, this(0, 0);
mY = 0;
}
}

請盡量使用建構子,各自獨立容易漏掉一些共同的檢查。

Initialization

1
2
3
4
5
6
Point copy() {
Point pt = new Point();
pt.setX(getX());
pt.setY(getY());
return pt; // new Point(getX(), getY());
}

能使用建構子完成的事情就盡量使用,分次使用可能會造成過多額外的檢查或調整,效能就會往下掉。

Find the Minimum/Maximum Element

1
2
3
4
5
6
7
8
Point getMax(List<Point> testList) {
Collections.sort(testList);
return testList.get(testList.size() - 1); // Collections.max(testList);
}
Point getMin(List<Point> testList) {
return testList.stream().sorted().getFirst().orElse(null);
// testList.stream().min().orElse(null);
}

排序很簡單,但也不能亂寫。

排序複雜度大部分為 $O(n \log n)$,事實上找最小值只需要 $O(n)$。當 $n = 10^6$ 時,效率就可能差到 20 倍。

Computed Getter

1
2
3
4
5
6
7
8
static final Comparator<CPoint> compateLocation =
(CPoint ca, CPoint cb) -> {
long p0x = ca.getCPt().getX();
long p1x = cb.getCPt().getX();
long p0y = ca.getCPt().getY();
long p1y = cb.getCPt().getY();
... // X, return ca.getCPt().compareTo(cb.getCPt());
}

請不要這麼寫,排版好看行數很多並不是好藉口,這呼叫了好幾次 getCPt(),如果牽涉到好幾步複雜運算,整個效率就慢上了好幾倍。

Computed If-Else

1
2
3
4
5
if (getA() != null &&
getA().getB() != null &&
getA().getB().getC() != null) {
...
}

寫在同一個 if-statement 很方便,卻造成效能嚴重退化。不如蠢一點的寫法,或者透過 Optional<> 來描述回傳型態。

1
2
3
4
5
6
7
8
9
A a = getA();
if (a != null) {
B b = a.getB();
...
}
getA().ifPresent(a -> {
a.getB().ifPresent(...)
});

List Getter

1
2
3
4
5
6
7
8
LinkedList<Long> X;
void doSomething(List<Long> X) {
for (int i = 0; i < X.size(); i++) {
long x = X.get(i);
...
}
}

別鬧了,這會出大事。效能殺手就是你。LinkedListget(index) 可是 $O(n)$ 的。

Immutable Methods

1
2
3
4
void parse(String elem) {
elem.trim(); // ??????, elem = elem.trim();
...
}

記得把回傳值接起來,請不要陡增效能問題。

Method Reference

1
2
3
4
5
6
7
8
9
10
Map<Long, List<Point>> map;
void add(Point a) {
List<Point> list =
map.computeIfAbsent(a.mX, key -> new LinkedList<>()); // X, Point::prepare
}
static List<Point> prepare(Long key) {
return new LinkedList<>();
}

盡量使用 method reference,防止 memory leak,也降低 lambda metafactory desugar 的花費。

Boxing

1
2
3
4
5
6
7
Double getRotate() { // X, double
double r = ...;
return r;
}
boolean getMirror() {...};
Boolean isMirror = getMirror(); // X, boolean

既然有預設值也確保不會發生 null,請不要過度包裝。拆拆裝裝的狀況會造成垃圾過多。

Exception is NOT a Return Value

1
2
3
4
5
6
7
8
public String getFileExt(File f) {
try {
String token = parseExt(f);
return "." + token;
} catch (NullPointerException e) {
return null;
}
}

請別接收這麼奇怪的 runtime exception。在 Java 中,exception 很昂貴的,造價就是整個 call stack。

也別這樣追蹤物件的建立,大量物件會造成內存不足。

1
2
3
class Point {
private Throwable trace = new Throwable();
}

Lightweight Exit

1
2
3
4
5
void process(Point p) {
List<Long> array = new ArrayList<>(10000); // ?????
if (p == null)
return;
}

別急著建立一堆用不著垃圾,有可能在後續判斷中直接返回。盡量縮小變數的生命週期,快用到的時候再準備計算資源。

If-Elif-Else

1
2
3
4
5
6
7
8
9
if (token.equals("a"))
{
}
else if (token.equals("b"))
{
}
if (token.equals("c"))
{
}

別說排版不重要,那一定是沒看過有人不小心漏了什麼。在大部分情況不太會出事,只是多判斷了幾次造成效能退化。

Dead instanceof

1
2
3
4
5
6
7
8
9
10
public abstract class Shape;
public class Poly extends Shape;
public class Rect extends Poly;
void write(Shape shape) {
if (shape instanceof Poly) {
} else if (shape instanceof Rect) {
// ?????, unsearchable
}
}

凡事有先後,請注意繼承關係。

Observer Pattern

1
2
private List<ObsListener> list = new LinkedList<>();
private Set<ObsListener> list = new HashSet<>();

當訂閱者數量不少,且容易進進出出,請不要用線性的 LinkedList。當你需要嚴格地再現 BUG,就不要使用不穩定順序的 HashSet,請使用 LinkedHashSet 是一種保守的選擇。

Remove Observer

1
2
3
4
5
6
class CreateUI extends Dialog {
public CreateUI() {
db.addListener(mChangeListener);
}
// where is your db.removeListener
}

別忘記移除掛載到資料庫的觀察者,這樣往往覆覆操作,越來越慢真的不能怪人。

Opposite Behavior

1
2
assert pathA.endsWith(pathB) ==
pathB.isEndOf(pathA); // fail ??????

英文函數命名上,操作對稱就該對稱。英文不好要先說,邏輯不好也先說一聲,大家可以幫忙的。

Global Garbage

1
2
3
4
5
6
7
static List<DbObj> tmp;
List<DbObj> getXXX() {
tmp = new LinkedList<>();
parallel...
return tmp;
}

別擠壓到下一個人的生存空間,要是沒有使用 getXXX,會看到一堆資料庫物件被卡在全區變數裡頭。

Useless Argument

1
2
3
4
class Path {
boolean startsWith(Path p);
boolean startsWith(Path p, Object a); // new one
}

別因為不想改動原本的,建立一個一模一樣名字的函數,而且第二個參數並沒有使用到,overloading 不是這樣子設計的。

Count

1
2
3
4
int getPointCount() {
return mPoints.parallelStream().count();
// return mPoints.size();
}

可以覺得慢,但不要總是開平行解決事情。這種計數問題,通常都有相關的方法可以呼叫。如果沒有,請聯絡相關人士。

Tooltip

1
2
3
String tooltip = ""; // should StringBuilder
for (DbObj t : db.getObjects(XXX.class))
tooltip = tooltip + t.toString();

沒人說這樣不好,除了串接消耗 $O(n^2)$,一般也不會把所有東西拉出來。

Convert Set to Array

1
2
3
4
5
6
List<Point> toArray(Set<Point> set) {
List<Point> arr = new ArrayList<>();
for (Point e : set)
arr.add(e);
return arr; // return new ArrayList<>(set);
}

建構子更方便,別這麼辛苦,效能至少慢了兩倍。

演算法還是有它的極限在的,常數的確不是很重要,但是數量一大的時候,均攤造成額外操作造成的垃圾,在 Java 中會變得相當明顯。

Error Message

1
2
3
4
5
6
7
8
9
10
11
Integer parseInteger(String x) {
String errMsg = x + "is an invalid integer format...";
errMsg = attachCurrentLineMessage(errMsg);
try {
Integer n = Integer.parseInt(x);
return n;
} catch (Exception e) {
System.err.println(errMsg);
return null;
}
}

人家還沒出錯,先別急著準備錯誤訊息。提前準備的字串複雜度比處理的複雜度還高,這絕不允許。

New Option

1
2
3
4
5
static void import(boolean a);
static void import(boolean a, boolean b);
static void import(boolean a, boolean b, int c);
static void import(boolean a, boolean b, int c, String d);
...

別再為了新參數往上疊,請用更容易看出參數意義的 builder 的寫法。

越來越多的參數,造成容易寫錯傳參的順序的悲劇,這時候 BUG

Read More +

可持久化陣列 Persistent Array 始

回顧

幾年前,跟 liouzhou101 一起搞了很多記憶中系列題目,有一題與陣列很相似,但操作更複雜一些。陣列的操作只有下列幾種

  • get(index): 回傳索引為 index 的元素,其中 $\text{index} \in \left [0, n-1 \right ]$
  • set(index, value): 修改 index 上的元素
  • pushBack(value): 陣列尾端後接一個新的元素
  • popBack(): 移除陣列尾端的最後一個元素

從演算法課程中,我們學到 C++ 中的 std::vector 可以做到均攤 $\mathcal{O}(1)$,其大致的做法為陣列快填滿容量時,倍增其大小後轉移原先的所有元素到新的容器上,均攤計算為每次增加的元素都需要預先支付未來轉移自己、轉移對應的另一個元素、移除自己、移除對應的另一個元素的花費,因此均攤花費為常數。

而這樣子的均攤操作在可持久化卻是不利的,因為單一操作的最慘複雜度為 $\mathcal{O}(n)$,意味著可能在同一個操作上,使用 $m$ 次持久化會造成時間複雜度退化成 $\mathcal{O}(mn)$。因此,我們需要最小化最慘時間複雜度的結構。

當年初學者的我,切入觀點有二元樹 (binary tree)、塊狀表 (unrolled linked list),前者讓操作必為 $\mathcal{\Theta}(\log n)$、後者為 $\mathcal{\Theta}(\sqrt{n})$,從理論分析上一定優先選擇前者實作,但如果操作有特別的比例問題,如 get(index)pushBack() … 等,這時候快取能力好的塊狀表反而有優勢,二元樹因指標的使用導致整體的內存使用率不高,透過 2-3 tree 那一種將節點儲存多個元素的設計,就相當於把塊狀表拉成樹狀,其效果也不錯,但在計算上會更需要耗費工夫。

塊狀表 (Unrolled Linked List)

任何操作皆為 $\mathcal{\Theta}(\sqrt{n})$,修改操作皆需要複製整個節點。在可持久化情況時,預先每一個塊的大小較為不可行,故做不到動態調整塊狀大小。

二元樹 (Binary Tree)

利用二元樹建立可持久化的情況有很多種編碼,以及紀錄節點的優化方式,這將會影響到我們的效率。盡可能地不在節點中儲存欄位 size 即可達到索引。若二元樹節點定義為

1
2
3
4
5
6
class Node<T> {
Node *lson;
Node *rson;
int size;
T value;
}

葉與內部節點皆帶有元素值,那麼在陣列的新增刪除尾端的操作,我們可以透過類似 heap 的方式,將其設計成不用旋轉操作、不用紀錄樹大小的編碼。當節點編碼為 $k$,則兩個子節點 $2k$$2k+1$,實作時只需要紀錄整體大小,接著在走訪過程中,採用位元運算得到其子樹大小作為操作依據。

1
2
3
4
5
6
7
1
/ \
2 3
/ \ / \
4 5 6 7
/
8

這樣的編碼問題,對於陣列實作時,發現 push/set(index, value) 時,時間複雜度為 $\mathcal{\Theta}(\log \text{index})$,那動態將 $n$ 個元素推入的時間必為 $\mathcal{\Theta}(n \log n)$,靜態建造則為 $\mathcal{\Theta}(n)$。索引值越大的元素,其操作花費越高。

設計函數庫時,我們通常希望盡可能地讓複雜度對稱,也就是兩端的索引速度不會差太多,即使是亂數也好,因為演算法設計、真實生活中的應用大多都會偏向一方,很可能總是觸發最慘情況。

Braun Tree

另一種編碼設計,對於每一個節點皆滿足右子樹大小最多比左子樹大小多一個,由於每一個節點都滿足,按照插入順序,可以得到下圖

1
2
3
4
1
2 3
4 6 5 7
8 10 12 14 9 11 13 15

明顯地,如同霍夫曼編碼一樣,這一個 1-indexed 的情況,最低位 0 則往左子樹、反之為右子樹。每一個操作皆為對稱的,但複雜度如同一般的二元搜尋樹,作為陣列操作也不滿足期待。

若用於可持久化陣列的基底,代碼量非常少,遞迴定義使得操作簡單,我們甚至可以連整體大小都不用儲存,透過其遞迴定義可在 $\mathcal{O}(\log^2 n)$ 得到,但大部分陣列使用都是會希望 A.size() 是可以在 $\mathcal{O}(1)$ 完成的。這樣的設計在優先隊列 (priority queue) 更友善,因為鮮少需要去拿到 size,只需要回傳這個優先隊列是否為空。

同樣地,這依舊不是實作可持久化陣列的首選。

線段樹 (Segment Tree)

線段樹的設計有一個缺點,大部分的情況總是預先知道大小,然後再代入修改操作。

如果要做到動態的增加大小,則採用 top-down 的展開節點方法。如根節點一開始設計範圍為 $\left [0, 2^{32} \right ]$,當我們 push 一個新的元素至尾端時,相當於開出一個葉節點為 index = size,同理 pop 操作。一開始預設最大上限 $M$,單一操作的時間複雜度必為 $\mathcal{\Theta}(\log M)$

以上述的狀況,每一次操作複雜度必為 $32$,作為函數庫的設計而言,這樣的寫法沒有彈性,而且要是未來超出指定大小,修改就非常的緩慢,更因為在持久化的環境下,不可能在對數時間內轉移其架構。

Leftist Leaf Tree

其概念類似二項堆積 (binomial heap),我們將使用 $\log n$ 棵樹表示整個序列。將內容放置於葉節點上,並且每一個樹皆為完美樹,無須額外紀錄子樹大小。

例如:當 n = dec(11) = bin(1011) 時,用三棵大小分別為 8, 2, 1 的樹表示之。當 push 一個新的元素至尾端時,與最右邊的子樹 1 合併成大小為 2 的樹,再與左邊的子樹合併成大小為 4 的子樹,最後成為 n' = dec(12) = bin(1100),用兩棵子樹表示之。同理 pop 操作,模擬二進制的退位。

每一個操作皆為 $\mathcal{O}(\log n)$,且分布較為一般的二元樹均勻。並解決一開始我們在二元樹上遇到的問題,動態將 $n$ 個元素推入的時間,整體複雜度為 $\mathcal{\Theta}(n)$。因此,這是目前實作可持久化隊列的首選。

其他

函數式理論複雜度最好的結構為 finger tree,實作複雜度相當高,卻具備了合併兩個陣列的特殊操作,這是以上結構皆不具有操作。實際的效能無法預測,通常常數過大而無法使用。有朝一日,我們再來挑戰這偉大的結構吧。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

Read More +

可持久化應用雜談

可持久化的實際用途到底有哪些?這麼複雜的概念大部分場景都用不上?

函數式編程

其不可變的需求,造就了持久化的使用。如果是可變的特性,函數式展開的一對多操作時,就會造成操作失效,除蟲大概是一輩子的痛。以 Java 的 Stream 為例

1
2
3
4
paths.stream()
.flatMap(path -> {
return Stream.of(path.add(a), path.add(b));
});

這樣的函數還算清晰好懂,一旦包了好幾層函數下去,就不曉得 path 到底是能不能被修改。如果不可被修改,意味著每一次都要回傳一個實例,那麼可想而知效能一定不會太高 (大部分的代碼都是整個數據複製)。別去想什麼黑魔法可以在常數時間解決、相信未來人可以穿越時空幫你完成即時計算。請面對現實,計算機終究還是一行一行去執行的。

在編程概念的分支中,函數式編程本身需要這一種技術,達到其函數定義的規範。這一種寫法的效能不好,能理解的人也不多,其一原因學校沒有強制要求去學,一開始都是從程序式、命令式、物件導向式著手居多,所以到工作階段也不太可能遇到大型程式的需求,不過一旦遇到就無可取代。

離線算法

將離線版本切換成強制在線,不用特別去構造一個全新的資料結構來解決問題,只需要預處理一部份的資料,並犧牲更多的記憶體空間來完成。

幾何計算

在幾何計算中,有很多離線算法很容易被找到,一個掃描線掃過去回答所有問題,在時間複雜度分析上總是相當優異的。那如何強迫在線的情況下,每一次都掃描一次,詢問操作的時間複雜度就從對數時間降成線性。為了解決這一種情況,持久化技術給了另一種思維,我們將掃描線的時間軸作為一個變動依據,持久化相關的結構,只要我們能將詢問在對數時間內穿梭於這個時間軸,必能動態解決先前的問題。

統計方法

在 OI 界的經典問題,區間 K 大、攤平成一維陣列的相關計算,問題本身不帶修改操作,只詢問統計於此的統計操作。通常可以透過持久化結構來完成,區間就相當於時間軸,我們能針對兩個時間戳記之間的差異變化來完成統計。

字串處理

為了達到非常高效率的合併操作,防止大量重複性字串的生成伴隨的效能退化,使得各方面的操作都能遠低於線性操作。如 C++ rope 就是一個持久化的資料結構,

不只是字串操作,若處理類型有大量重複的情況,持久化的概念便能派上用場。

版本回溯

實際上就是對應大部分的應用軟體中的 redo/undo。如果資料庫/操作變動為了高效率操作而會配上複雜的結構 (並不像 hash, set 反轉操作只需要常數或對數時間),那麼為了快速回推變動結果,持久化結構就是要減少 redo/undo 的花費。

根據工作上遇到的經驗,資料庫本身可以常數回推,紀錄變動的部分情況即可。而應用層的計算,大部分實作都是砍掉快取,並且重新計算出一份新的結構,有時候回推的變動大小為 m,為了重新計算結構而消耗了 n+m,如果 n 和 m 的差距非常大,那連續回推的體感就很糟糕。

其他

更強硬一點的叫做 Confluent Persistence,可以讓兩個不同的版本合併一個版本,感覺起來就相當於兩個平行宇宙要合併,實際的應用更少一些,大部分應該是在兩個資料結構的合併,如兩個堆如何合併,兩棵伸展樹的合併 … 等的底層定義所需。

Read More +

可持久化雙向隊列 Persistent Deque 續

接續前一篇 《可持久化雙向隊列 Persistent Deque 序》,同樣的概念,Okasaki 用了他那精妙的公式描述了前一篇採用的策略只不過是常數 $c = 3$ 的情況,實際上可以根據需求去改變常數 $c$,先決條件 $c \ge 2$

預先評估雙向隊列 (Pre-Evaluation)

  • SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

同樣地,雙向隊列為兩個堆疊表示,並限制其中一個大小不能大於另一個的 $c$ 倍,如果發生了用另一種方式表示部分翻轉的結果。

Invariants

$$\begin{aligned} & |L| \le c |R| + 1 \; \wedge \; |R| \le c |L| + 1\\ & |\hat{L}| \le \max(2j+2-k, 0) \; \wedge \; |\hat{R}| \le \max(2j+2-k, 0) &\\ & \text{where} \; j = \min(|L|, |R|) \; \wedge \; k = \max(|L|, |R|) \end{aligned}$$

Functional Definition

$$\begin{align} \left [ \; \right ]_{d} &= \left \langle \left [ \; \right ], \left [ \; \right ], \left [ \; \right ], \left [ \; \right ] \right \rangle \\ |\left \langle L, R, \hat{L}, \hat{R}\right \rangle| &= |L| + |R| \\ \textit{insert}L(e, \left \langle L, R, \hat{L}, \hat{R}\right \rangle) &= \textit{makedq}\left \langle e:L, R, \textit{tl}\; \hat{L}, \textit{tl}\; \hat{R}\right \rangle \\ \textit{insert}R(e, \left \langle L, R, \hat{L}, \hat{R}\right \rangle) &= \textit{makedq}\left \langle L, e:R, \textit{tl}\; \hat{L}, \textit{tl}\; \hat{R}\right \rangle \\ \textit{remove}L\left \langle L, R, \hat{L}, \hat{R}\right \rangle &= \left \langle \textit{hd}\; R, \left [ \; \right ]_d \right \rangle & \left \{ |L| = 0 \right \}\\ &= \left \langle \textit{hd}\; L, \textit{makedq} \left \langle \textit{tl} \; L, R, \textit{tl} \; (\textit{tl} \hat{L}), \textit{tl} \; (\textit{tl} \hat{R}) \right \rangle \right \rangle & \left \{ |L|> 0 \right \}\\ \textit{remove}R\left \langle L, R, \hat{L}, \hat{R}\right \rangle &= \left \langle \textit{hd}\; L, \left [ \; \right ]_d \right \rangle & \left \{ |R| = 0 \right \}\\ &= \left \langle \textit{hd}\; R, \textit{makedq} \left \langle L, \textit{tl} \; R, \textit{tl} \; (\textit{tl} \hat{L}), \textit{tl} \; (\textit{tl} \hat{R}) \right \rangle \right \rangle & \left \{ |R|> 0 \right \}\\ \textit{makedq}\left \langle L, R, \hat{L}, \hat{R}\right \rangle &= \left \langle \hat{L}, \hat{R}, \hat{L}, \hat{R} \right \rangle, \; \begin{aligned} \text{let} \; n &= \left \lfloor (|L| + |R|)/2 \right \rfloor \\ L' &= \textit{take}(n, L) \\ R' &= \textit{rot1}(n, R, L) \end{aligned} & \left \{ |L| > c |R| + 1 \right \} \\ &= \left \langle \hat{L}, \hat{R}, \hat{L}, \hat{R} \right \rangle, \; \begin{aligned} \text{let} \; n &= \left \lfloor (|L| + |R|)/2 \right \rfloor \\ L' &= \textit{rot1}(n, L, R) \\ R' &= \textit{take}(n, R) \end{aligned} & \left \{ |R| > c |L| + 1 \right \} \\ &= \left \langle L, R, \hat{L}, \hat{R} \right \rangle & \left \{ \text{otherwise} \right \} \\ \textit{rot1}(n, L, R) &= \textit{hd} \; L : \; \textit{rot1}(n-c, \textit{tl}\; L, \textit{drop}(c, R)) & \left \{ n \ge c \right \} \\ &= \textit{rot2}(L, \textit{drop}(n, R), \left [ \; \right ]) & \left \{ n < c \right \} \\ \textit{rot2}(L, R, A) &= \textit{hd}\; L : \; \textit{rot2}(\textit{tl}\; L, \textit{drop}(c, R), \textit{rev}(\textit{take}(c, R)) + A) & \left \{ |L| > 0 \wedge |R| \ge c \right \} \\ &= L + \textit{rev}R + A & \left \{ |L| = 0 \vee |R| < c \right \} \end{align}$$

放眼望去共計 15 條式子,而一半都是對稱操作。唯獨在式 12 到 式 15 較為特別,相當於前一篇的反轉操作,只是我們透過額外的定義來描述它,實作時相當多一個類別。不管是記憶體分析、還是時間複雜度分析,原則上與前一篇是相同的。

公式裡描述了一堆的 $\hat{L}, \; \hat{R}$,我們卻沒有在任何的條件式中使用,只作為我們去理解操作的含意。因此,實作時只在 $makedq$ 區域變數中作用,並不會成為一個必要紀錄的值。

特別注意到建構子中,令 $R' = \textit{rot1}(n, R, L)$,這個操作可能直接成為 $\textit{rot2}(L, \textit{drop}(n, R), \left [ \; \right ])$,思維必須往前看一步去轉化所有實際的類別,否則很容易在相關操作退化。因為 $L, \; R$ 都是作為 rot1 或者是 rot2 後的產物,盡可能地使之成為最簡單的表達式。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

Read More +

可持久化雙向隊列 Persistent Deque 序

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

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

Read More +

可持久化隊列 Persistent Queue 續

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

Read More +

可持久化隊列 Persistent Queue 序

前言

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

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

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

需要以下操作:

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

Read More +

可持久化堆疊 操作 Persistent Stack Operators

接續前一篇 《可持久化堆疊 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 ]
Read More +

可持久化堆疊 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 為主,又細分成好幾種操作。即使運行結果相同,造就的效能與可拓展性也不同,如 reducecollect 的差別,都能將一系列的元素縮合成一個,但是 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 個堆疊,每一個堆疊指向堆頂元素。對於加入一個元素到堆疊,我們就額外多一個節點指向先前的堆疊;相同地,移除堆頂元素時,回傳前一個堆疊結果。

1
2
3
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]

相應的儲存圖

1
2
3
4
5
6
7
8
9
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/immortal-jellyfish

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package persistent.stack;
import persistent.PStack;
/**
* @author morrisy
*
* @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();
}
}
Read More +