Java 8 開始推出了 stream 介面，搭配 lambda 可以達到函數式編程 (functional language) 的能力，但是也造成非常多的效能爆炸的憾事。尤其是在我們沒有深入了解官方實作的細節時，請別輕易地轉換到 stream 介面。

Stream

在 Stream 出現之前，我們可以透過 Iterator 的實作來達到串流的概念，如 guava 庫所提供的 FluentIterable 就是一個替代方案。公司內部則是因為維護問題自己實作了一個自己的庫，因此沒辦法輕易地用 guava 的項目。但其中一點很明顯的不同在於 parallel 並行特性，即使是 FluentIterable 中，我也未見相關的平行操作。

在自己實作庫、人手不足的團隊配置下，直接吹捧去使用現有的函數庫，那麼問題就容易出現在於轉換上。必須考慮「何時我們該去使用」，決定好使用場景，再決定是否要改寫。公司已經升級到了 JDK 11 的，在銜接官方的 stream 實作時，依舊造成顯著的效能退化，甚至還有嚴重的運行問題，導致 dead lock 等問題。

Static Initialization Block

1
2
3
4
5

class classA {
    static {
        getXXX().parallelStream().forEach(e -> doSomething(e));
    }
}

在 JDK 11 中，可能會無知地不小心在 static initialization block 中觸發 parallel 特性，此時會造成程式無法運行、卡住。這個問題在於 threading 之間調度時的鎖，另一部分則是 lambda 抓取變數造成的。目前在 bug JDK-8143380 回報系統上看出無意解決此問題，因為這是人為撰寫的問題。如果是呼叫大量的函數來初始化參數，很容易遇到不知道哪個函數區塊內偷偷開了平行計算。

像同事都把 stream() 都改寫成 parallelStream()，不管問題是大是小，這樣改寫有時候就造成莫名其妙的 Bug 發生，造成找了半天才發現問題。如果覺得著官方提供的項目都有公信力，而且不會做很蠢的事情，一直都可以很聰明地在平行與不平行取捨的話，那其實也不用設計 parallelStream() 給我們使用，統一一個 stream() 接口就好。

想到同事如此狂妄的想法「工程師不該考慮資源，從摩爾定律來看，硬體明年就會解決，我們要做出更好的 scalability 的寫法」，讓我整個火氣都上來，無法接受 用而不知 的習慣。在沒人力挺下，只能眼真真地看著代碼被改得亂七八糟。

Stream Cost

了解 Stream 基礎實作後，就會明白在沒有平行的狀況下，維護 stage 的狀態會是額外開銷，相較於手刻的 Iterator，很多沒有必要的狀態紀錄容易在非常簡單的迭代器中暴露。

Stream Concatentation

串流串接又是更可怕的實作技術，請參閱附錄文章 Efficient multiple-stream concatenation in Java。

1
2
3
4
5
6
7

                                       concat(concat(concat(a, b), c), d)
                                      /                                 \
               concat(concat(a, b), c)                                   d
              /                      \
  concat(a, b)                        c
 /           \
a             b

串接的實作像是二元樹。如果操作順序不當，馬上會產生一棵偏斜的二元樹，假設我們要取 a 裏頭的元素，則必須從根一路走到葉節點去。如果構造 $n$ 次操作，且每一個恰好為一個元素，蒐集所有的內容，時間複雜度為 $O(n^2)$。

因此，亂改寫遞迴構造器很容易出現問題，不如用原本的回傳值 List/Collection 把要的東西收集好，不支援惰性操作也好，舊的寫法依舊在 $O(n)$ 完成。若要支援惰性操作，使用 StreamBuilder 建立平衡的二元樹也能在 $O(n \log n)$ 最慘複雜度下完成迭代。

這個問題並不是開 parallelStream() 解決，必須從根本的複雜度去分析，

Iterator to Stream

從內建的 Collection 到 Stream 大部分都由官方做得很好，用不著花太多的心思去思考如何實作，直接呼叫相關函數即可。如果工作需要自己的 Iterator 變成 Stream 就沒有這麼好運。必須了解什麼是 Spliterator，而 Spliterator 是怎麼實作的，會有什麼樣的介面，而它是從何支援 parallelStream 這一項特性。

假設您已經詳讀 Spliterators.java 下的所有代碼，如自動建造函數

1

static <T> Spliterator<T> spliteratorUnknownSize(Iterator<? extends T> iterator, int characteristics)

標示不確定迭代器實際運行的元素個數，好比在 stream 的 flatMap() 和 filter() 後，無法得知下一階段的元素多寡。在這些情況下只能透過這一類函數構造。然而官方預設的行為卻造成了嚴重的效能問題，它要求建造一個 IteratorSpliterator，而為了支援平行特性，平行通常需要透過高效的拆分陣列完成工作分配，因此會呼叫 Spliterator::trySplit 不斷地拆分，從源代碼中我們可以得知在未知大小的狀況下，則建立 new Object[1024] 預處理資料結構，即使在沒有開啟 parallelStream，依舊按照相同的運行流程。

有人說在 Java 開 new Object[1024] 很快，而最慘情況迭代器就只有一個元素，甚至沒有任何的狀況下，用最蠢的實作只消耗了一個迭代器的宣告開銷，而轉換串流卻消耗了整整數千個位元組，這是個效能損耗。就算 GC 很強，也不代表它能發現這麼複雜的操作，它整整跨足了超過一個函數區塊。

工作中因為繪製處理，需要運算數億次，若每一次都宣告這麼多餘的陣列，那麼莫虛有內存損耗高達幾十 GB，GC 若要運行 10 次，畫面繪製需要多一分鐘都是有可能的，將數秒不到的計算整整拖累下去。

Lazy Evaluation

惰性計算是 stream 的主要特性之一，從另一個術語按需計算 (on-demand)。即使是官方提供的庫也有一些小 Bug 造成假的惰性計算。最常見的像是 flatMap、map 和 filter 混用的時候，最後使用 findFirst 操作。從代碼上，我們會預期差不多就是找到一個元素之前的所有計算，而從回報系統裡面下關鍵字去找，會發現不少多餘的計算發生。

同事老是說「我們自己的庫超慢的，用 stream 比較快。」

言下之意，只是沒有遇到官方庫的 Bug，而你看到了庫的 Bug 卻從沒打算解決。

最常見的迭代器實作，忘了 Lazy Evaluation 的寫法如下：

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

class MyIterator<T> implements Iterator<T> {
    ...
    @Override
    public T next() {
        if (!hasNext())
            throw new NoSuchElementException();
        T val = nextVal;
        findNext(); // on-demand ?
        return val;
    }
    @Override
    public boolean hasNext() {...}
    private void findNext() {
        ... // time complexity ?
    }
}

很明顯地，透過 findNext() 我們可能只拿了第一個元素，在不需要第二個元素的狀況下，卻耗費了線性時間。

Note

還有一些問題，下一次再聊聊吧。

Reading List

• 3 Reasons why You Shouldn’t Replace Your for-loops by Stream.forEach()
• Efficient multiple-stream concatenation in Java

Java

Setter/Getter

1
2
3
4
5
6
7

class Parser {
    X getX() {}
    boolean x() {}
    boolean readX() {}
    void parseX() {}
    void X() {}
}

Java 特性預設都是透過 setter/getter 的概念來完成成員變數的存取。為了擴充使用不建議直接存取變數。

這毫無設計的函數是發生甚麼事情？名字這麼像是想害死誰啊，而且還都是不同邏輯。

1
2
3
4
5
6

class Parser {
    X eX() {}
    boolean aX() {}
    boolean sX() {}
    void pX() {}
}

不是這樣子說完，就用奇怪的前綴解決。把整個動詞完整描述出來會讓你打字很痛苦嗎？

Inner/Anonymous Class

現在我們用一個指令去搜尋建立的 class files。

1
2
3
4
5

$ find ./bin -name "*\$[0-9]*.class"
xxxx$1$1.class
xxxx$64$1.class
...
xxxx$64$64.class

居然發現了非常非常多的匿名類別，而且還是爆炸性的嵌套。這意味者當改變一個 class 檔案時，編譯會一次可能產生上百個檔案。

1
2
3
4
5
6

boolean getToken() {
    return new Token {
        @Override
        public String toString() { return "here we are"; }
    }
}

這也是常常在調適函數時，不知道為什麼會有 IDE 崩潰的情況發生。其實都是上述的寫法氾濫，連帶的內存洩漏問題也很嚴重。事實上，大部分的匿名類別都可以額外地用功能去描述類別，請重新宣告並且命名好。

Long Name Method

1
2
3

void addXXXsToAdjacentYYYsSetSoItWillNotAAABBBWhereMMM();
void setXInDatabaseAAABBBField();

這種命名函數比惡名昭彰的匈牙利還兇殘，直接把文件描述寫在函數上，這時候又願意打字了。

請找個稍微中立一點描述方法，等到哪天換了連帶功能，所有相關函數都要重新做過。

Create Context

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

boolean read() {
    try {
        readPartA();
        externalCall();
    } finally {
        setCacheEnabled(true);
    }
}
boolean readPartA() {
    setCacheEnabled(false); // why not place it in read()?
    ...
}
// in external.xxx
java::setCacheEnabled(false); // what are you doing?
...
return true;

建立 context 的習慣是要寫在同一個檔案中，而且盡可能寫在同一個函數內。

跳來跳去，有時候只有下文，有時候只有上文，不覺得很可怕嗎？萬一中間執行失敗，直接萬劫不復。

Create Context II

1
2
3
4
5

boolean read() {
    db.setDbCheckEnabled(false);
    ...
    // where's your setDbCheckEnabled(true);, can I trust you more?
}

直接把所有重要檢查通通關閉，卻忘了開起來，直接出逃啦。

Create Context III

1
2
3
4
5
6
7
8
9
10

boolean read() {
    try {
        db.setDbCheckAEnabled(false);
        db.setDbCheckBEnabled(false);
        ...
    } finally {
        db.setDbCheckAEnabled(true); // setDbCheckBEnabled() first, please
        db.setDbCheckBEnabled(true); // setDbCheckAEnabled() last, please
    }
}

大部分都不會錯，但建議採用堆疊的順序撰寫。因為有些保護機制會造成重複工作。

Create Context IV

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

boolean read() {
    try {
        db.setDbCheckAEnabled(false);
        db.setDbCheckBEnabled(false);
        ...
        db.setDbCheckBEnabled(true); // I don't know.jpg
        ...
    } finally {
        db.setDbCheckBEnabled(true);
        db.setDbCheckAEnabled(true);
    }
}

我不知道.jpg。

Regression Test

Create Test Folder

1
2
3
4
5
6

$ tree Regression/FunctionA
├─testBBBB
│  └─testCCCC
│    └─testDDDD
│      └─test.sh
...

為什麼需要前綴 test？請給我一個理由。

Create Test Folder II

1
2
3
4

$ tree Regression/FunctionA
├─DoNotThrowNoSuchElementException
│  └─test.sh
...

如果是預期丟出錯誤的測試就算了，但錯誤的實例也是會變動的，這樣的資料夾名字不具有太深遠的意義。

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 解決問題，這只要開一個有平行工作，另一個工作沒設計好就會自動失敗。

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

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);
        ...
    }
}

別鬧了，這會出大事。效能殺手就是你。LinkedList 的 get(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

舊金山

即將過年時，才知道二月底完要去趟美國舊金山開會，那時美國疫情還沒有大爆發。面對跟著主管一起出國的情況，緊張的心境已經釋懷，那時還不知有多少人會跟著去，只想著這次順便去看組織改組的同事有哪些人，並沒打算規劃順便玩什麼行程。

由於時間有點趕，只有兩周的時間準備，也不知道去的實際目的，要準備的相關報告內容，連剛進來兩個月的菜鳥也跟著去，由於不是每個人都有去，能倚靠的人不多，另一個進來快一年的學弟被邀請去，這多少有點不妙的預感。

從早開到晚為期一周的密集會議，並沒有像波士頓有個悠哉的下午。顯然地，在充滿華人組織的西岸和洋人的東岸風格不同，汲汲營營的華人文化，每一刻都相當地重要。工作起來相當辛苦，也嚴謹很多。

在聖荷西的分公司，擁有數千人的團隊，還有正統的公司餐廳？而我們人數只有個位數，開會起來明顯沒什麼說服力，高階主管們說什麼是什麼。產品大部分小功能也都幾千行，對於 EDA 的貢獻也只在規劃工具，而不是負責最實際的實作工具，說話力道與市場規模實在不大。

唯一的優勢就是近期的 3D IC 封裝，開始走向一次構築整個版子。雖然沒辦法像實作工具規劃走線細節，作為一個高層級的規劃工具可以一次展現百億個物件分布與管理，只是比 Excel 好用一些吧。

一連串開會下來，大概明白自己在組織裡面排在哪個位階，也能從一些會議主持上看出各部門的信賴、依賴圖。不得不說，公司還真的很接近三個人種分部門，分別是亞洲、印度及歐美，分別主導不同層級的產品。想必在相同母語與文化上，這樣開發才是最容易的組織發展，怪不得這次改組將大部分的人都塞進這個亞洲圈。

途中若都是亞洲人的會議，用中文開會，途中若出現外國人，就下一秒切成英文會議，在一旁觀看略有風趣，龐大的專有名詞庫，最後也搞不清楚到底是在講中文還是英文。那被抓去的另一個目的是什麼呢？應該是主管報告產品功能時，緊急救火隊在一旁修 BUG 和評估是否能支援突然拋出的問題。

接下來的事就不有趣，菜鳥是個雷隊友的事實逐漸明瞭。回想在搭飛機前說了要留著餘額刷旅館信用卡，千萬別玩手遊刷爆，結果當晚入住時還是刷不過，原來是出發前刷了一台手機。這也許還不打緊，回旅館打算去隔壁的購物中心，幫公司同事買台 switch 回台灣，沒想到菜鳥卻回說「回房間玩手遊」正準備在大廳做簡報的主管在一旁聽到，說道「不一起去嗎？」。我想徹底的社畜就是下班不認識吧，最後一個人摸黑走去購物中心買。也許是中國疫情爆發，店員看到這一臉黃種人也沒問太多，比起害怕說英文的我，那種中國式恐懼無法比擬。

令我感到最微妙的是，開會一直補零食咖啡，看到主管們正在報告的當下，菜鳥卻三番兩次地繞到後頭拿零食回來吃，也許是不同成長背景下的關係，看起來非常低水準的行為，讓我都不好意思坐在一旁聽講。這讓我想起，在剛進來的幾個月時，主管曾說我們家教都還不錯，在這些小動作中，就能略知一二吧。

在家工作

回國時已三月初，疫情開始大爆發，之後便開始在家工作。決議內容其實多到不太可能在短時間內規劃得好，在屈指可數的開發人力下，不讓產品崩盤就很不錯，交代下來的事情，從回程飛機的等待時間，跟主管談論這次的各方面狀況，也談到為何讓菜鳥也跟著來，一次要出個十幾萬讓幾個人飛過去開會，這對公司也不容易。談論內容就留著大家自行想像。

在家工作並沒有想像中得好，完全看各位的自制力。然而，公司 IT 部門開始封鎖了許多網站，如 Youtube, Netflix … 等，發現 VPN 承受不住大量的居家工作者，可見有多少人平時上班會佔據這麼多的網路資源。由於在家工作，各種事情討論都在線上會議中。同時，由於部門改組，每周、每雙周、每月開始有固定會議，不健康的社畜生活就此展開。

越來越少去公司，忙得事情卻越來越多，周一催計畫 A、周二催計畫 B、周三開個會、周四解決緊急需求、周五做計劃。這些堪比大學修課，每天都在準備隔天的課程作業似的，單純做報告也許還好，老實說開發一個大功能並不太合適，實驗都還沒跑完整，隨口說出來也是浪費大家時間，畢竟誰也不會插手幫忙誰的，並沒有實際討論的價值，頂多出事知道要找誰。

看著每周報告的計畫項目中，開始出現了負責人指向自己，壓力大了不少。更煩躁的是，有好幾個項目旁邊都有著自己的名字。人力不足，卻必須這樣搞的話，心境相當崩潰。對於系統功能而言，也與一次負責好幾項很正常，但每周都得對項目報告進度，這個就有點分身乏術。變相結果，在每天稍微撥點時間每個都推一點進度，開始進入分時工作。有些同事並不會這樣子，負責一項慢慢推就好，怎麼說都心理不平衡。

開發

新功能要做，舊功能要顧、還要寫教學文件給未來菜鳥使用，不時還會因為同事寫出糟糕代碼而氣憤。每次做簡報分析要怎麼寫，看來都做了白工。在某一日，直接開幹，不得不在線上會議直接說出來，我所說的話，又有多少可信度呢？的確，我也會犯自己說過的錯誤，做了全自動的反饋系統後，照理來講定時要去修正那些潛在錯誤。然而，對於某些人而言，潛在錯誤不算錯誤，只要還沒有錯，那就是對的。

由於人力不足，工作分配上有明顯地不妥當，即便希望學著做，有不懂事情就問，但結果並非理想中的發展。不如預期就先看源代碼，自行谷歌可能得到的問題，第一個搜尋結果就是答案的蠢事不斷上演，如何編譯一個簡單的 Java 程式、如何使用 Git 分支、如何快速設定環境變數，這些瑣事拿到關鍵字先上網學習，與其不同的地方再拿出來討論。看到同事以如此沒效率的方式在工作，從繁重的工作中脫身，幫忙處理這些小事，直接氣炸了鍋。

逐漸地，發現測試時間越來越不穩定，log 輸出裡面還吐了不少問題，撰寫的教學文件的錯誤範本一度上演。大多數的問題都是基礎功，基本的語言特性、作業系統的架構、工作的運行流程等，用腦內模擬就知道有各種組合切入點。要怎麼讓大家一起提升素質呢？並沒有辦法。大部分說「我先寫，效能問題你來修。」的狀況，還會很自豪地說「這樣的合作不錯吧？」，在大家都在的場合下能講出這些話，信心十足。寫完之後我砍掉，這到底哪門子的合作方法。

為了壓制不穩定的要素，按照反饋系統的指導逐一修正，再根據歷史教訓不斷地增加測試案例來防堵再次發生，來到了 11% 代碼覆蓋率，相較於半年前提升了一倍之多。在伺服器平行測試從半小時再壓回 20 分鐘，在單機運行就得花上數個小時。平行內的平行資源管理，不要總是資源耗盡，造成誤判逾時，測試不過就跑第二次到底是什麼觀念？怎麼會把這些事情習以為常，要與幾千人的產品整合，那一點穩定度都辦不到，每次都不敢說這產品還能活多久，要是我沒去注意，沒有去做一些髒活，這早就該瓦解了。

產品整合上，外觀圖樣、操作快捷、文字顯示等等都要配合，這對於沒有產品驗證的團隊而言，整個工作落在我的身上，一一對應圖標顯示，還要保留先前的 UI 主題，又要處理跨平台的操作環境，有時還要自己開美工軟體去修圖擺放，怎麼想都不太妙，連 UI 動畫都有一些基礎需求，邊邊角角的幾個像素都要求到位，寫程式的涵蓋範圍可大呢。

因為要處理百億數量級的顯示與檢索更新，得放下新功能開發，回過頭去把問題抓回來解決，測試與分析並不是那一種試誤流程，覺得快不是總是快，當下快不代表以後快，長久的發展沒有人去支持，得花上好幾天驗證的工作，在每周開會的壓榨中，無法靜下來去思考問題。

後談

由於開發的緊迫，心情盪到谷底，想要去找找看新工作，卻被每周開會壓迫，緊急事件不斷，潛在問題不斷暴露需要調查。不幸地在七月初，摔傷了右手臂和腳，包著紗布也趕工。

八月中，受不了自己在忙什麼，找了主管談了一下發展，我再也沒辦法繼續了。家裡嫌賺得少，也沒什麼成就，連個女朋友都沒交過，每天就在那邊工作。在工作中什麼都沒有發展，依舊是那三年前的我。

工作

距離上一次編寫日記到現在已過五個月，累積著不同的經歷與感受，才能寫出一篇有所不同的日記。然而，工作後每天回寢室不是睡覺就是打個遊戲，周末也沒特別想做什麼，完全地放空就是最好的休閒，這使得寫一篇文章又變得更加困難。一成不變的煩惱，到底能寫些什麼。

單元測試

這幾個月來，總算把單元測試拉了起來，從原本代碼覆蓋率 1% 拉到 6%，測試數量十幾拉到四百多個，這過程最痛苦的就是慢慢將所有代碼重新審視，就會開始發現一堆函數不同名稱卻功能相似，甚至是子集合的概念。有人會說「至少沒錯啊，你改那個做什麼」。的確，只是重複的代碼多了一點，但後續的維護就非常痛苦，一旦這重複的代碼中出了 BUG，我們花了九牛二虎之力修了它，卻發現到處都有，這時候心裡不鬱悶嗎？

程式碼多寡會影響效能嗎？大部分的情況並不會，但是對於 Java 的 JIT 而言，跑越多次的代碼它就會更進一步地優化，把沒有用處的代碼移除，做到跟 GCC O2 的效果類似。這其中最困難的處理操作為另一個函數的子集，大部分的情況下，直接導向到另一個函數是沒有問題的，例外是時間複雜度增加與例外處理的不同，為了處理更複雜的情況，功能越強的函數通常都會有一些額外的邊際效應 (side effect)，這時候就要非常小心。

於是每天就是把上千行代碼、數百條函數裝進腦子裡，然後攪一攪把相同功能的代碼移除。好比，判斷一個圖是否同構，這基本上已經接近 NP-Complete 問題，一下子腦子運轉就會過熱，無法去思考其他的項目。有些人的腦子的確可以完全阻隔思考吧，但是對我來說，潛意識帶動的壓迫卻是無盡的痛苦。

做這一些很無趣，出於使命必須審視它，不然每次呼叫函數都不確定自己在處理什麼，甚至傳錯了組態也不會噴任何錯誤。於是開始加起了無數的防火牆，各種防禦性編程的代碼。果真還有不少代碼使用錯了，造成永遠拿到錯誤的結果，那問題就擴散出去，於是又針對相關函數進行修改，連帶回歸測試都要更新，工程浩大卻沒有產出。

這過程發現一些無理的要求，發現自己努力了好幾個月，依然會有人亂加函數，要解決問題，果然還是要拔除源頭。傳了個完全不到的參數，還特地做了重載 (overloading)，此時心裡就納悶了，這傢伙到底是怎麼想的？「因為原先的代碼我不敢改，但是為了效能我複製了一份，又怕自己忘記於是弄了相同的函數名稱 …」這樣子我有點明白了，永遠不該去用常理去看待問題，問題就是那些思維上的漏洞。

架設了 SonarQube 這一類的代碼品質監控後，上千個 bug、vulnerability 和數萬的 code smell，這幾個月終於把前者壓到三位數，目標是控制在一百內。在這五十萬行的裡，多半程式根本不會用到，也不會讓使用者觸及到。那修到底有什麼動力嗎？只有一個，因為初學者會複製類似的行為，做出一樣的蠢事。

公司在美國那裡的新成員，開始寫的時候總會搞不清楚 Java 的特性，就像從 C++ 跳過來的孩子，常常會忘東忘西地，不斷地複製類似的代碼片段來做事，就像字串常量常常會到處冒出來，實際上這些常量如果會一起變動，就應該用一個變數去取代之，這也方便我們去追蹤使用情況。實際的結果不是，造成了無數問題，升級版本的時候，常量到處找，耗費工時又一堆 bug 有待追蹤。

資料庫

因為製程的進展，大廠開始要求效能，來解決上億物件的資料庫問題，物件存取速度要快，開檔存檔都要更進一步加速。於是又開始放下那些代碼的修正，跑回去研讀資料庫相關的處理，由於 EDA 工具總是自己刻一個資料庫，方便規則的變化以及升降版本之間的問題，更提供鬆散的客製化需求，相當於要求自己刻一個嚴謹的資料庫介面。

除了資料庫的基本理論，還有牽涉到開檔讀檔這種小眾知識，解壓縮與壓縮的效能，在每一個階段的每一種算法中追求內存用量最少，額外宣告變數量最少，盡可能使用位址定位等等，每一步都要精準到位，當處理數量破億時，問題就會放大得相當嚴重。就像原本內存 50 GB 可以開起來，修改完卻變成 100 GB 才能使用，這種算法常數的影響就很嚴重，這些問題甚至不是整體的結果，而是處理的過程。也就是說，甚至要最小化中間過程，否則造成某個時間點是達不到運行需求。最後，記憶體用量少一半，存取速度快兩倍之多。

在這過程中，見識到了各種邪門歪道的升降版本的修正技術，這也造成了無數相依性問題。例如在這個時間點，你所請求的物件並未存在，實際上這段代碼毫無作用，卻也活了無數年，沒有人測試過它，看起來又相當合理。陸陸續續地將這些問題分析與移除，有時不小心修正了，激活了無數功能，卻要花時間更新好幾條的回歸測試。

資料庫接口的重要性影響著整個軟體的效能與穩定性，有時會有人受不了效能而開啟平行計算，那首先的問題是「為什麼會慢？」，並不是單純地「因為慢，所以開平行。」一旦開平行下去，有些問題可能不是真的問題，因為 GC 在平行情況下，遮掩著你對剖析器 (profiler) 的觀感，因為整個停頓點如果偏移一點，就會造成優化的方向都不對。

這麼說也許是理論派吧，信者恆信。因為能解決問題的方法，總是把原先的解法全部砍掉重做，要拿這些說服別人的確是難上加難，這裡也許該相信未來會解決吧，總有一個人會跳出來滅了這個火，也許是像神一般的編譯器、或者是 AI 可以幫你除錯並修改，就不再提及了這些公司鬼故事。

周末

其實已經沒小夥伴在玩楓之谷，身邊認識的人也不會玩這種遊戲，大多都是課金到滿的手機遊戲或者單機遊戲。逐漸地，也不是很想玩遊戲，王沒課金也打不贏，花時間也無法達到那個境界，跟團又要看別人臉色和時間。玩遊戲各路牛馬鬼神的人都有，跟不同文化背景的人打交道相當不容易。

最後，我仍選擇了淡出，周末坐在電腦桌前，開著麥克風，要講著自己不太喜歡的詞，看著那無法理解的笑點，時間久了喉嚨不好受。每天上線，還會有一些不雅遊戲暱稱的人騷擾，不知道是吃飽閒著還怎麼的，難道就這麼有趣嗎？即使封鎖拉黑都沒有，這樣的情況持續一個多月，嘗試去找兇手，卻總是沒有任何音訊。

奇怪的是，總能挑到上線的時候發出訊息，非常高的機率是相關人士。後來有一天，群組還是透露了他們其實都知道是誰搞得，還給出了一堆提示後，仍然不願意告訴我那個混蛋是誰。這樣的狀況仍持續了幾周，依舊只說了「如果要答案的話，下一次線下聚會就跟你說。」，這種說詞，徹底讓我貫穿了所有雲雨。

明知答案為何，卻老是不願意透露。這讓我想到寫了幾千題的過程中，遇過一些人也採用類似的策略，終究也沒辦法從之獲得什麼，那一種糾結始終在我心裡迴盪。有一天，我突然想到自己那種快樂遊玩的感覺沒了，都是在過程中想辦法找到玩下去的理由，開始剝離原先的群組，也不需要什麼理由，我累了，在尋找那簡單快樂的旅途中累了。

接下來的幾周，逐漸地縮短遊戲時間，開始想了當初一些還沒做好的事情，整理一些瑣事，跑了一些實驗驗證算法。在房裡發呆也好，不跟人說話也罷，那一種重新探求的感覺，心想還可以持續多久？

年底的最後幾周，拾起了論文，開著 sci-hub 下載論文來看，嘗試解決當年規劃的藍圖，藍圖都還沒做好，卻發現了工作上更多的問題，甚至還找到了原生 JDK bug，這也解釋了為什麼老是愛開平行解決事情，這都還只是附加產物。印出了一疊論文在公司裡放著，稍微有空閒的時候看。

如果能解決根本問題，不需要研究論文的話，其實也不用這麼痛苦地看論文。若在公司要分享論文知識，或者請求別人一起努力什麼的，這是不太可能的。曾經與同事這麼說道「這個問題很難，總是要有人去犧牲、去解決的，看論文也是這個原因」，得到的回應卻是「那你去犧牲吧」。也許，不經意的一句話才是現實的真相。

生活

沒有。

這些日子研究了一些持久化結構，但我的生活卻不會這麼地持久。

回顧

幾年前，跟 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

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

函數式編程

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

1
2
3
4

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

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

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

離線算法

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

幾何計算

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

• 參考資料 MIT 6.854 Advanced Algorithms - Persistent Data Structures Notes

統計方法

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

字串處理

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

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

版本回溯

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

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

其他

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

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

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

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

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

Invariants

Functional Definition

放眼望去共計 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

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

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

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