老調重彈演算法？這次不一樣，試著物件化它吧！

14 min readJun 25, 2022

為了找工作，練習leetcode是現代工程師不可避免的命運 (大家只能乖乖接受被leetcode f*ck)，因為刷題這種活動能練習到許多演算法與資料結構，此舉能讓工程師的面試更為順利。

但今天不是要談我如何刷題、也不是要談資料結構與演算法，今天要談的議題是在我刷題過程中所產生的疑問：演算法的code只能這麼醜嗎？演算法只能關注資料結構與procedure嗎？身為物件導向信仰者的我難道沒辦法用物件來降低演算法的複雜度嗎？如果沒辦法用物件來降低複雜度的話，是否物件有其應用的極限、亦或者是我目前思維的極限？

因此今天的文章想要探討的議題是：如何將複雜的演算法物件化並降低其複雜度？

由於演算法不是我們關注的重點 (用紅黑樹大家也不會想看)，文中將會使用泡沫排序法 (一個剛開始寫程式一定會碰到的算法)當作範例，最終將其物件化，此文章希望達到幾個目標：

了解為何演算法那麼難懂。
了解為何物件能大幅度降低演算法複雜度。
了解物件版本演算法與原本演算法的差異。

泡沫排序法

以下是泡沫排序的程式碼，相信大家對這段程式碼應該都不陌生，不管你如何實作，大概念都差不多 (忽略掉奇怪的-1, -1-i的話)。

void IAmABubbleSort(List<Integer> numbers) { 
    for (int i = 0; i < numbers.size() - 1; i++) {
        for (int j = 0; j < numbers.size() - 1 - i; j++) {
            if (numbers.get(j) > numbers.get(j + 1)) {
                var temp = numbers.get(j);
                numbers.set(j, numbers.get(j + 1));
                numbers.set(j + 1, temp);
            }
        }
    }
}

當初還是初學者的我，在看到這段code時，腦袋就有一些疑問：為什麼i要小於numbers.size() - 1？、為什麼j要小於numbers.size() - 1 - i？。

要了解上述的問題，我們需要拆解演算法的執行步驟，去觀察outer loop與inner loop執行的次數與pattern。

假設我們輸入[5, 4, 3, 2, 1]，並且預期排序後的結果是[1, 2, 3, 4, 5]。

演算法會這樣執行：

i = 0、size = 5：

j = 0，執行後變成4, 5, 3, 2, 1

j = 1，執行後變成4, 3, 5, 2, 1

j = 2，執行後變成4, 3, 2, 5, 1

j = 3，執行後變成4, 3, 2, 1, 5

j = 4，因為j < size - 1 - i不成立，因此inner loop跳出。

i = 1、size = 5：

j = 0，執行後變成3, 4, 2, 1, 5

j = 1，執行後變成3, 2, 4, 1, 5

j = 2，執行後變成3, 2, 1, 4, 5

j = 3，因為j < size - 1 - i不成立，因此inner loop跳出。

i = 2、size = 5：

j = 0，執行後變成2, 3, 1, 4, 5

j = 1，執行後變成2, 1, 3, 4, 5

j = 2，因為j < size - 1 - i不成立，因此inner loop跳出。

i = 3、size = 5：

j = 0，執行後變成1, 2, 3, 4, 5

j = 1，因為j < size - 1 - i不成立，因此inner loop跳出。

i = 4、size = 5：

因為i < 4不成立，因此outer loop跳出。

我們可以觀察到幾件事情：

numbers.size() - 1：因為有n個泡沫，當n - 1個泡沫都浮到最上面時，最後的泡沫根本不需要浮動，因此numbers.size() - 1 。
numbers.size() - 1 - i：inner loop決定泡沫需要浮動幾次，有n個泡沫要比較扣掉自己因此n - 1，而i變數在inner loop代表已經浮動到最上面的泡沫的數量，假設三個泡沫已經浮動到最上面，其他泡沫就不需要考慮這三個浮動到最上面的泡沫了，因此n - 1 - i。
i變數只用來控制幾個泡沫要往上浮動，每個浮動都從最底部開始。

知道上述概念後，或許我們重構此演算法來降低複雜度…

重構後的泡沫排序法

我們先把難懂的變數換個名稱，重構後的程式如下：

void sort(List<Integer> numbers) {
    int bubbleSizeNeedToFloatUp = numbers.size() - 1;
    for (int i = 0; i < bubbleSizeNeedToFloatUp; i++) {
        int floatedBubbleSize = i;
        for (int j = 0; j < bubbleSizeNeedToFloatUp - floatedBubbleSize; j++) {
            if (numbers.get(j) > numbers.get(j + 1)) {
                var temp = numbers.get(j);
                numbers.set(j, numbers.get(j + 1));
                numbers.set(j + 1, temp);
            }
        }
    }
}

上述可以看到幾件事：

將numbers.size - 1抽象化成bubbleSizeNeedToFloatUp。
將number.size() - 1 - i抽象化成bubbleSizeNeedToFloatUp -floatedBubbleSize。
我們用變數將原先被隱含很深層的概念表達出來。

但同時我們也到了重構的盡頭，就算在刻意拆解其他函數也不會有好效果，從演算法角度，這段程式碼已經很難在優化了。

但光就這樣命名，實際上的複雜度還是存在，命名沒辦法解決根本原因，我們接著下來分析根本原因…

分析問題

我們要解決的問題是泡沫排序法，也就是說：泡沫排序法本身是我們的problem domain，在這個problem domain已經有預期的行為、物件、互動，只是我們還沒找出來而已。

我們先將實作面放在一旁，思考如何用高階的語言來描述泡沫排序法，就跟我們用高階語言來描述應用程式的需求那樣。

泡沫排序法採用泡沫的比喻，在一群泡沫中，每次浮動我們都從最底部的泡沫開始，被挑選的泡沫會慢慢的向上浮動到不能浮動為止，當一群泡沫都浮動完後，我們會得到排序好的泡沫。
那麼被挑選的泡沫如何向上浮動呢？此泡沫會跟上面的泡沫比較，如果比上面的泡沫還要大就往上浮動，反之請上面的泡沫繼續往上浮動。
每i次的浮動，會讓第i大的泡沫浮動到第i大的位置，ex：第一次浮動，第一大的泡沫會浮到最上面、第二次浮動，第二大的泡沫會浮到第二上面，以此類推…

如果您同意這是bubble sort的problem description，那我們會發現一件事：

演算法版本與problem domain的語意落差非常大，一個非常高階、一個非常低階，這樣的差距也稱之為conceptual gap。
由於conceptual gap過大的原因，造成我們難以從演算法回推要解決的問題以及用什麼方式解決，problem domain有泡沫、泡沫集群、泡沫浮動的概念，但演算法只能看到list、swap、nested loop。
針對問題切割時需要刀子，而在演算法中我們的刀子是data structure、data flow、procedure。
這樣的切割方式顯然無法有效降低複雜度，這也是為什麼修改變數的名稱無法降低複雜度的原因，因為僅僅是修改變數名稱還是很難補足conceptual gap的差距，我們需要不同的切割方式與思維。

那麼物件導向能否解決conceptual gap過大的問題呢？讓我們繼續看下去…

物件、責任、互動

物件尋找

換成物件的切割方式如何？讓我們從problem domain找出隱藏的物件開始，藉由上述problem description，我們找出的物件如下：

Bubble (泡沫)
BubbleCollection (泡沫群集)

責任分配

從problem description的描述，我們能發現演算法對於bubble、bubble collection物件的期望行為，如下：

bubble：負擔如何浮動的責任。
bubbleCollection：負擔指揮每個泡沫的責任，確保每個bubble浮動過、負擔bubble查詢的責任、負擔bubble之間交換的責任。

物件互動

客戶端請bubbleCollection排序。
bubbleCollection請所有的bobble向上浮動。
每個bubble接收到訊息，自行決定如何向上浮動。

透過上述分析產生的程式碼如下：

@Test
public void sort_numbers() {
    List<Integer> numbers = Arrays.asList(4, 6, 3, 2, 1);

    var r = new BubbleCollection(numbers);
    r.sort();

    assertEquals(r.values(), Arrays.asList(1, 2, 3, 4, 6));
}public static class BubbleCollection {
    private final List<Bubble> bubbles;

    public BubbleCollection(List<Integer> numbers) {
        bubbles = createBubbles(numbers);
    }

    private List<Bubble> createBubbles(List<Integer> numbers) {
        return numbers
                .stream()
                .map(Bubble::new)
                .collect(Collectors.toList());
    }

    public void sort() {
        floatUpBubbles();
    }

    private void floatUpBubbles() {
        int index = 0;
        while (index < bubbles.size()) {
            bottomBubble().floatUp(this);
            index++;
        }
    }

    private Bubble bottomBubble() {
        return bubbles.get(0);
    }

    Optional<Bubble> nextOf(Bubble bubble) {
        int index = this.bubbles.indexOf(bubble);
        if (index + 1 >= this.bubbles.size()) {
            return Optional.empty();
        }
        return Optional.of(this.bubbles.get(index + 1));
    }

    void swap(Bubble b1, Bubble b2) {
        int b1Index = this.bubbles.indexOf(b1);
        int b2Index = this.bubbles.indexOf(b2);

        this.bubbles.set(b1Index, b2);
        this.bubbles.set(b2Index, b1);
    }

    public List<Integer> values() {
        return this.bubbles
                .stream()
                .map(b -> b.value)
                .collect(Collectors.toList());
    }
}public static class Bubble {
    private final int value;
    Bubble(int value) {
        this.value = value;
    }

    public void floatUp(BubbleCollection bubbleCollection) {
        while (true) {
            var nextBubbleOpt = bubbleCollection.nextOf(this);
            if (nextBubbleOpt.isEmpty()) {
                break;
            }
            var nextBubble = nextBubbleOpt.get();
            if (isLargeThan(nextBubble)) {
                bubbleCollection.swap(this, nextBubble);
            } else {
                nextBubble.floatUp(bubbleCollection);
                break;
            }
        }
    }

    private boolean isLargeThan(Bubble nextBubble) {
        return this.value > nextBubble.value;
    }
}

物件版本的排序法告訴我們幾件事情：

bubbleCollection負責請所有的bubble依序往上浮動。
bubble負責向上浮動的工作，先問問跟鄰兵比大小 (nextOf)，如果比較大繼續浮動，反之接棒給鄰兵繼續浮動。
上述的設計與problem description之間的conceptual gap差異較小，能表達出bubble sort這個problem domain所要解決的問題。

物件思維 vs 程序思維

物件思維與程序思維最大的不同在於如何切割問題：

物件切割的刀為抽象化、行為、責任、物體之間的互動。
程序切割的刀為data、data flow、procedure。

為了降低複雜度，同時也就是降低conceptual gap的差距，我們需要關注問題的物件、期望行為、互動而不是實作細節。

當我們切割的方式越貼近problem domain，複雜度也同時降低，反之則上升，這也是為什麼演算法難懂的原因，因為演算法企圖用錯誤的載體表達複雜的problem domain，抽象程度太低注定沒辦法有效平衡更多的複雜度。

常見的問題

雖然你能認同物件的方式能將problem domain表達得更好，但是否同時你也覺得跟演算法相比好像變得更複雜了呢？這是有點矛盾的觀點，但也是很重要的問題，由這個問題會延伸出下面問題：

一個10行以內、一個80行，演算法就好不行嗎？
看習慣了就覺得演算法比較好懂，物件的方式好複雜。

我們先來回答第一個問題：

首先，程式碼的長短與複雜度沒有關係，決定複雜度的是：problem domain與program之間的conceptual gap。
演算法雖然只有10行，但先前就有提到，演算法企圖用很小的載體來表達複雜的problem domain。
物件版本雖然有80行，但這80行是為了表達bubble sort演算法本身的複雜度，換句話說，也就是essential complexity。
演算法版本沒辦法完整表達problem domain的概念、互動、期望行為，只是把這些概念隱藏，也就是因為這種隱藏，讓我們很難從演算法往回猜其要解決什麼問題。
物件透過80行表達出完整複雜的問題；而演算法企圖將這麼多概念塞在10行內並要求讀者從中發掘出背後要解決的問題、物件透過80行把複雜度紀錄到程式碼來降低讀者腦袋需要記憶的資訊；演算法把複雜度塞在10行，讓讀者負擔從problem domain轉換到實作細節的困難任務。

接下來第二個問題：

會覺得演算法比較好懂的原因在於先前練習bubble sort的過程，我們早已把整塊的程式碼chunking在腦海，因此一看就知道是bubble sort。
程式碼的可讀性判斷雖然很主觀，但還是有些方式能夠驗證：當我們用人類語言描述出要解決的問題後，試著觀察程式碼能否完整的表達這個問題。(此點很重要，因為現實專案可能沒有需求文件，程式碼要能幫我們往回推算解決的問題，而不是如何問題的實作細節，這點演算法表現得很差勁)

心得

如果說複雜的演算法都透過這樣的方式來切割、找物件、互動，是否複雜的演算法能變成跟撰寫application一樣簡單呢？

差別只在

撰寫application我們需要理解現實的problem domain；撰寫演算法我們需要理解computer science的problem domain。
現實的problem domain抽象與實作細節之間的界線很清楚；computer science抽象與實作之間的界線可能較為模糊。
application中的problem domain可能較好學習；computer science中的problem domain較難學習，並且當學習完這些problem domain就變成工程師了XD。

結論

物件與演算法切割的工具不一樣，物件透過抽象化、行為、互動切割；演算法透過data、data flow、procedure切割。
演算法再怎麼重構都沒有多大幫助，因為conceptual gap的複雜才是根本原因，要再進一步降低複雜度，需要完全不同的思維。
物件的表達力較好能降低conceptual gap的距離；演算法沒辦法降低conceptual gap的距離。