#96 分散式系統介紹

分散式系統是我念書過程裡最喜歡的課程之一，也是以前我的研究領域．這一門課通常開設在碩博士班的課程裡，因為這門課需要不少基礎的課程，如果開在大學部的話，也一定是屬於大四選修課的內容．它的先修課程包含了作業系統, 演算法, 資料庫理論, 網路理論，網路程式設計等．它有一個兄弟課程叫分散式演算法．這兩門課蠻接近的，對我而言，分散式系統是比較以工程實作導向來討論分散式系統，而分散式演算法是以數學和演算法更嚴謹的電腦理論來談許多分散式系統裡所需要的運作細節. 我剛好都修過這兩門課，所以都清楚這兩個課程的內容．由於這個部落格的目的是將較不好懂的電腦理論用較白話易懂的方式來介紹給大家，所以在分散式系統的文章裡，不會著重在分散式演算法的內容．這是分散式系統系列文章的第一篇，所以會用一個較宏觀的角度來說明什麼是分散式系統.

在 1980 年代以前，電腦科學的理論已經發展的很快了，但實際上的 "商業化產品" 並還沒有大量地出現．然後在 80 年代開始，個人電腦漸漸地普及，並且 Internet 也開始大量地商業化．因此，從這個年代開始漸漸地有商業的分散式系統出現. 我們先簡單定義一下什麼是分散式系統． 用一個不是很精確的定義，分散式系統是由一群電腦一起互相合作然後達成一個共同目標或任務．舉個例子, email．發電子郵件對現在的你來說是幾乎每天都會做的事情．當你在電腦上打開郵件程式，編寫一封 email，寄給在其他位置的使用者．這封信件會從你的電腦傳送到你對應的 email server，然後再從你對應的 email server 一路展轉到目地端的 email server， 最後收件人打開他的郵件程式再把這封 email 下載到他的電腦上．所以, 整個電子郵件就是一種分散式系統，它需要一堆電腦，這些電腦可以連線用來傳送訊息，進而達成讓人們溝通的目的．分散式系統就是在討論這麼多電腦在彼此互相合作達成某個任務或目的時會遇到的問題以及相關的基礎知識和解決方式.

從這樣的定義你可以了解到現在的時代 (2022) 裡有許許多多的分散式系統．例如，WWW 可說是目前全世界最大的分散式系統. 還有許多 online game 也是分散式系統的一種. 像台灣人常用的 LINE 也是分散式系統的一種. 現在因為處理器能力大增加上軟體工具的進步，所以 AI 的應用可以漸漸地在生活上看見．如果那一天你發現某一個計程車行推出了自動駕駛計程車，不需要司機操作，完全由系統自行決定如何運行，從被客人呼叫，載客，到個計程車之間的行程調派等．這也是分散式系統的一種. 再舉另外一個例子，如果某一個國家或公司發展出先進的飛彈系統，這些飛彈能在發射之後，在空中彼此溝通，彼此協調目標，然後把所有的目標都命中． 不在是傳統的一個飛彈飛到一個固定的點或目標．別懷疑，這也是分散式系統的一種．

從這些例子，我相信你可以強烈地感受到什麼是分散式系統．這門學問基本上就是一種討論如何 "打群架" (多台電腦協同運作)，用一台電腦打不過 (達不成目標)，那只好找一堆電腦來一起打．要叫一台電腦做一件事，這是簡單的，但要叫一堆電腦一起做事來達成一個共同目標，這就顯的複雜許多．這也呼應了一開始所說的，分散式系統的先修科目有作業系統, 演算法, 資料庫，網路等等. 

因此，你可以知道，分散式系統是一堆電腦透過網路連線能彼此溝通進而達成一個任務．電腦不局限是電腦，也可以看成是某一個電腦程式．網路不局限於有線或無線，也不局限於區域網路或廣域網路．概念上，分散式系統的定義是可以很廣泛的．不同的任務所需要底層知識會有差別．例如，email 是一種分散式系統，不論你是用那一種電腦系統，不論你的 email 程式是用什麼語言寫的，也不論你的 email server 在世界上的什麼地方，這些都不應該是障礙．所以，為了讓某一個分散式系統能夠商業化地運行下去，必須定義許多 "標準" 好讓不同的軟體廠商可以依這些標準來產生可行的工具，這樣這個分散式系統才能成功．所以，不同分散式系統的應用就能看到不同的標準．例如, email 系統要定義出 email address 的合法格式，要定義出 email 內容的合法規格，要定義出 server 和 server 之間的溝通方式和通訊協定等，也要定義 server 和 mail client 之間的溝通方式等．從 email 系統的例子，你可以看到光是網路通信就有很多標準要完成．有許多的分散式系統不見得需要走向標準化．因為一些商業考量，有些公司喜歡有自己的應用，例如早期的 ICQ, MSN messenger, 到現在的 LINE．這類似的分散式系統是相對較封閉的分散式系統，因為是由某一家公司自己主導與開發，所以每家公司所使用的 "標準" 就不見得是一致的，各家都可能不一樣.

希望這一篇短文能幫助你了解什麼是分散式系統，下一篇文章，我們將介紹分散式系統裡會面臨到的挑戰，而整個系列文章將會圍繞在這些挑戰來介紹相關的解決方案.

閱讀全文

#95 Priority Queue 是不是 Queue ?

 在日常生活的情況中，排隊是一件很常見的事．原因是提供資源的人少，而使用資源的人多．例如，一堆人到便利商站買東西，買完後要結帳，而櫃檯人員只有一個，所以結帳得一個一個來，因此買商品的人就得排隊．在此時，如果出現一個文化水準低落的人來插隊，想必你一定會很生氣去跟對方說．在便利商店的排隊結帳來說，插隊通常不是件好事，但日常生活裡，某些特殊情況下，插隊是需要的，比如在醫院的急診室，或是馬路上遇到救護車救火車之類的，這種特殊情況，不緊急的必須先讓給緊急的．

當我們撰寫程式碼時，一般情況下我們會使用 Queue 資料結構來達成 "排隊" 的目的，然後，因應需求，如同急診室或救護車的例子，我們必須提供一個方法讓 "插隊" 可以成真．試著想一下，如果我們要用 Queue 結構的概念來達成插隊這件事，該怎麼做呢 ? 

假設我們用 Linked list 來實現 Queue 結構,

 

source: https://en.wikipedia.org/wiki/Linked_list

上面的 List 一共有三個元素，當實做 Enqueue() 時，我們可以把最新的元素加到最後面，這個動作的時間複雜度是 O(n)，n 是元素數量，當實做 Dequeue() 時，我們把前最面的元素讀取出來，然後第二個元素將變成第一個元素，時間複雜度是 O(1)．當我們要實做 "插隊" 時，我們該怎麼插隊呢 ? 首先，我們需要了解如何定義優先順序．以 List 而言，它的 index 位置就是優先順序 (Priority)，因為排在越前面會越先被 dequeue．假設我希望有一個元素能插隊在第二個位置，這表示我們得走到第二個元素，然後做插入的動作．這樣子有一個小缺點，我們必須知道每個元素的優先順序才能正確給出位置．如果我們必須先知道優先順序，這表示我們需要了解每一個元素的內容，這樣才能幫助你決定正確插入的位置是什麼．這顯然有點缺點，因為我們還得寫更多的程式碼來記錄每一個元素的意義，然後來決定該元素是重要還是不重要．

另外一個方法，我們可以將元素的內容改成兩個東西，一個是元素值和另一個是優先順序值．

上面的數字代表優先順序值，下面的數字是原來的元素值．當我們需要 Enqueue() 時，優先順序值就必須先指定．執行時間一久之後，你就會發現這方法也是有問題，因為若我們要將新元素指定到最後面，優先順序值就必須不斷新增，總有一天，這個數字將會超過 integer 的範圍．因此，用這個方法並不好，原因就在於我們必須指定優先順序值．如果我們不要指定優先順序值，同時有這樣的效果，那豈不是更好嗎 ? 此時，你就該了解到用  Queue 結構來實做並不是個好方法．

在資料結構的世界裡，有那一個結構能做到 Queue 的行為並且能定義優先順序的能力呢 ? 有的，它的名字叫 Heap，其範例如下圖所示:

source: https://en.wikipedia.org/wiki/Heap_(data_structure)

Heap 是一種特別的 Tree結構，它有一個很重要的特性，任何一個節點的值都必須大於等於或小於等於該節點以下所有的節點值．以上圖為例，這是一個大於等於的例子，意思就是每一個節點值都會比在它之下所有的節點值還要大或一樣．我們稱它為 max heap，若是小於等於，稱為 min heap．

節點值就是優先順序，只要我們能將需求面的優先順序定義清楚，就能把每一個工作 (節點) 建立 (Enqueue)  max heap，而建立的時間複雜度是 O(lg n)，其中 n 是所有節點的數量，這樣效能就比前面說的 Linked list 要來的好．取資料時 (Dequeue)，就直接將 root 取出，因為當下 root 是最大值的節點，然後再從 root 的子節點中挑出一個較大的節點做為新的 root 即可，以上圖例子而言將是 36，取出的時間複雜度是 O(1)．

使用 max/min heap 來做為具有優先順序功能的 Queue，就稱它為 Priority queue．在主要的程式語言裡 C++/Java 等的 library 都有實作 priority queue，所以讓大家可以直接用，方便許多．所以，當你需要一個有插隊功能的 queue 時，別忘了 priority queue．

閱讀全文

#94 演算法的 Backtracking 策略

 Backtracking 是一種演算法的策略，可用來解決三種面向的問題，分別是 Decision problem, Optimization problem, 以及 Enumeration problem．有關 Optimization problem 在前面的文章裡已經談過不少，這裡不多說明．一個 Decision problem 可能會有至少一個或一個以上的解答，這種問題我們通常只要找一個可用的解答．Enumeration problem 和 Optimization problem 蠻相近，就是要將所有解答找出來．舉個例子，之前講過的老鼠走迷宮是一種問題，如果我們要找一條可行的路，那麼老鼠走迷宮將是 Decision problem．如果我們要找出一條最短的路，此時便是 Optimization problem．如果要將所有可行的路找出來，這便是 Enumeration problem．不同的問題需要不同的解決策略．Backtracking 就這麼巧地可以用來做為這三種問題的解決策略．

以西洋棋裡 n-Queen 問題來說明，一般以 n = 8 為市面上較為熱門的題目，現在我們把 input size 縮小一點，將 n=4. 而棋盤和其中一個可行的解答如下:

Source: https://www.geeksforgeeks.org/backtracking-introduction/

n-Queen 問題的解決策略如果用最直覺的暴力法來做，其解法如下

1. 列出所有 Queen 的排列座標，例如

    Answer candidate 1: (0,0) (0,1) (0,2) (0,3)

    Answer candidate 2: (0,0) (0,1) (0,2) (1,3)

    Answer candidate 3: (0,0) (0,1) (0,2) (2,3)

    Answer candidate 4: (0,0) (0,1) (0,2) (3,3)

    Answer candidate 5: (0,0) (0,1) (1,2) (0,3)

    .... 以此類推， 一共有 4x4x4x4 = 256 種位置．

2. 然後將每一個候選答案放到一個檢查器．這個檢查器就是題目要求的，要讓每個皇后所在的位置不會影響到其他的皇后．這個檢查器要執行的程式碼就是問題本身所給出的限制．你我都知道，暴力法簡單粗暴，保證一定讓你能找到答案，但不保證能快速找到答案．這個問題的 "限制" 本身就是一個有點複雜的運算了．如果你忘了西洋棋的皇后走法，你需要複習一下才能知道這裡所說有點複雜運算的意思了．

如果是用 Backtracking 的策略，該怎麼做呢 ?

Backtracking 的策略在我看來和暴力法是有一點接近的．只是差別在於 Backtracking 不會一開始將所有可能列出來，然後再進行對每個輸入一一地檢查．Backtracking 的策略是在產生所有可能的排序方式過程中，就直接檢查了．如果在過程中不符合 "限制" 時，則中斷這條路，然後跳到下一組排列來做.

以上述的答案候選為例子:

一開始，第一個皇后放在 (0,0)，然後試著將第二個皇后放在 (0,1)，執行檢查器，這樣檢查器會回傳 false，因為棋盤上同一行只能有一個皇后．於是，後面答案候選裡面只要是 (0,0) (0,1) 開頭的組合便可跳過．前面兩個皇后的位置已經不合法了，所以後面的皇后也不用浪費時間檢查．若以程式的角度來看，某一層次的 for loop 將可以整個跳過去而不執行．所以，下一個要檢查的便是從 (0,0) (1,1) 開頭的答案. 

以上的過程的解題思考就是 Backtracking．

看到這裡，雖然我們沒有寫出細節的程式碼，但我相信你能感受到 Backtracking 的解題策略的精神是什麼了．Backtracking 適合用在需要 recursion 來解決的問題．在我們試著將所有的可能答案窮舉出來的過程中，就執行著 "檢查器"，一旦發現檢查器不通過，就直接跳開這一個層次的答案，直接轉往下一個層次，這就是 Backtracking 能夠省出時間的方式．上述的 n-Queen 是一個常見的例子，Sudoku 也是一個常見的例子. 我相信在你的工作中 Backtracking 能派上用場的時機點是很多的．

底下的程式碼是我小徒弟在數個月前練習解決 Sudoku 題目的程式碼，其解決策略是 Backtracking.

閱讀全文

#93 平衡樹系列 - AVL Tree

在前面的資料庫文章裡曾介紹過 B-tree，一種平衡的搜尋樹，利用樹狀的結構來達成快速尋找的目的，而且因為是平衡的，所以從 root 出發到每一個樹葉的尋找成本是一樣的，這也是必要的，畢竟資料庫引擎用公平的方式來對待所有的資料．然而，B-tree 的結構並非是 binary 的型式，因此這帶給它很大的彈性可以方便地達成一個完全平衡的狀態．在前幾篇的文章也談過了 binary search tree，若你看過的話，你會清楚地知道 binary search tree 和 binary tree 的不同．在 binary search tree 裡，因為在建立樹的過程中有一個很重要的特性，就是右邊子節點的值大於父節點，左邊子節點的值小於父節點，因此在建立樹或是尋找節點時，到達一個節點時，只需要選擇其中一邊，不是左邊就是右邊，所以也達到 "binary search" 的效果．如前面的文章所說，binary search tree 的特性並不保證樹結構本身是平衡的，所謂的平衡就是其結構會和 complete binary tree 很接近．因為 binary search tree 沒有這樣的特性，因此樹的結構很可能是 "歪" 的．

為了要防止這種 "歪" 的情況，在早期的電腦科學研究裡便出現了許多的點子和做法，其中一個稱為 AVL Tree．這是兩位前蘇聯時代的科學家所發明的方法．發明的時間都是在我們出生之前 (我猜想這部落格的讀者群應該沒人超過 60 歲)．首先，先把 AVL tree 的時間複雜度列出來．

Search: O(log n), Insert: O(log n), Delete: O(log n)，不論是 average case 或是 worst case 都是一樣的時間複雜度，超級完美的．這也是為什麼在上一篇章的 APCS 考題會拿像 binary search tree 的實做來用，因為就是這麼快．不論是刪除或插入，甚至尋找都是 O(log n)，為什麼可以這麼快呢? 接下來將來說重點了.

AVL Tree 是一種 binary search tree 的特例，所謂的特例是指 binary search tree 再加上一些其他的特性之後就能變成 AVL tree．而這一個特性稱為 balance factor．每一個節點上都會有一個 balance factor，它代表的是一個值，其值是右邊子樹的高度減掉左邊子樹的高度．例如:

source: Wikipedia

節點 F ，右邊高度為 1，左邊高度為 2，所以 F 節點的 balance factor 為 1 -2 = -1，其他的節點也是用同樣的公式而得．AVL tree 定義了每個節點的 balance factor 必須為 -1 , 0 或 1．透過 balance factor 的限制，我們能知道這一個樹就 "比較" 不會那麼歪掉了，因為右邊子樹和左邊子樹的高度最多只能相差 1 而己．為了確保這個特性能發生，在插入節點或刪除節點的過程裡便需要採取一些動作．而這些動作如下:

1. 往左轉

source: www.tutorialspoint.com

如上圖，節點 A 的 balance factor 是 2，因此必須降低它，由於這是 binary search tree，所以 C 的值大於 B，而 B 的值又大於 A，因此，要把樹技折下來的話，拿中間者來當新的父節點最好，於是以 B 為中心將 A 往左轉，所以就變成了最右邊的圖，這樣就符合了 AVL tree 的特性．

2. 往右轉

source: www.tutorialspoint.com

往右轉的情況剛好是和第一種相似，只是換另一邊而己.

3. 往左再右

source: www.tutorialspoint.com

第三種情況其實是前面兩種情況的綜合體．若你看懂前面兩個為何要那樣轉的話，我相信你也一定看的懂第三種．其主要目的就是要讓 AVL tree 的特性可以滿足．

最後第四種，可想而知就是往右再往左.

4. 往右再往左

source: www.tutorialspoint.com

第四種情況就是第三種的另外一邊．只要你懂第三種情況，那麼第四種情況自然也不會是問題．

你可能會問我，像這種 AVL tree 要應用在什麼地方．老實說，到處都是，許多程式語言在他們的 standard libary/SDK 裡都會提供這種平衡的 binary search tree．我在工作上時常會用到這類型的資料結構以快速建立資料和尋找資料．前一篇 APCS 的解題就是靠類似 AVL tree 這種的平衡樹才能將時間複雜度降到 O(n log n)．別以為 O(n²) 和 O(n log n) 相差不多，一旦輸入的數量到達數以萬計時，你的家用 CPU 就會告訴你他們之間有很大的差距了．

在 Wikipedia 上你也可以找到一個動態的圖來說明 AVL tree 在建立的過程中，這些節點是如何左轉或右轉來達成平衡．AVL tree 將達成平衡這件事分攤在節點插入和刪除的過程中，因為才使得插入節點，刪除節點和尋找節點都有相同的時間複雜度．這的確是很高明的做法，我們大家又再一次站在巨人的肩膀上來看見電腦科學的神奇之處．

閱讀全文

#92 今年一月份 APCS 程式設計第三題 - 切割費用

前陣子，我的小徒弟去報名他人生第一次的 APCS 考試，可以說是他學習電腦科學以來第一次的正式上機考試．一共有四題的程式設計題目，前面兩題算是簡單的，第三題算中等，第四題比第三題再進階一點點．這篇文章就來談談第三題的解題思考．

完整的題目在 https://zerojudge.tw/ShowProblem?problemid=f607 ，首先，要解題之前，請先確定自已己經百分百了解題目．這一個題目的解決過程可以分成下列 2 個部份,

1. 讀取輸入參數，因為輸入參數並非按照切割次序而輸入的，我們要進行切割時是按照次序來切割的．因此，我們必須對輸入參數做處理，以讓沒有次序的參數集合變成有次序的參數集合．

2. 每一次切割時，都需要知道左右兩端的長度，這樣才能算出該次切割的費用，而知道左右兩端的長度，這需要一個快速的行為才能符合題目的要求．因為題目提到切割次數最多會到二十萬次，並且棍子的長度可以到 10 ⁷ 那麼長.

有關讀取輸入參數的內容，基本上有兩種做法，可以把切割資料全部讀進來之後，再以切割次序做排序．若是這樣做，這個動作將花費 O (n lg n)  ，假設是用 quick sort. 除此以外，我們可以換個角度思考，題目給的切割次序不會出錯，也就是說當切割資料讀進來時，切割次序就是一種 key，不會重覆，因為第 n 次切割只會發生一次．所以可以用 (key, value) 的 hash table 來存放切割資料．由於 hash table 的 set , get 都是 O(1) ，所以這讀取動作將花費 O(n)．

因此，第一個部份的時間複雜度最小可以到 O(n).

接下來，第二部份是計算每一次切割的費用．可以想像正在發生第 k 次的切割，也就是我們要想一個快速的方法讓我們可以查到在第 k 次切割時，當時所在的位置往左邊和往右邊走碰到的第一個切割點. 假設一開始用一個 boolean array 來代表被切割的點，

index :  0    1    2    3    4    5  ......98   99  100    101    102    103  ........ n

value:   f     f     f     f    f     t  .....  t     f       f        f        t         f      .......  f

一開始 array 的都是 false ，被切割過的點就變成 true，假設第 k 次的點要切割在第 100 個位置，而 98 和 102 是 true，所以這一次的切割費用是 102 - 98 = 4．如果以程式的角度來看的話，你得寫一個 for loop 從 100 往右邊走，找到第一個 true ，然後再往左邊走找到第一個 true，然後再做減法．這樣的尋找方式是 O(n)，而這個會發生在切割資料的迴圈裡，假設切割資料是 m 筆，因此這一段的時間複雜度是 O(nm)，一旦 n 和 m 都很大時，這就相當於是 O(n*n)．而 n 最大的值會到 20 萬，因此 O(n*n) 是不能接受的．因此，用 array 做搜尋是不合格的，所以我們必須用其他的資料結構，並且這個資料結構所花費的成本要小於 O(n) (比 array 一個一個找再快).

這時候，答案其實已很明顯了，能夠比 array O(n) 還要快的只有 binary search tree O(lg n) 或是 hash table O(1) ．在這一個動作的過程中，我們需要能 "往左走" 和 "往右走" ，Hash table  顯然不會是個好選擇，因為 hash table 無法儲存元素之間的 "順序"，因此，就剩下 binary search tree 了．binary search tree 在儲存的過程花費 O(lg n) 時間，而尋找的過程也是花費 O(lg n) 時間，而且 binary search tree 的特性讓我們可以 "往左走" "往右走" 來找到最近被切割過的位置．因此，採用 binary search tree 之後，時間複雜度可變成 O (m lg n) ，如果 m 和 n 都很大時，就是 O( n lg n)，這個比剛剛的 O(n*n) 快上很多.

最後，以下的程式碼是我的小學徒提供的，在很大的測試資料下仍花費了 0.25 秒完成，雖然不是最快，但也符合了題目 2 秒內的要求.

閱讀全文

#91 如何寫有影響力的履歷表

根據 Facebook 社團上的成員資料，目前三百多位成員裡有將近 40% 成員的年紀在 34 歲以下，因此，希望這篇文章可以提供年輕人有關撰寫履歷表內容時的參考.

一般來說，我會把履歷表的寫法分成兩種，一種是屬於年輕工程師的寫法，另一種是資深工程師的寫法，我將年資不到十年的人定義為年輕工程師，所以可能是在 32 - 36 歲之間，就看你在幾歲從學校畢業．在這年資以下的人，撰寫履歷表時應該要著重在技能的部份．也就是說，你得在履歷表上說明你用過了那些工具與方法來製造軟體系統，以及你運用了那些專業知識 (課本上學的) 在你的工作上．比如，某個年輕工程師從事電商系統前端功能的開發，屣歷表上就需要清楚說明用 Javascript/TypeScript 寫了什麼東西，是否用到其他的 framework，如 Angular 等等，並且做過那些功能，如購物車系統，付款流程，購物體驗等等．把這些東西寫清楚來，讓看履歷表的人明確知道你過去曾用過的工具以及熟悉的產業環境是什麼，這樣能幫助雇主加快認識你的速度．

為什麼年輕工程師要寫這樣的內容呢 ? 因為年輕工程師通常被給予的任務是小而明確的，如解 bug 或做一些小功能．履歷表上寫一些技能類的事情可以幫助未來的雇主知道你過去做過些什麼，也能幫助雇主評估是否要找你來進行面試．

如果 32 - 36 歲以上的工程師 (超過十年的業界經驗)，理論上來說，在業界工作了十年應該要達到資深工程師的水準了．我猜想在台灣的公司對於職稱上的給定標準並沒有一致且較寬鬆，所以中小企業或是非資訊科技領域的公司做了三五年後就能得到資深工程師的職稱．在規模大且制度嚴謹的公司裡，要在三到五年內拼到資深工程師是件不容易的事情，資深工程師的履歷表就應該著重於有關 "影嚮力" 的事情，比如，製造一個付款交易系統，讓整個網站可以在一分鐘之內完成 n 筆交易，使得網站可以承受 m 個使用者的流量．再舉另一個例子，重新製造了購物車系統，讓原本客戶評價極差的用戶體驗變成零負評的新體驗，並且讓網站提升 n % 客戶滿意度．再舉另一個例子，製造了一套基礎建設程式庫用於處理公司內所有系統的溝通機制，將原本平均一分鐘執行時間的動作提升至十秒鐘完成．或是一個更利害的例子，製做了一個很利害的 open source software，放在 Github 上得到了 n 顆星星，造福了世界上許多的軟體工程師．透過這些簡單例子，我相信你一定明白我所謂的 "影響力" 是什麼意思了.

回過頭來，並不是說年輕工程師就不用寫影響力．對於年輕工程師而言，如果你可以寫出令人信服的影響力，一定要寫下來，因為那些都是能讓你換到新公司時談職位與薪水的利器．

不論你寫的是技能比較多或是影響力比較多，千萬要記得別亂寫或是誇大地寫．若有機會面試時，這些技能和影響力是很容易被檢查出來的，一旦面試官發現你在 "唬爛" 時，你有可能永遠不會出現在這公司的面試名單裡．

履歷表內容的基本上包含了你的個人基本資料，工作經歷，學歷，技能以及一些參考資料．以我的經驗來說，我會將影響力放在工作經歷的內容裡，所以每一個工作都會是一段描述，而不是一行文字只包含公司名稱，職位名稱和時間而己．通常來說，一到兩頁的履歷表就應該要把你自己說明清楚，過長的內容，雇主很容易跳過不看，因為有名的公司每天都會收到很多履歷資料，沒有人會把細節看完．同時也要告訴一些年輕的工程師，工作要慎選，常常換工作並不是一件好事情，技能的程度高低也許不會受到換工作的影響，但我相信影響力是需要時間累積的，若常常換工作，則很難說明與說服其他人你在短時間裡能在一家公司做出有影響力的事情! 所以，找新公司時要好好想清楚，工作經歷就像是學歷一樣無法抹去也無法作假的，因此，在換公司時也要好好想想你該如何在新公司做出影響力的事情．同時這個題目也可能當成你和你老闆一對一面談時間裡的內容．

Hope it helps,

閱讀全文

#90 淺談 Dynamic Programming (2)

 前面說過 dynamic programming 的應用很多，這一篇文章來說明其中一種應用，Maximun subarray sum．這個問題是在一個整數的 array 裡找一個連續空間的元素，其元素的總和的值是最大的．如下圖:

source: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

從 index 2 到 index 6 之間的元素總和等於 7，這個區間是這個 array 裡最大的區間總和. 要解決這個問題其實不難，因為用最直接的暴力法就可以解決了，其程式結構如下:

這一個暴力法的時間複雜度是 O(n*n*n) ，n 是 array 的長度. 如果 n 很小，影嚮不大，但若 n 很大，這一個運算雖然在空間複雜度很表現的很好，但浪費許多 CPU 的運算資源，因為許多加法的計算是重覆了. 將這個問題的時間複雜度降低的方法不只一種，在這篇文章裡，我們用 dynamic programming 的策略來試著降低時間複雜度．如前一篇文章提過的內容，dynamic programming 的策略在於用空間換取時間，所以我們必須找出在什麼地方可以減少重覆的計算．要減少重覆計算之前，我們可以先從暴力法來看到底真正的計算是花在什麼地方了. 從上述的程式碼，你可以看到決定 subarray 的總和值是從最裡面的迴圈來運算的，所以第一圈會計算 start = 0 , end = 0 的總和值，第二圈會計算 start = 0, end = 1 的總和值, 第三圈會計算 start = 0, end = 2 的總和值，以此類推下去．透過觀察，你便能發現第二圈要計算的內容在第一圈已經算過了部份答案，第三圈要計算的內容在第二圈已經算過了部份的答案，因此，最裡面的迴圈其實是重覆了做了許多相加.

Loop 1: -2 

Loop 2: -2 + -3 = -5  (Loop 1 + -3)

Loop 3: -2 + -3 + 4 = -1 (Loop 2 + 4)

Loop 4: -2 + -3 + 4 + -1 = -2 (Loop 3 -1)

因此，透過以上的運算呈現，便能知道最後一個迴圈是可以去除的．我們只要將上一圈計算後的內容先暫存起來，留到下一圈時便能拿出來用，直接做一次加法就可以得到這一圈的答案了．因此，那個查表法的 "表" 也只不是一個臨時的變數，在空間複雜度上並沒有增加，而時間複雜度卻降了一階變成了 O(n*n)，如下列的程式碼.

接著，或許你還會問，空間複雜度還仍再降嗎 ? 剛好這一個題目是可以的，它的名字是 Kadane's algorithm，這個演算法在許多讀者還沒出生之前就已經發明了，這演算法能用 O(n) 的時間複雜度解決這問題，而發明人是一位教授，現在已經非常高齡了. 若你晚些才看到這篇文章, Kadane 教授也許不在人世了，我們大家都是站在巨人的肩膀上.

最後，你可能會問這個演算法我們該用在那裡．這完全取決於你是否會遇到類似的題目．如果你遇到一個問題，而這問題剛好可以 Reduce 成 maximum subarray sum 時，Kadane's algorithm 便能幫助你寫一個超快速的程式來解決問題，例如，你老闆要你找出過去十年裡，那幾個連續的月份其營業額是最好的．

Dynamic programming 的策略確實應用在許多地方，未來介紹更多的主題時，一定都還會碰到 dynamic programming 策略所產生的解法.

閱讀全文

#89 淺談 Dynamic Programing (1)

Dynamic programming 是大學部演算法課程裡相當重要的一個主題，也是典型用空間換取時間的策略．但奇怪的是，這個策略一點也不 dynamic ，一點也不 programming．老實說，我不知道為何這個策略叫 dynamic prograaming，我倒覺得它比較適合叫 "查表法". 接著就來看看為何說它是查表法.

Fibonacci number 是許多演算法課本用來解釋 dynamic programming 最簡單的例子．Fibonacci number 是以數學多項式來表達的數字集合，以數學式來表達就可以寫成如下:

F(n) = F(n-1) + F(n-2) 

也就是說求第 10 項 (n=10) 的答案時，你必須要先算出來第 9 項和第 8 項. 如果要求第 1 項呢 ? 難道要找出第 0 項和第 -1 項嗎 ? 在 Fibonacci number 上，我們會為這個 number 定義起始點，也就是說第 1 項和第 2 項的值是早被確定的，往後的項次皆由這兩項為基礎而算出來，所以不會有第 -1 項的情況. 假設, F(0) = 0, F(1) = 1 ，那麼數列的答案如下:

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3 

F(5) = F(4) + F(3) = 3 + 2 = 5 

F(6) = F(5) + F(4) = 5 + 3 = 8  以此類推

當你要算第 n 項時，就按以上的方法一直算到第 n 項就能得到答案. 接著，數學公式 F(n) = F(n-1) + F(n-2) 寫出來了，那麼寫程式碼就變得相當簡單.

透過一個 recursive function 就能快速完成  Fibonacci number 第 n 項的計算程式．這一個程式碼沒有使用額外的記憶體空間，所以 space complexity 是 O(1)，但仔細看一下 time complexity，卻發現超乎想像的大，因為有許多重覆的步驟:

            F(5)  
          /     \
       F(4)      F(3)
      /    \    /    \
   F(3)   F(2) F(2)  F(1)
   /  \
 F(2) F(1)

上圖是整個 recursive 的關係. 意思就是，當程式在 F(5) 那一個層次要往下呼叫時，程式會呼叫自己兩次，並傳送 4 和 3 為輸入參數，當第一個 recursive call 再進去時，又會再呼叫自己，並傳入 3 和 2 為輸入參數，以此類推．所以你可以看的出來，有許多重覆的計算在這 recursive 的過程中一直發生．以上圖來說，F(3) 發生了 2 次，F(2) 發生了 3 次．當 n 是一個大的數字時，你就可以發現比 n 越小的數字，重覆計算的次數越多，並且是以指數趨勢來增加．上述的程式碼雖然很簡單，但是 time complexity 卻是很可怕的．上述的程式碼是由上而下計算下來的，假設我們繼續用由上而下的計算方式，改良此程式碼的方法就是將 "重覆" 的計算步驟讓它不要重覆計算．如上圖，如果 F(3) 只真正地被計算了一次，而 F(2) 只真正地被計算了一次，那麼就不會有重覆計算的事情了．為了達成這目標，最簡單的方法便是把計算後的結果儲存下來，等到要計算一樣的內容時，去 "查表" 即可．也就是說第一次 F(3) 計算的結果儲存下來，當程式遇到第二次的 F(3) 時，直接去查詢，若有答案，直接將答案拿來使用，這樣就不用計算了．同時，為了確保不會造成過多的 time complexity，我們也需要確認答案的儲存和查詢所花費的 time complexity 要非常小，如 O(1)．這種 "查表" 的精神也是 dynamic programming 所代表的策略．

若將上述的程式碼加入 "查表" 的功能，它將看起來如下:

或是直接改成由下往上計算

以上兩個程式碼雖然結構有點不太一樣，但都是用了一個 array 來記錄每一個項次計算的答案，因此 time complexity 省下來了，而且 space complexity 也增加了，但這樣的空間增加似乎是值得的．當然也可以再把上述的程式碼繼續改下去讓 space complexity 變的更小，不過這並不是這篇文章的重點．透過以上的簡單例子讓大家方便了解 dynamic programming 的 "查表" 意義是什麼．許多世界上有名的演算法都是基於 dynamic programming 的精神所發展出來的，例如你幾乎每天都在用的字串比對演算法就是基於 dynamic programming 所發明出來．

這篇文章用 Fibonacci number 的例子來說明 dynamic programming 的精神，這是相當簡單的例子，下篇文章我們用較難的例子來說明 dynamic programming 的用法.

閱讀全文

#88 資訊工程系的大學先修考試 APCS

在美國加拿大的大學入學測試中心成立了一種測驗，名為 Advanced Placement，裡面分成多個不同的專業考試，主要用來測驗高中生在該專業領域的 "程度" 如何．這些專業領域如生物，歷史，物理，語言，統計等等，其中電腦科學也是其中一個專業領域．簡單地說，就是要測驗那些資優班的高中學生，當他們申請大學時，可以附上 Advanced Placement 的成績用來代表他們有多少的能力在這些專業領域裡．詳情可參考 https://en.wikipedia.org/wiki/Advanced_Placement

在數年前，台灣教育部也發動了一樣的計畫，其中電腦科學的專業是由台師大資工系來執行，詳情可參考 https://apcs.csie.ntnu.edu.tw/

到今年 2020 為止，大部份在台灣有比較好的資工系學校都會參考這個成績，並且設下了門檻，例如台大資工要求觀念題和實作題都要達到 4 級分以上．這個考試結果一共分為五級，依照學生答案的內容來分級．若要達成 4 級分的話，基本上要熟練一個程式語言，如 C++，並且會用基本的資料結構，如 Array, List 等，除此之外，還要知道如何寫 recursive code 來解決問題，例如 binary search 等．對於正在讀文章的你，可能已經工作多年，這些並不是什麼難事，但對一個高中生，除了要面對高中的課程，還要花時間學習這些 "課外讀物"，這的確不是件容易的事. 在師大的 APCS 網站裡，提供了歷史考題．我會在這網站裡貼出參考答案. 如果你是打算以後念資工系的高中生，或是你們家有這樣的高中生，歡迎你分享給他們.

程式實作題: 三角形辦別

日期: 2016/10/29

參考答案

程式實作題: 矩陣轉換

日期: 2016/3/5

參考答案

以上的答案是 C++ 搭配 STL，答案並不是我寫的，是我一位小徒弟寫的答案，他在二個月前剛升上高一，以他目前的能力要應付台灣 APCS 題目算輕鬆．我這位小徒弟是個小學霸，以後再來介紹我是如何訓練他電腦科學的知識.

以上兩題對於已經在工作的你來說應該都是很簡單的題目，只是一些基本的數學應用題．台灣 APCS 的歷史題目還有好多題，未來文章會介紹.

閱讀全文

#87 Binary Search Tree 簡介

在 "資料結構" 系列文章裡寫過了 Binary search ，也寫過了 Tree．Binary search 能幫助我們在一個 "排序" 好的資料序列做快速的資料尋找．Tree 提供我們一個資料儲存 (放置) 的結構，當這兩個碰在一起時，產生了一個相當有用的資料結構.

Binary Search Tree 的發明比起我和絕大部份的讀者的都還要來的老，它出現在 1960 年代，在那個電腦硬體仍不太發達的年代，這個超級有用的資料結構就被發明出來了．誠如之前談的 binary search 內容，當你要進行 binary search 時，有一個很重要的前提就是被尋找的資料需要以某種排序好的順序存在，不論是從小排到大，從大排到小，或是從中排到小，再排中排到大，只要是資料依照某種屬性而排序好，就可以進行 binary search. 它的尋找資料的時間複雜度也在前面文章提過了，是 O (log N) 的複雜度，因為每一次尋找都可以捨棄掉一半非尋找目標的資料，這對尋找是個很大的幫助．然後，別忘了剛剛說的前題，資料必需是以某種方式排序好的．若你要在一堆沒有排序好的資料，把它排序，再執行 binary search 來找資料的話，這顯然有點過頭了，因為光是較快的排序都要花費 O(nlogn) 時間．因此在使用 binary search 之前，資料已是排序好的方式存在則能馬上使用 binary search，

當要讓資料以某種排序的方式建立起來時，可想而知，在建立的過程中可能要花費較多的時間，畢竟這不是隨便把資料加上去就好，而是要找到一個適當的位置才能加上去，以維持排序的狀態．你可以想像一個 integer single link list ，當你要加資料進去時，你得找到適當的位置並執行 insert 的動作，如下圖所示:

因此，只要我們能找一個適合的資料結構將資料依排序的目標建立起來，binary search 就可以派上用場. 在 Tree 的應用裡面，有個基本的結構叫 binary tree，也就是每個樹節點除了資料本身的空間外，還有另外兩個空間，一個是指向左邊節點的空間，另一個是指向右邊節點的空間. Binary tree 本身並不涉及任何資料排序的概念，但若我們為它加上一個限制，資料大的往右邊節點方向去建立，而資料小的往左邊節點方向建立，那麼這個 binary tree 便存在了排序的特性，如下圖所示，在任一個樹節點上，若左邊存在一個節點，則左邊節點的值將比較小，同理，右邊節點的值將比較大.

當 binary tree 加上了 "順序" 的特性時，這時就稱它為 binary search tree. 當尋找資料的動作發生時，從 root 開始出發，假設我們在上圖的 binary tree 上找 44，我們會在 root node 往右邊走，因為 44 > 11．以此類推，只要經過兩個樹楖點，我們便能找到 44. 如前面所說，這個動作的時間複雜度是 O(logn). 在大部份的應用裡，這個速度已經夠快了．

此時，你可能會發現在 binary search tree 要找資料時, root 的值是很重要的，因為你可能會看到如下圖的情況,

如上圖，倘若我們選到了一個不適合的值來當 root 時，此時 binary search tree 就長 "歪" 了．所謂的歪並不是壞掉的意思，而是大量傾向某一邊造成不平衡的情況．所謂的不平衡的意思就是某一樹節點左邊的 subtree 和右邊的 subtree 在高度上有大的落差．這會造成搜尋成本的不平均．比如，若你要找 44，它剛好是 root，所以一下子就找到了，若你要找 7，中間要經過 44 -> 33 -> 11 -> 6 ，最後到 7，若是你要找 11，中間經過 44 -> 33 就到 11. 所以，每個節點被找到的成本存在的大差異，因為我們稱之為不平衡的樹．這是我們希望能避免的情況，畢竟你希望的是每一個資料在被尋找時，每個資料被找到的時間成本和平均成本是很接近的，這樣才是公平．倘若資料本身需要不公平的情況，那就另當別論了.

Binary search tree 幫助我們將資料能用某一種順序的方式儲存起來，並且在尋找時也能達成 binary search 的效果．有些程式語言的程式庫裡都會提到這一個好用的資料結構，例如 C++ 的 map 就是典型的 binary search tree 實作. 如果你常用的程式語言裡沒有提供 binary search tree 的實作，我強烈建議你應該要在網路上找找是否有其他人做好成熟度夠高的實作，因為 binary search tree 的應用實在很多而且很好用. 當然 binary search tree 並無法為你自動達成 "平衡"，所以才會有其他的資料結構產生用來解決這個平衡的事情，如 AVL tree, red back tree, B tree 等等. AVL tree, red black tree, B tree 也算是蠻有用的資料結構，不光是學術價值，其工業應用價值也是頗高，以後會寫文章來介紹它們.

閱讀全文