#38 Coding 面試 - LeetCode #2 Add Two Numbers

原文題目 https://leetcode.com/problems/add-two-numbers/

這題是個基本的 Linked List 考題，如果題到這類型的 List 題目，若題目沒特別說的話，就一律想成是 Single Linked List 了．其實，我個人不是很喜歡 List 考題，原因是大部份的問題都蠻無聊的，可能就在 List 上把元素搬來搬去，而且不一定會有一個很好的邏輯來搬這些元素，所以就會造成一個 function 寫的長長的．像這一題就是這樣．

題目給了兩個 input list，要把每個元素加在一起後，然後輸出一個最後的 list．其實也蠻簡單的，你只要在這兩個 input list 上一個一個元素去拜訪，然後把加起來的答案寫到新的位置上，同時再注意進位的事情．並且你也要考慮到兩個 input list 的長度可能是一樣長，也可能是不一樣長，甚至可能是空的．如果你按照這個想法寫，答案就可以寫的出來．

但是，就這麼簡單嗎 ? 基本上是的，但要注意一件事，上面的想法是會製造出另一個新的 list，算到最後把這個 list return 出去．這樣做的話就等於空間複雜度是 O(n+m) 了，假設 n,m 分別是兩個 input list 的長度．

所以，比較好的做法是讓空間複雜度變成 O(1)，也就是說每當計算一次元素的加法時，就把答案寫到某一個 input list 上，最後 return 這一個 input list 就行了，所以就不需要宣告出其他不是 O(1) 的空間．

參考的程式碼如下:

沒錯吧，又臭又長! 如果你能想到更好的方法來簡化以上的程式碼，再麻煩你教教我! ^_^

閱讀全文

#37 資料庫基礎 - Clustered Index 與 Non-clustered Index

在編號 #33 的文章中介紹了什麼是 Index．這可以說是資料庫對資料能快速尋找的主要方法，基本上也是一個用空間換取時間的方法，也就是為了更快速地找到資料，於是犧牲了更多的硬碟儲存空間來達成這件事．也因為如此，所以資料庫引擎也需要有相對應的功能來妥善管理這些特別的儲存空間．然而，儲存空間的內容不同也會影響不同的管理方法，所以這一篇文章將來介紹不同的儲存空間 -  Clustered Index 和 Non-clustered Index．

如果你曾撰寫過資料庫應用的相關程式或是你本身是資料庫管理員，相信你一定聽過 Clustered Index 和 Non-clustered Index．這兩個 Index 有什麼不同呢 ? 給一個比較簡單直覺的答案就是 Clustered Index 是根據某個資料在儲存空間上排列的順序而建立，而 Non-clustered Index 不一定要按照實體的資料排列順序而建立．

把 #33 那篇文章中的圖片再貼過來一次．

之前提過這是一份資料，按照學生證號碼排列寫入儲存空間的概念圖，所以你可以看到學生證的號碼有 1,5,7,11,13,16,23,24,36 這些號碼，而這些號碼基本上會被選做為 primary key，所以資料庫引擎可以利用這個號碼做為資料儲存位置的順序．因此，號碼小的一定寫在號碼大的前面，若不是在同一個 page 上的話，那一定是在前面的 page 上．所以，如果資料庫引擎用學生證號碼做為依據來建立 Index 的話，它的 Index tree 就有如上圖所承現．這一個 Index tree 我們就稱為 Clustered Index，也就是這個 Index 是依據決定實體順序排列的資料而建立起來的．其他種類的 Index 就稱為 Non-clustered Index．

所以，你就能知道為什麼在建立 Clustered Index 的時候你只能建立一個，而 Non-clustered Index 可以建立好多個，那就是因為實體順序排列只會有一種．

在尋找資料時，Index 特別強大的功能是在於某一個範圍內的尋找，比如，你要找學生證號碼 5 號的資料，或是找學生證號碼大於 20 號的資料．這類型的範圍尋找對使用 Index 來說是最好的．而 Clustered Index 和 Non-clustered Index 在這方面又有什麼差別呢 ? Clustered Index 的建立是依據資料實體的排列順序，所以當你執行了一個 SQL command 如 select * from students where ( ID < 10 and ID >0) ，你就會發現這只需要讀取一個 page 而己，這是以上圖為例子．如果你執行了另一個 SQL command 如 select * from students where street = '1st'，假設有一個 Non-clustered Index 是根據 street 資料而建立的，所以當你要尋找 street = 1st 時，這一個 Non-clustered Index 就會被用到，而且很有可能會指到許多不同的 page，比如 1 號學生和 36 號學生都住在 1st street．所以，Clustered Index 的尋找所需要讀取的 page 數量理論上會小於或等於 Non-clustered Index 所需要讀取的 page 數量．

總結，對資料庫引擎而言，不論是 Clustered Index 或是 Non-clustered Index，尋找資料的過程基本上都是一樣的，由於這兩種 Index 的特性不同，所以造成 Clustered Index 所帶來的維護成本較高 (因為實體的儲存順序就是 Index 上資料的順序，要變動比較麻煩)，而 Non-clustered Index 所帶來的維護成本相對較低 (因為只要改 pointer 指到新的 page)．

閱讀全文

#36 Code Review - 檢視你的程式碼

不論是寫好一個新的功能或是修改 bug，在程式碼都能正確執行並且在 check-in 到 source control server 之前，一定都會有一個 code review 的動作．這件事情通常是由比較資深的人員或對整體程式較為熟悉的人員來執行．Code review 帶來的好處很多，在這裡不一一描述，這對比較資淺的人員或新進的人員來說都是一件好事．因為透過 code review，新進或資淺的人員可以比較快進入情況．有時我們進入了一個龐大程式碼的專案，短時間之久是蠻難完全了解所有的細節以及那個團隊的寫程式碼的文化，所以透過 code review 來了解程式，也算是一種學習．

如果你工作的地方有執行 code reivew 的動作，那真的恭喜你，畢竟教學相長，透過檢視彼此的程式碼是一種良好的學習方式．也因為這跟團隊文化與團隊技術能力與要求上有很大的關係，所以 code review 實在很難說有什麼標準可言．除了程式碼要符合團隊的寫作規定外，要求嚴格的團隊甚至會到極為嚴苛的地步．

接下來，我分享一些我以前在 code review 中學習到的經驗．

1. 每個公司或團隊因為人的不同，所以要求的標準也不同，先不用假設對方是來找你麻煩，如果他對你寫的程式有意見，他一定能說的出原因讓你相信他說的是對的．

2. 如果你寫的是像 Java/C# 之類的物件導向的程式，這樣可能就會有點小複雜．因為同一個功能因每個人對物件的設計會不同，再加上會導入一些 pattern，所以當你不明白全部的內容時，會很容易就不是故意了犯了一些錯．也不用過於放在心上，這種事情是常常發生的．

3. 以我個人而言，程式碼寫的簡單乾淨好閱讀就行了，但是你很可能會遇到資深的工程師要求你要改的更簡潔．例如，

bool visited;
if (isActive == true) {
    visited = true
}

改成

bool visited;
visited |= isActive

基本上這兩個邏輯是一樣的，如果你被要求要寫成下面那樣的語法，就當做是個學習經驗吧!
其他像是變數名稱，物件名稱或屬性名稱也是會有類似的情況．

4. Comment 寫註解．做產品的公司會連註解也有嚴格的格式要求．如果是一般的程式註解，也是要寫到讓人看的懂，否則有寫跟沒寫是一樣的．

所以，如果你是新人，那就好好享受 code review 的過程吧，因為當你遇到一位功力深厚的前輩幫你 code review 時，保證你會收益良多的．

閱讀全文

#35 Coding面試 - LeetCode #94 Binary Tree Inorder Traversal

這題目出現在這 https://leetcode.com/problems/binary-tree-inorder-traversal/

如果要考 Tree 相關的題目，這一題算是相當經典的考試題目了．我想經典的原因就是 Tree inorder traversal 是資料結構課本裡面一定會教到的內容．大部份的課本裡面都會提供 recursive 的方式來做 inorder traversal，其程式如下

        public List<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int> ();
            if (root == null) return result;
            if (root.left != null)
                result.AddRange(InorderTraversal(root.left));
            result.Add(root.val);
            if (root.right != null)
                result.AddRange(InorderTraversal(root.right));
            return result;
        }

但面試官既然要考你這一題的話，絕對不可能只問你 recursive 如何寫，也一定還會問你怎麼用 iterative 的方式來寫．
如果你完全沒做過相關的練習，一時之間還真的很難想的出來該怎麼把 recursive 改成 iterative. 在這可以分享一件小事，因為寫 recursive 有階層的關係，所以程式的 call stack 就一層一層往上加，上一層結束回到下一層時也自然知道該從什麼地方繼續執行．但是若改用 iterative 的話，就沒有這種記住上次執行到那的好處了．對於這種需要記住位置的情況，就可以直接想想 Stack，因為 Stack 能幫助我們記住走過的痕跡．

所以，改成 iterative 的程式碼如下

        public List<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int> ();
            if (root == null) return result;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = root;
            while (stack.Count != 0 || node != null)
            {
                if (node != null)
                {
                    stack.Push(node);     // <-- 幫我們記住位置
                    node = node.left;
                }
                else
                {
                    TreeNode temp = stack.Pop();    // <-- 把上次記住的位置拿出來
                    result.Add(temp.val);
                    node = temp.right;
                }                              
            }
            return result;
        }

沒感覺嗎 ? 多寫幾次就會有了.

閱讀全文

#34 資料結構 - 非電腦科系的工程師們，你們體會多少了呢 ?

我第一次念資料結構時是因為準備台灣的資工研究所考試而念的，當時為了考試再加上時間也不夠多，所以念的很匆忙，沒有太多的時間思考著這門課程的精華．後來，念了研究所之後，研讀了一些學術論文，才慢慢了解到資料結構的精華．在許多學術論文裡都是討論著許多真實世界上的問題，通常這些問題會用一個數學公式或模型來表示，所以接下來的內容討論就可以直接在這數學公式或模型上直接去模擬．而這類的數學公式或模型若要用電腦程式來表達時，通常會發展出適合的演算法與資料結構．所以，這類的論文看多了之後，反而有幫助自己漸漸了解資料結構的精華．

基本上，電腦有二個基本的東西，一個運算器，一個是儲存空間．運算器就是大家所知的 CPU，而儲存空間就是記憶體和硬碟，其中記憶體是速度快但記憶時間較短，而硬碟是速度慢但記憶時間較長．這兩個東西你可以想成他們是長長的紙條，運算器可以在這長長的紙條上寫下資料，也可以讀取資料．

資料結構基本上就包含了兩件內容，一個是你需要用的資料是要寫在紙條上的何處，另一個就是如何在這些資料之間進行讀取或寫入．舉個例子，之前的文章提到 Array 這個資料結構．它的特性就是當你建立這個資料結構時，你必須先在紙條上找到一個符合你需要的足夠大的空間，而在資料之間進行讀取寫入的方式就是直接透過計算要讀或寫第幾個元素，就可以直接算出在紙條上的位址．例如，宣告了一個 byte array，一個有 20 個元素，如果第一個 byte 就是紙條上第 1000 個 byte 的位址，當我們要讀取第 5 個元素時，我們就知道要去 1005 byte 的位址上去讀取資料．

再舉另一個例子，Linked List．當你宣告了一個 Linked List 時，一開始你會先加入一個元素，這個元素可以寫在紙條上任何足夠空間的地方，而當你再加入另一個元素時，此時運算器就在紙條上任意一個足夠空間的地方把資料寫下，然後再回到第一個元素的位址上，把第二個元素的位址寫在第一個元素的空間中．所以，你可以知道在每個元素的空間中，除了元素的資料以後，還有下一個元素的地址．因此，當你想知道這個 Linked List 有多少元素時，你就必須從第一個元素一直讀到最後一個元素．

因此，課本裡面教的都是一些最基本的資料結構，就好像數學裡的四則運算一樣．電腦世界裡面的執行過程都是把紙條上的資料讀過來寫過去．當你發現你需要的問題很難用這些基本的資料結構來表達時，這時就是可以發明新的資料結構的時候了．

也許你會問，那這些跟平常的工作有什麼關係嗎 ? 比如，每天都在寫 JavaScript 搞前端畫面或是都在寫 java 寫後端程式．其實，多多少少會有關係的，尤其是你用物件導向在寫程式時，你所宣告的 class 就像是你定義了一種資料結構，這個 class 裡面所用到的儲存方式和運算方式都會大大地對程式在各方面有影響．就像是你知道了 Array 和 List 有何不同，你才會選得較適合的資料結構，也才能寫出比較快的程式碼．

未來的文章，不論是討論資料庫或是面試題目，你們都可以好好地思考一下是否還有其他可用的資料結構．不同的資料結構就代表程式的內容是不同的，可能會更好，也可能一樣，但也可能更差．所以，非電腦科系的工程師們，你們體會多少了呢 ?

閱讀全文

#33 資料庫基礎 - 什麼是 Index

Index 在資料庫的領域裡算是很基本且極為重要的項目，因為它幫助我們可以在龐大的資料裡快速地找到資料．這一篇文章就來說明 Index 運作的原理．

Index 也是一種典型的用空間換取時間的做法．這感覺就像是書籍裡最後面會有一些專有名詞在那一個頁數中可以找到，透過書籍的 Index，你可以很快找到你要找的專有名詞．同樣的，在資料庫裡也是類似像這樣的做法．資料庫引擎可以將你感興趣的資料製做成 Index，如此一來，資料庫引擎只要在 Index 上尋找目標，就可以很快速地得知該筆資料的位置是在資料庫檔案裡的什麼地方．這些就是 Index 概念．舉個例子，在資料庫裡有一個學生資料的表格，表格的 primary key 是學生證號碼，其他的欄位有名字，班級，地址，電話，性別等等．誠如以前的文章曾提過，這個表格有 primary key，所以基本上來說資料庫引擎就會以 primary key 的排序順序做為資料在 page 上儲存的順序．因此，當我們用學生證號碼做為尋找資料的依據時，資料庫引擎就會在 page 上依序地找出我們要的學生證號碼那筆資料．這是在沒有 Index 的情況下．如果你腦筋動的快，你會發現既然學生的資料已經是用學生證號碼排序好了，當我們要用學生證號碼來尋找時，何不用 binary search 呢 ? 沒錯，若你能這樣想，恭喜你已經漸漸習慣了用電腦科學來想事情了．但在這裡，binary search 真正能派上用場嗎 ? 那就要看資料是用何種方式儲存在 page 裡了．如果是用 directory based 的方式，還可行，但若是其他的儲存方式，那基本上不太實用．所以，為了不受儲存方式的干擾，我們可以用更多的空間來儲存成一個方便資料庫引擎搜找的資料結構，同時也享受快速尋找的好處．於是，有什麼資料結構適合呢 ? 答案就是 Tree．

如果我們把學生證號碼做成 Tree，如下的範例圖:

圖中數字為學生證號碼．資料庫引擎會依據學生證號碼的資料做成 Tree，也就是圖片上 Index tree 的部份，然後在 Index Tree 的末端節點上會放入該筆資料位置的 pointer．因此，只要 Index 一建立好之後，資料庫引擎就可以在 Tree 上遊走尋找想要的資料，若找到目標時，也可以馬上切換到該筆資料的位置．這就是為什麼透過 Index 的使用可以讓資料庫引擎快速找到資料的原因．

如果現在的情況改成要用學生的名字來做為搜尋目標，那麼上圖的 Index 就幫不上忙了，因為那個 Index 是以學生證號碼來建立 Tree．所以若我們希望用學生名字來搜尋時也能像之前的效果一樣，則資料庫引擎就必須以學生名字再來建立另外一個 Tree．所以，Index 的建立就必須是有意義的，如果隨便建立一些資料庫引擎用不到的 Index，那只是增加了資料庫引擎對資料維護上的成本而且也浪費更多硬碟空間．

這篇文章先為基本的 Index 概念先開個頭，之後的文章會再來介紹更多有關 Index 的故事．

閱讀全文

#32 資料庫基礎 - 資料讀取的成本評估

在前面的文章裡曾提供當資料庫引擎要儲存資料時可能有三種方式可以選擇，分別是 heap file, sorted file, 和 hashed file.

Heap file

基本上就是沒依照任何的規則來儲存資料，也就是說你先把資料A寫進去，然後再寫資料B，則自然而然地 A 的位置就會在 B 的前面．正常情況下，我們似乎不太希望用這種方式來儲存資料，因為它對資料搜找的速度上並沒有什麼幫助．

所以，假設資料一共分佈在 p 個 pages，然後每個 page 的讀取或寫入的平均時間為 d，那麼在尋找資料時所花費的成本便是 p*d，這是以最壞的情況來看的，因為我們無法知道我們要找的資料是在前面的 page 還是後面的 page，所以在成本評估時就用最壞的情況來看．

如果做 insert 動作，heap file 的特性會讓新的資料一律從最後面加入，所以必須要從第一個 page 走到最後一個 page，然後再做寫入的動作，所以寫入的成本是 p*d+d．

如果換成是一個資料刪除的動作，那就是尋找資料的時間再加上一個資料寫入的時間，所以也是 p*d+d．這也是以最壞的情況來打算的．

如果我們平均來看的話，假設需要找的資料有一半在前面一半的 page，另外一半落在後面一半的 page，而每筆資料都會被尋找，則搜尋的時間成本就可以想像成 p/2 * d，也就是說長時間下來每一筆資料都會被尋找，所以搜尋成本才會除以2．同樣的想法也可以推廣到 delete 的動作．Insert 的動作都是加在最後一個 page，所以平均來看的話，這並沒有差別．

Sorted file

資料會依照某一個規則來排放在 page 之中，這個規則如果能讓每筆資料能顯露出獨立的效果是最好的，比如依照身分證號碼或是員工編號，但這不是必要條件．我們也可以用員工的姓氏來做為排列的規則，這樣至少你可以確定同一個姓氏的員工資料就會被放在同一個或是附近的 page．所以，我們可以明確地知道如果資料是用 sorted file 方式來儲存，這將對於搜尋會很有幫助 ? 為什麼呢 ? 還記得之前文章曾提過的 binary search 嗎 ? 當資料以某一種規則排列好時，binary search 可以讓搜尋更快速，有多快呢 ? 還記得 binary search 的時間複雜度嗎 ? 它是 O(log n)，再重複一次，在電腦科學的世界裡，大部份的情況下 log 是以 2 為基底．

因此，對於 sorted file 而言，尋找資料的成本就是 log (p*d)，這裡的 p 和 d 跟前面的定義是一樣的．

如果是 insert 的動作，因為這是 sorted file，所以需要找到適當的位置然後再做 insert 的動作，所以 insert 的成本就是尋找 + 寫入，因此就是 log (p*d) + d，前提 insert 動作不會造成 page split 的現象發生，也就是說 page 裡面有足夠的空白空間可以寫入新資料．

如果是一個刪除的動作，資料必須要先找到，然後再加上寫入的動作，所以成本也是 log(p*d) +d．以上這些成本評估都是基於資料排序的規則會被應用到，比如，如果是員工資料用員工編號來排序時，那麼資料在被尋找，被新增與刪除時，都必須提供員工編號才能達到上述的成本評估．

Hashed file

Hashed file 的安放方式是讓資料經過 hash function 的計算之後才決定要放到那一個 page．如果 page 有足夠的量而且 hash function 夠好的話，就不會有 overflow page 的發生，也就是說 hash function 計算出一樣答案的資料在同一個 page 能提供足夠的空間了，不需要再連結到其他的 page．由於 hash function 的時間複雜度是 O(1)，所以這是相當有吸引力的儲存方式．

因此，如果是要找資料的話，只是經過 hash function 運算，然後就知道去那一個 page 進行讀取，所以成本是 d，這前提是沒有 overflow page．如果有 overflow page，那成本就還是加上拜訪這些 overflow page 的成本．

如果動作是 insert，一樣經過 hash function 運算後，就知道要去那一個 page 進行資料寫入動作．假設該 page 仍有足夠大的空白空間，則成本也是 d．如果動作是 delete，一樣經過 hash function 運算後就知道要去那一個 page 做資料寫入的動作．假設沒有 overflow page 的情況，則 delete 的成本也是 d．

你可能會覺得用 hashed file 有很好的成本效果．在真實世界的情況下，資料量通常會大，當然硬碟空間也相對地很大，所以 page 的量也會很大．如果你今天要找的資料是很接近的，比如要找員工第一號和第二號，用 hashed file 的方式很可能會造成兩筆資料會被儲存在相距很遠的 page，雖然資料庫引擎很快就計算出來要去那些 page 抓資料，但是硬碟就會忙於東奔西跑去讀取資料，所以也別被 hashed file 的低成本給騙了．

不同的實體儲存方式都有各自的優點和缺點，資料庫引擎會看資料的情況或管理者的安排來決定什麼樣的安排方式會比較好．如果我們不是專門的資料庫管理員，這種實體的儲存方式通常不需要我們來操心．但若你是專門的資料庫管理員而且資料已經成長到相當大的數量時，此時你就必須要知道你的資料是如何被儲存，這樣才能幫助你思考效能改進的事情．再講下去的話就會偏向市面上的商業產品與工具了，所以就到此打住，畢竟此網誌儘量不講產品和工具，只講跟電腦科學有關的想法．

閱讀全文

#31 程式該怎麼分辨好壞呢 ?

上個星期看到一篇短文，文章網址如下
http://buzzorange.com/techorange/2015/10/08/the-six-most-common-species-of-code/

這文章很有趣，它列出不同的人會如何寫出同一個 function．

看到學生寫的就是很標準的學生該有的答案．儘管 recursive 的寫法會有 call stack overflow 的問題，但對一個學生來說，重點是練習 recursive 的思考，所以這樣寫蠻好的．

看到由 Hackathon 寫出來的答案，哈哈，老實說，我真的是打從心裡笑了出來．這個笑可不是嘲笑的笑，而是一種打從心裡佩服的笑，尤其是看到那一句註解 // good enough for the demo

再來看看新創公司寫出來的，其實看不出來這和學生寫的有什麼大差別．也許作者在暗示些什麼?

再來看看大公司．還真的是有大公司寫法的樣子．你是否曾想過大公司的寫法為何是這樣子呢 ? 明明是個很簡單的數學式子而己．我能想到的幾個原因如下:

1.  大公司所生產的產品都具有一定的規模，所以在具有規模的產品下，一定會有許多設計是為了滿足軟體設計的一致性．所以，可想而知，這種具有規模的程式碼一定都是抽象再抽象化，把物件導向常用到的觀念一定都會套用進去，所以你才會看到也許明明是一個簡單的動作卻要搞的好像很複雜的樣子．

2. 大公司也是從小公司漸漸演變上來的，程式經過長時間的演變並且很可能經過許多不同工程師的改進與維護，所以，一般人很難能很快速地看懂程式碼，因為實在有太多故事在裡面了．

3. 在大公司工作的工程師們，平均來說也都是書念的比較好，程式寫的比較好的人．這些人心中或許有一些優越感存在．這些人也許為了顯出自己的優秀，真的會寫出很優秀的架構與運作流程，但由於實在太優秀了，所以對一般人來說就比較不容易懂．

最後，我們再回到 Fibonacci 數列．在電腦與數學的世界裡，這是一個非常有名的數列．在學校學習有關 recursive 或程式設計時的基本練習題目．也許你也可能在面試的時候會遇到這一個題目．一般來說，大家都會直覺地用 recursive 來寫這個題目，因為學校課本是這樣練習的．以時間複雜度的角度來看，recursive 的寫法並不是最好的，更何況它會有 call stack overflow 的問題．我會建議大家改成用 dynamic programming 的寫法，從小的數字算起，一直累積到大的數字，時間複雜度只有 O(n)，而要付出的代價就是較多的記憶體空間．所以，Fibonacci 若把 recursive 改成用 dynamic programming 來寫的話就是典型的用空間換時間的方法．

再回到主題，那程式到底要怎麼寫才好呢 ? 其實，我欣賞 Hackathon 的寫法，重點並不在於寫的好不好，重點是這樣的寫法非常能表達出來作者明白所需要達成的目的是什麼．所以，把問題回歸本質，我們應該要問的是，輸入參數會是什麼，需要輸出什麼，有多少的 CPU 與記憶體可以用．把目的搞懂，再把限制條件搞清楚，這樣寫出來的程式不會離好程式太遠了．我們只要在我們關心的情況下讓我們的程式能正常運作就行了．在限制條件或需求之外，程式會有問題的話，那也不是我們需要關心的．

閱讀全文

#30 Coding面試 - LeetCode #125 Valid Palindrome

題目的網址: https://leetcode.com/problems/valid-palindrome/

這一種題目算是蠻基本的，以前在台灣找工作時曾遇過有個公司的考卷出這一題，而在美國找工作時，目前還沒遇過有人考這一題或是相似的題目．

基本上，這題就是要寫一個 function 來驗證輸入的字串參數是不是 palindrome．所謂的 palindrome 就是字串中第一個位置和最後一個位置的值是一樣，第二個位置和倒數第二個位置的值是一樣，以此類推．所以一個很簡單的想法就是只要一個 for loop 就可以做完這樣的工作，而且不需要線性成長的空間，因此時間上是 O(n)，空間上是O(1)，這是對答案的要求了．

但 LeetCode 出的這一題有一點點小小的變化，因為輸入字串中可能會有其他的符號，而這些符號是不列入規則的，所以題目上寫 "A man, a plan, a canal: Panama" 是一個合格的 palindrome，因為只要不是符號類的字元都一律跳過．因為有這樣的小變化，我們除了用一個變數來記錄前面開始的比較位置，也還多用了一個變數來記錄從後面過來的比較位置．由於這是固定的兩個變數，數量不會隨著輸入參數而改變，所以在記憶體空間使用上是固定的．

另外，我們透過一個基本的 function (IsLetterOrDigit) 來幫助我們辦別輸入字元是字母還是數字，我們假設 IsLetterOrDigit 的時間複雜度是 O(1)．實際上 O(1) 是可以做的到．最後，整個程式如下:

這個程式碼的時間複雜度是 O(n) , 而空間複雜度是 O(1).
這是一個很基本的考題，如果你的面試遇到這種題目，那表示面試官根本不想為難你．

閱讀全文

#29 測試，該如何開始 ?

對一個好品質的軟體而言，測試的確是件很重要的事情．你寫的程式是否能在你假設的情況下做出正確的反應，這也是許多軟體工程師們的挑戰．一般較年輕的軟體工程師們往往過於著重在寫程式的技巧，所以常常忽略了花時間在學習如何測試你的程式．其實，軟體測試的學問完全不亞於一般的軟體開發所需的知識，而很多人可能會有一個先入為主的想法，那就是程式如何都寫不出來了，那學如何測試有什麼用呢 ? 聽起來好像還有幾分道理，至少在十多年前我是這樣想的．後來接觸多了之後也漸漸發現，如何不知道如何測試的話，那你怎麼能知道你寫出來的程式一定能用呢 ?

一般來說 (至少在我的工作環境下是如此)，軟體工程師自己寫出來的 function 一定要自己寫好 unit test．這是蠻重要的事情，因為除了你，應該沒有人比你更了解你寫的 function 是什麼，但也因為如此，也容易造成自己在測試時會陷入一些假設的情境下而忘了一些測試條件．

我們來看一個很簡單的例子，

int Add(int x, int y) {
    return x+y;
}

以上是一個很簡單的加法，每個人都會寫．如果我們要為這個加法 function 寫一些 unit test，你會寫那些東西呢 ?

首先，我們先來找一些可行的例子，先來試試 test for pass，例如輸入 x=0, y=0 或輸入 x= 10, y = 10 之類的，如果你能得到正確的答案，那看來這個 function 是可以用的．

接下來，我們就要再多想一想，我需要把所有可能的數字組合都測試過一遍以確保這個 function 是正常的嗎 ? 如果你有時間的話，當然應該是要這麼做，因為一旦這個 function 送到客戶那執行時，你已經把所有可能的輸入組合都測試過了，所以你當然知道會不會有問題．但我們真的需要這麼做嗎 ? 其實也不用．關於這點，你可以在一般的軟體測試文章或書藉裡看到一個所謂邊界值條件的測試．據經驗來看，讓程式發生問題時有較高的機率會發生在邊界值的情況，例如 x = int.MaxValue 或 y=int.MaxValue，當你一輸入進去時，你就會發生這個 function 其實是有問題的，因為 integer overflow 了．

接下來，既然 x 和 y 是 int，那表示負數也是接收的，所以你還可以測試負數的邊界值，x = int.MinValue , y = int.MinValue，同樣的也會發生 overflow 的錯誤．所以，你就可以看到只要你把 x, y 的數值在可接受的範圍上跑了一遍，你就會發現這個加法 function 到底有沒有問題了．

接下來，你可能會說現在市面上寫的專案程式不是那麼單純呀．沒錯，我同意你的看法，的確都不單純，但寫 unit test 的精神還是一樣的．再看一個簡單的例子，

Result[] GetData( Connection conn, Command cmd) {
  .....
}

以上的 function 是一個根據命令 (Command) 在連線 (Connection) 上做一個取得資料的動作，取得到的資料將會以 Result[] array 的形式傳出來．

按照上述的第一步，你應該要先測試  test for pass 的情況，傳入正確的 connection 以及正確的 command，然後檢查是不是會得到結果．

接下來，我們可以調整 conn 和 cmd 的物件屬性，來測試 GetData 會如何反應．例如，故意把 cmd 輸入誤會的命令，或是故意把 conn 的狀態設定為關閉．甚至你還可以傳入空物件，看看 GetData 的行為是不是符合預期．

所以，你應該可以感覺到撰寫這些 unit test 的時間與力氣並不會比較少．尤其是一旦軟體能做的事情越多時，這些輸入參數的可能變化將是成指數形式往上成長，我們根本很難把所有可能的情況都試過一遍．如果你真的都試過了，那麼客戶會遇到的問題一定都會在你的掌握之中，甚至你可以在交貨之前就先修正這些問題了．但畢竟這只是理想，對一個具有某程規模以上的軟體而言，這幾乎是不太可能的事情，一來是時間，二來是預算等等的考量．所以，我們要做的也是在時間與預算範圍內能包含大部份的情況，比如 90% 的客戶都不會有問題等．

其實在設計程式時也有些技巧可以幫助你做測試，這些將都是未來文章的內容．

閱讀全文

#28 資料庫基礎 - 存取 Page (Hashed File)

前面兩篇文章提到了存取 page 的兩種方式，在這一篇文章裡要介紹的是另一種方式，我們稱它為 hashed file．聽到這個名字，你可能已經猜到這是和 hash function 有關係的儲存方式．沒錯，它就是利用 hash function 來決定儲存位置，也是就說透過 hash function 的計算來決定要儲存到那一個 page 上．

前面的文章曾提到過基本的 hash function，也介紹了它最簡單的運算方式．所以，假設一開始有十個 page，然後有五筆資料，我們可以將每筆資料傳給 hash function，計算出來的結果是 0 - 9 的數字，而這數字就用來代表要儲存到那一個 page 上．一旦資料變多時，資料的筆數一定會遠遠大於 page 的數量，所以同一個 page 上一定會有許多筆資料．因此，透過 hash function 的方式來計算儲存位置也是個蠻快速的方法．不過，資料庫引擎通常不會被設計成將整筆資料拿來 hash，因為我們在找資料時很少會用全部的欄位做為搜尋的條件，因此，我們通常會選擇幾個重要的欄位或是只選擇 primary key 的欄位來做為 hash function 的輸入值，而 hash function 輸出值就是 page 的號碼．因此，資料庫引擎在為我們找資料的時候，只要欄位條件符合的話，就可以透過 hash function 的計算而快速地得到 page 號碼．

接下來，你可能會問到，一旦資料量越來越大時，一定會有很多的資料經過 hash function 計算後會得到同樣的答案，而這些資料量會遠遠超過一個 page 得記錄的資料量．這種情況在我們談論 hash function 的時候也會發生，當時所採用的方法就是在 bucket 上做一個 list 來承接更多的資料．相同地，在這裡也是可以用相同的觀念．如下圖:

如上圖的上面那個 page，當它沒有足夠的空間承載更多資料時，此時資料庫引擎就必需要一個空白的 page ，然後在前面的 page 做一個連結到空白的 page，接著就可以把屬於同一個 bucket 的資料寫進去．因此，你可以看見的是，如果 hash function 的 bucket 準備不多的話，那麼資料就會長成像幾條很長的 page life，我們並不希望碰到這樣的情況．所以若要採用 hashed file 的儲存方式，則該 hash function 需要有能力產生足夠多的 bucket，甚至最好是能彈性處理，依照資料的多少來決定，但相對地要做多的配套措施．但若以好的角度來看，用 hashed file 的結構來儲存資料，對資料庫引擎而言可以大大提供資料搜尋的速度．

有關資料如何儲存在 page 上，從儲存的方式來看基本上有三種方式，而每一種方式都有其優點和缺點，所以針對不同的資料，根據他們的特性來決定用那一種儲存方式將是比較好的決定．要怎麼評估呢 ? 我會把評估的成本估算寫在未來的文章裡，讓大家知道資料庫引擎是根據什麼樣的數據來決定要用什麼方式儲存資料．

閱讀全文

#27 Coding 面試 Leetcode #98 Validate Binary Search Tree

我記得這一題我被問過兩次，是兩個不同的團隊，而且都是跟資料庫有關的工作．所以，若你也要尋找資料庫相關的開發工作，看來 Tree 的題目是很難避免的．

這題的題目很單純，就是要寫一個 function 用來驗證題目的 Tree 是不是 Binary Search Tree (BST).
根據 BST 的定義，左邊的節點值必需小於父節點值，而右邊的節點值必需大於父節點值.
但這題有一點要小心的是，別只是檢查父節點值而己，應該要檢查所有上層的父節點值都要小於或是大於．

如果題目只給你 tree root，那麼你可以寫出像下面的 function 來檢查這個 tree 是不是 BST.

        public bool IsValidBST(TreeNode root)
        {
            return BST(root, null, null);
        }

        bool BST(TreeNode node, int? min, int? max)
        {
            if (node == null) return true;
            if (min == null && max == null)
            {
                    return BST(node.left, min, node.val ) && BST(node.right, node.val , max);
            }
            else if (min != null && max == null)
            {
                if (node.val > min )
                    return BST(node.left, min, node.val) && BST(node.right, node.val, max);
            }
            else if (min == null && max !=null)
            {
                if ( node.val < max)
                    return BST(node.left, min, node.val) && BST(node.right, node.val, max);
            }
            else
            {
                if (node.val > min && node.val < max)
                    return BST(node.left, min, node.val) && BST(node.right, node.val, max);
            }
            return false;
        }

若你仔細看的話，我是把每個分支出去時可能的節點值範圍也傳遞過去．這樣的寫法也許不是最好，但就如之前文章所說，要在五分鐘內想好然後在半小時內寫完再測試，所以就勉強用了.

這時候如果遇到要求更高的面試人員，他可能會說 recursive 的方法不適合用在 tree，所以要改成 iterative 的方式來寫．
其實要改成 iterative 的方式，說難不難，說簡單也不簡單，因為要在那短時間想出來也是件不容易的事．比較幸運的是之前我有練習過 BST 用 In-order traversal 的走法來驗證 BST，所以這題也就順利寫完了，以下就是改成 iterative 的方式，用 In-order 走訪 BST 之後，得到的答案一定是從小排到大的數值，所以只要多一個 for loop 來檢查數值是不是從小排到大即可.

  public bool IsValidBST(TreeNode root)
        {
            if (root == null) return true;
            List<int> re = InOrder(root);
             if (re.Count == 1) return true;
            for (int i = 0; i < re.Count - 1; i++)
            {
                if (re[i] >= re[i + 1])
                    return false;
            }
            return true;
        }

        List<int> InOrder(TreeNode node)
        {
            List<int> result = new List<int>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (stack.Count != 0 || node != null)
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.left;
                }
                else
                {
                    TreeNode t = stack.Pop();
                    result.Add(t.val);
                    node = t.right;
                }
            }
            return result;
        }

雖然在初步面談中都把上述的題目做完了，但這也不代表就有機會可以繼續做後續的面試．所以，很可惜沒能做成資料庫開發的工作，找工作真的一切都是個緣份.

閱讀全文

#26 資料庫基礎 - 存取 Page (Sorted File)

上一篇文章談的內容是針對資料之間是沒有順序的情況，因此在尋找資料時就是採用依照資料的排列順序來尋找．因此整個尋找過程的時間複雜度是 O(n) ．通常來說，資料庫設計者不會讓這樣的事情發生，除非資料本身是一個相當小的參考資料而己，否則資料一旦多了，  O(n) 實在不是一個好現象．

在真實世界中的應用，我們常常可以為資料找到至少一種排列方法，例如，在學校的資料庫中，基本上可以用學生證的號碼來排序學生的資料，因為在同一個學校裡不會有相同的學生證號碼．我們在前面的文章中也提過，一旦資料排序過了之後，時間複雜度就會從 O(n) 下降成 O(log n)，基本上就是 Binary search．因此，如果資料可排序的話，則資料庫引擎就可以依序地將資料寫在檔案中．

資料庫引擎為這些可排序的資料寫入到檔案中有兩個方式．第一種方式是直接將資料依序排列好寫在檔案中，所以每個資料的前後順序就跟排列的順序是一模一樣的，如果中間要插入一筆新資料時，就很有可能會發生 page split 的動作．如圖是一個例子．紅色的框框代表 page，而藍底的框框帶表一筆資料，而藍框裡的數字代表資料的序號，序號不一定要連續，只要不重複即可．所以一開始把資料寫入時，它的排列長相如下:

這時候如果要新增一筆序號 7 的資料，那麼它要排在 5 和 10 之間，但是該 page 已經沒有位置了，因此發生 page split．

資料 7 會放在前面的 page 還是後面的 page，這將由資料庫引擎內定的邏輯來決定．

第二種將資料寫入檔案的方式是讓資料的實體位置不需要改變，另外在建立 "目錄"，然後在這目錄上做 binary search 的動作．

在這種方式下，新增一筆序號 7 的資料時，它就可以直接在 page n+1 的地方寫入，然後資料庫引擎只要更新目錄的內容即可．

當新增一筆序號 7 的資料在目錄 page 時，此時會發現  page split 還是在有足夠的空間下把後面的資料往後移，這將由資料庫引擎的內定邏輯而定．因此，第二種方式就變成直接在目錄 page 上做  binary search ，然後再依照其內容 (pointer) 就可以找到該筆資料．

所以，你的 table schema 的設定理應當是都有 primary key 的存在，如此一來才能做為資料庫引擎排序的依據．其實，以上的內容基本上也就是 clustered index 和 non-clustered index 的精神．

閱讀全文

#25 資料庫基礎 - 存取 Page (Heap File)

        在前面的幾篇文章中提到了資料庫引擎讀取與寫入資料時在面對固定長度與非固定長度時所可以採用的儲存方式，其中提供了 Page 為一個儲存空間的管理單位，透過 Page 的機制，讓資料庫引擎能以 Page 為單位做資料讀取與寫入的動作．搭配上 Page 裡的 manifest 資料，資料庫引擎就可以很清楚地知道這個 Page 裡面有多少筆資料以及有多少剩餘空間可用．這時候我們把層次往上拉高一點來看，那 Page 跟 Page 之間的關係是如何定義呢 ? 舉例來說，當某一個表格裡的資料繼續變多時，這些資料很可能會需要很多的 Page 來能承載，那資料庫引擎又怎麼知道是那幾個 Page 是用來承載這表格的資料呢 ? 因此，我們也必須定義 Page 和 Page 之間的關係．

        要定義 Page 之間的關係最簡單的方法就是採用 Linked List 的概念，也就是說每一個 Page 都會記錄著上下一個 Page 的位置，這就像是 Double Linked List 一樣，所以資料庫引擎便很容易地在 Page 之間游走來尋找資料．參考下圖來看一個很簡單的例子:

上圖一共有七個 Page，其中 page 1, 3, 4, 6 前後之間有 pointer 指著上下一個 Page 的位置，這也代表這四個 Page 儲存著高度相關的資料，比如說是同一個表格的資料，或是同一份 index 的資料等．但什麼樣的資料會讓 Page 用這種方式儲存呢 ? 看來是隨意安排的資料，不需要排序，也不需要特殊的安排，資料先進來就先寫入．因此，當資料庫引擎在存取這類型的資料時所花費的成本就會很高，因為都必須從頭開始往後找．不論是找什麼樣的資料，尋找一律都是從最前面的 Page 開始找到最後的 Page．其實這也就是 Linked List 的特性之一．也就是說你要找的資料剛好落在最後一個 Page 的時候，資料庫引擎就必須要從最前面的 Page 一直找到最後一個 Page．因此，這樣所花費的成本是相當高的．

所以，這也告訴了你一件事情，如果你的資料用上述的方式來儲存，這將造成資料庫引擎花費許多時間成本來尋找與寫入資料，而這種像 Double Linked List 的 Page 關係方式，一般的課本稱它為 heap file. 後面的文章會再繼續介紹其他方法．

閱讀全文

#24 我的 IT 人生 - 簡短篇

這一篇內容我不談資料結構，也不談資料庫，更不談寫程式，我來簡單地談一談自己的 IT 人生．

在我還是高中生時，當時有接觸一些電腦課，學會了操作 MS-DOS 系統，也會寫一些簡單的 BASIC 程式，對電腦的確是有相當興趣，但還沒想過要把它當成一生的工作方向．後來，念了大學之後，我念的是機械工程，原本我的打算是想要念電機工程，因為自認為在物理課本中，電學念的比力學好很多，不過也奇怪，我當時還是把機械工程填入到志願卡裡，若我印象沒錯的話，我記得我的志願卡裡還有土木工程電子工程等等相關的工程科系．大學四年就這樣念到畢業了，說實在，到現在我還是覺得大學那 4 年似乎是浪費的，因為我現在沒需要用到任何機械工程的知識．不過，人生就是這樣，現在回過頭來看，就當做是用人生的時間換來了一些人生經驗．

接著，學校畢業後就直接去當兵了．我想這是我整個 IT 人生的起點．我很幸運地被分配到資訊單位，我還記得一進去時學長丟給我一本書，網路概論．我就從網路開始學習，從區域網路到廣域網域，也包含通訊協定如 TCP/IP 等等的都學了，後來還得學習寫網頁程式，一開始用 CGI 後來用 ASP 寫．在那近兩年的時間裡就像是一個職業訓練所一樣，我把基本的網路和網頁程式學了起來，退伍後就直接在資訊業找了工作．當時是差不多 2000 年的時候，Internet 和電子商務正在蓬勃發展，所以許多公司也不會在乎學歷或科系，只要真的能拿出工具寫出一些真實的東西，很多公司都是歡迎的．我的印象中，當時我快退伍找工作時，每個星期總是可以收到公司邀請面試的信件．

在工作了幾年後，我腦中漸漸地有越來越多的問號，比如要怎麼才能寫出好的程式，要如何才能是好的設計，甚至細節到為什麼資料庫的搜尋可以這麼快，在工作上有太多太多的問題實在讓我很好奇．因為我覺得我如果要在工作上更進一步的話，我最好還是去了解這些問題的原因，因此我決定回學校去念書，但我選擇不是回去念資訊科系的大學部，我選擇是去考資工研究所．我還記得當時大部份的學校都會考資料結構，演算法，作業系統，計算機組織以及離散數學．我當時買了一堆書，一堆補習班的講義就開始念了．在念書的過程中也得到不少的收獲，比如作業系統裡提到了 CPU Scheduling 才知道電腦要做多工環境的概念，念了資料結構也才知道原來程式的效能是透過 Big O 來評估的．在那過程獲得不少心得，但可惜準備的時間太少還無法完全熟悉以及融會貫通，最後我用三個月的念書時間考到一家國立大學後段班的資工所．

在念研究所時，我已經 30 歲了，對自己來說算是項蠻挑戰的投資，在那段時間我到大學部去上課，作業系統，離散，資料結構，演算法等等，把這些基礎課目透過學校課程補起來，然後也念了物件導向，分散式系統與資料庫等課程，自己也蠻開心可以走到這一步．在畢業前，我收到了一間美國大學的入學許可，我申請到了電腦科學博士班，畢業一年後，我就前往美國念書．到了美國後，學校規定演算法和計算理論是必修，成績不達標準不能畢業，光是這兩個科目就讓我很辛苦，重修一次後才過關，也是因為這樣的辛苦，所以對電腦科學才有更進一步的認識．雖然最後沒能把博士學位完成，但還是覺得自己能走到這一步也是不賴了．在我大學剛畢業時，我可從沒想過自己能走到這樣的地步．

寫這篇文章時，我 40 歲了，在美國一家軟體公司上班，每天就寫著一些程式來改進公司的工具與產品．從現在回過看，在我 28 歲之前，連 Big O 是什麼都不知道，也不知道什麼是 Binary search，這十年來的變化就好像變魔術一樣讓自己的 IT 人生起了很多的改變．把自己的 IT 人生寫的很簡短，現在我有新的人生方向，但短期內還不會離開資訊業，就如同前面說的，這一切都是自己的選擇而造就自己的人生經驗，也希望這些經驗能提供其他年輕人做為參考．如果你認為我有值得讓你參考之處，歡迎你留言給我. ^_^

閱讀全文

#23 Coding 面試 Leetcode #73 Set Matrix Zeroes

我打算把以前遇到的一些在面試時遇到的一些特別經驗或感想記錄在這電腦科學筆記裡，一方面，在面試時會遇到的問題大部份都是基礎的電腦科學題目，二方面也把這些過程記錄下來，當做是一種紀念吧!

在美國的軟體行業裡，要做 coding 面試算是很正常的事情，而這些 coding 面試大部份都是資料結構和演算法的內容，所以都是大學的必修課．但其實有許多題目還真的不是光念過課本就能想的到，那些題目還真的需要多練習．在市面上有許多網站會列出一些常見的面試考題，而我之前最常去的網站就是 Leetcode. 這網站不僅記載了許多考題，而且還有 online judge 可以直接測驗你的程式碼是否正確.

今天來聊聊這一題，在 Leetcode 網站上的第 73 題．我被問過一模一樣的題目，面試者連改都沒有改，而這一題也讓我體會到另一種空間複雜度的境界．

第 73 題的題目是指，給你一個 m x n 的矩陣，如果在第 (i,j) 的位置上出現 0 時，就要把 row i 和 column j 的元素全部變成 0．剛看到這個題目，覺得不會很難．最直覺的方法是你可以宣告兩個 Array 或 List 來記錄那些 row 和 column 裡面有 0 ，最後再依據 Array 或 List 的內容把相關 row 和 column 的內容變成 0．如果你是這樣想的，其實這方法也沒什麼不好，只是要多浪費一點空間，因為另外宣告了額外的 Array/List 來記錄那些 row, column 有 0 的元素存在，而且 Array/List 的大小會根據矩陣的大小而改變，因此在空間複雜度上就不是 constant 了，而是 O(m+n)．如果這時候面試官沒繼續要求的話，那基本上就過關了．但生活中有時很難會如此順利，面試官很可能會要求你在空間複雜度上做到 constant space．也就是說你可以用其他的空間，但是這些額外的空間不能隨著矩陣大小變化而改變．

既然是這樣規定的話，這題目就真的變得有相當的難度了．我自己在做這題目時也無法在五分鐘之內想到好的解答．為什麼是五分鐘呢 ? 因為一個面試通常是一小時，其中做 coding 考試的時候大約有三十分鐘，所以在五分鐘之內沒有想出正確答案的話，那就很難可以在剩下的時間把程度寫完在白板或電腦上．
後來，我參考了網路上其他人的解法，我找到一個蠻好的解法．基本上，這個解法要宣告兩個基本的變數，這是  constant space，而它把每個 row, column 有 0 的資訊直接記錄在輸入矩陣之中，因此，根本就不需要用到非 constant space 的空間了．

如果你用心把這個解法看完的話，你一定也會覺得這方法實在太妙了，而且保證你對空間複雜度的應用會有更高一層的體會．原來把 input parameter 的空間拿來做為暫存空間，也是一種省空間的好方法．

閱讀全文

#22 資料庫的資料實體儲存單位 Page - 3

在來延續上一篇文章 (#21  資料庫的資料實體儲存單位 Page - 2) 的內容．在上一篇的文章中看到了如果沒有 page 的概念時，資料庫引擎有那些可行的方法來在硬碟上管理資料，從上一篇文章中，你看感受到空白空間的處理與以及資料的定位並不是很方便．於是在階層管理的方便性上多加了一層 Page．

在一般市面上常見的資料庫產品中，Page 的大小都大約在幾Kb之間，類似於作業系統的儲存單位大小．所以，一個資料庫可能會包含一個或多個資料庫檔案，而每一個資料庫檔案都會包含多個 Page．

我們再看看如何用 Page 來管理資料．如上一篇文章的情況，資料有可變長度與固定長度兩種．固定長度的情況是比較單純好處理，可以參考下圖:

上圖是某一個 Page 的示意圖，由於每筆資料都是固定長度，所以每一個 Page 都可以儲存相同數量的資料筆數 (除了最後一個 page 可能因為資料筆數無法除盡，所以不一定有相同筆數)．在每個 Page 的最後面會留下一些小空間用來做為目錄式的記錄，所以可以從這小空間中可以知道這一個 Page 一共儲存了多少筆數的資料，同時也可以知道每一個位置是不是都有資料．以上圖為例，我們透過 delete 語法刪除了一筆資料，而這筆資料剛好是位在這個 Page 的第二個位置，所以可以看到在目錄式記錄上第二個位置是 False (boolean)，用一個 bit 就可以表達完成．所以，當有新資料要寫入時，資料庫引擎就可以讀取每個 Page 上的這目錄就可以知道那一個 Page 有多少的空間是可以寫入新資料的．因此，這種實作方式對 storage manager 的開發者來說相當簡單，而且空白空間也易於維護．

另一個情況是可變長度的資料．因為每筆資料的長度不見得會一樣，所以每個 Page 能放多少筆的 record 完全得視實際上每個 record 的長度來決定．在 Page 上安排位置時，在 manifest 那段小空間裡所放的內容就會有點差異了，如下圖:

由於資料非固定長度，所以在 manifest 上每一個位置都會有一個 pointer 指定到那個資料的位置，同時也會指出來空白空間是從什麼位置開始．上圖的狀態等於是資料經過了一些 update/delete 指令後才會出現的情況，因為每筆資料之間還是有空白空間的存在，但那些空白空間不會被資料庫引擎所使用，因為管理上實在太麻煩了，所以當有一筆新資料要寫入到這個 Page 時，資料庫引擎只會找這個 Page 上的空白空間 (灰色區塊)，只要有足夠的空白空間，那麼新資料就會被寫進來，同時更新 manifest 的相關 pointer 內容．

以上的內容是資料庫引擎對在一個 Page 內針對固定長度與可變長度資料的存取安排，所以你就可以想像的到當一個資料庫運行了一段時間之後，零零碎碎的空白空間一定是散落在資料庫檔案的各角落，而那些零零碎碎的空白空間是不會被資料庫引擎所使用．所以，資料庫的產品通常都會一個功能把這些零零碎碎的空白空間給消除，也就是讓資料靠的更緊密些，讓儲存空間可以在容量上得到發揮更好的效果．

閱讀全文

#21 資料庫的資料實體儲存單位 Page - 2

延續上一篇文章 (#19 資料庫的資料實體儲存單位 Page) 的內容，在這篇文章裡，我們來談談有關資料庫的實體儲存結構．所謂的實體儲存結構是指資料放在硬碟中的情況．

首先，我們先來看看一個很簡單的結構，資料長度是固定的．這種情況在前面的文章有提過．因為長度都是固定的，所以每筆資料的長度便可以固定，這樣好處是在於方便計算也方便存取．

另一種情況是資料長度不是固定的，這種情況在前面文章也有提過．因為長度不是固定的，因此必須要想一個方法把不同欄位的資料做一個區隔，這樣在讀取資料時才知道什麼情況下是資料欄位的終點．在實體資料儲存時，有兩個方式可以來達成這種目的．第一，在每個資料欄位之間都用一個特殊符號隔開來，長相如下:

上圖是用一個 # 來當特殊符號，這是很笨的例子，但只是方便說明用．在資料寫入到硬碟時，資料欄位之間會透過特殊符號做為間隔，而在讀取資料時，資料庫引擎也知道該如何處理資料了，而這樣的好處就是非常直覺且簡單，並不會浪費多餘的硬碟空間，缺點就是會浪費較多的資料讀取時間，例如我只要讀取表格裡欄位五的資料，那麼資料庫引擎就必須從欄位一讀取過四個特殊符號才能取得欄位五的資料．從前面文章中，你應該有學到一個精神就是當你對時間不滿意時，那就犧牲點空間去換取時間．所以可以把上述的儲存方式最一點小改良如下圖:

在整筆資料的最前面加上一個導覽式的目錄，裡面存放著每個資料欄位開始的位址起點，所以每筆資料有五個欄位，因此目錄裡就有五個 pointer，而每個 pointer 的內容就是一個硬碟位址用來記得資料的起點．所以當資料庫引擎要讀取欄位五的資料時就不用從欄位一開始讀取了，可以透過目錄裡的第五個 pointer 就可以直接找到欄位五的位址．

以上所說的方法都是很直覺且自然的，但我們來想像一下如果進行資料更新或刪除時會發生什麼事情?

先針對資料更新來討論，如果把欄位三的內容更新成較小的內容時，此時影響不大，只是欄位三後面會有空白空間，而我們該討論的是該不該保留這個空白空間．因為這裡討論的是每個資料欄位都有一個 pointer 會對應到資料，所以若我們保留空白空間的話，可以讓資料少了些移動，但也可能會浪費許多細小的空白空間．如果此時的情況是欄位三的內容被更新成比較大的內容時，例如更長的字串，接著就面臨到沒有足夠的空間問題了，解決方法會有很多種，也許比較簡單的是把整筆資料搬移到足夠大的空間，好讓欄位三可以容納下新的內容，同時前面的五個 pointer 的內容也需要一起改變．如果是刪除呢? 那就更單純了，只要把整筆資料在刪除或是做一個已刪除的 flag 即可．所以，從這裡我們可以看到，其實在更新時所面到的挑戰是比刪除的挑戰還要大很多．而且不論是那一種更新 (內容變多或變小)，都會遇到空白空間管理的問題．

所以我們可以發現，當資料庫的資料筆數越來越多時，讓資料庫引擎直接去對每一筆資料做管理時，其實是有點不方便的．因此，我們需要在這中間多一層實體儲存的管理單位，而這管理單位就是我們前面文章中所介紹的 Page．這種感覺就有點像一個國家不可能直接管理到每一個家庭，中間一定會有省，市之類的層級來做為分類，以便於管理上的應用．而 Page 也就是這樣的感覺．

閱讀全文

#20 The Power of Ten - 撰寫可靠軟體的思維

標題為 The Power of Ten - Rules for Developing Safety Critical Code 的文章刊登在 IEEE Computer 2006 年 6 月的月刊中，作者是位在 NASA JPL 實驗室的研究科學家，同時也是位學者和工程師．這篇文章可以在 http://spinroot.com/gerard/pdf/P10.pdf 看到．

若以武功修練來比喻的話，這篇文章就像是一個得道高人所寫下來的內功心法，他把自己在 JPL 實驗室工作的多年 C 語言工作心得濃縮成十項重點，作者也為每一個重點留下說明．雖然這一篇文章是將近十年前的文章了，但它的參考價值極高，而且我相信許多資深的軟體工程師幾乎都會同意作者所寫的內容．

其中有幾點並非在所有的程式語言中都會碰的到，尤其是跟記憶體管理有關的工作．以現在一般商業應用裡最常見的 C# 和 Java 語言都應該有其 runtime 環境的設計，所以記憶體管理的工作並不在程式設計者上，而是在開發其語言的公司上，所以這樣等於你把記憶體管理的工作交給其他人來處理了．我想這對 NASA 來說應該是不太能接受的事情，畢竟能打上太空的物體都是極為龐大的資金，因此 NASA 應該是不可能用類似像 C#, JAVA 這般的語言來打造火箭或衛星要用的軟體．回歸最基本的本質，用 C 應該是相當原始且基礎了．所以，在那篇文章裡，作者談了一些與 C 語言有關的準則．在這裡我不談特定語言，我們來看看其他的通用的準則．

1. Restrict all code to very simple control flow constructs – do not use goto statements, setjmp or longjmp constructs, and direct or indirect recursion.

這一點應用也沒什麼好再做說明的了，就是這樣，沒有 GOTO，沒有 recursion．所以在前面的文章裡，有些程式的寫法我提供了 recursive 和 iterative 的寫法，那時也提過 iterative 的寫法是比較好的．

2. All loops must have a fixed upper-bound. It must be trivially possible for a checking tool to prove statically that a preset upper-bound on the number of iterations of a loop cannot be exceeded. If the loop-bound cannot be proven statically, the rule is considered violated.

你想想看你寫程式時做到了這一點嗎? 你有沒有做過 while (true) 之類的語法呢 ?

4. No function should be longer than what can be printed on a single sheet of paper in a standard reference format with one line per statement and one line per declaration. Typically, this means no more than about 60 lines of code per function.

這是一定要的．若以 OO 的角度來看，有一個 function 能寫的很長，我都會懷疑程式碼一定在某些地方會有重覆功能的現象．

5. The assertion density of the code should average to a minimum of two assertions per function.

每個 function 平均來說至少有兩個檢查．這邊的檢查就是要防止一些不尋常的參數發生．比如你今天要寫一個加法，接收兩個 int ，如果傳入的參數是負數，那你的程式能處理嗎? 或是加起來的數字 overflow 了，你的程式能處理嗎?

6.  Data objects must be declared at the smallest possible level of scope

這應該是很直覺的想法，因為你不需要把不相干的資料物件提供給不需要該資料物件的程式碼．

7.  The return value of non-void functions must be checked by each calling function, and the validity of parameters must be checked inside each function.

這應該是每一個程式工程師要做的，只要呼叫的參數皆符合要求，那麼回傳值也需要檢查，同時還要注意是否有可能會產生其他的 exception ，都要記得做好 try catch 的反應動作．

10. All code must be compiled, from the first day of development, with all compiler warnings enabled at the compiler’s most pedantic setting.

最後這一點就是在考驗你們的專案裡有沒有良好的軟體工程流程以及 build system．工程師們一旦把程式碼 check-in 之後，所有的程式就應該要重新編譯，然後所有的測試案例都要執行．這樣才能即早發現問題，即早解決．

閱讀全文

#19 資料庫的資料實體儲存單位 Page

在上一篇文章中提到了有關資料庫 Storage manager 一點點的資訊．因此，這一篇文章就來談談更基礎的東西，叫 Page．它是什麼呢 ? 它就是 Storage manager 在處理儲存資料上的一種邏輯格式，也就是每個邏輯儲存空間的大小．這樣說可能還不好了解，讓我來直接舉個例子．資料庫引擎中有一個管理員叫 storage manager，它是負責資料儲存和讀取用，也就是說，今天使用者發出一個請求如 select * from table123，那麼這個命令就會經由資料庫引擎裡各式各樣的管理員來做語法確認解析，來做語法最佳化，然後可能還會經由其他管理員的檢查，最後才會到 storage manager，而 storage manager 負責的工作就是到磁碟機上正確的位置點，把資料讀取出來然後再回傳給呼叫它的管理員，最後資料就一直這樣被回傳到使用者端．因此，storage manager 就是負責找到資料在硬碟上的那個地方，然後進行資料讀寫．所以，你現在可以知道 storage manager 的工作是非常底層的．

那 Page 和 storage manager 又是什麼關係呢 ? Page 是資料儲存空間的一種單位．依不同的產品設計，Page 的大小可能不同，如 Microsoft SQL Server 的 Page 設計成 8KB. 所以，如果你的資料庫檔案設定為 8000KB，那就表示你這個資料庫檔案就有 1000 個 Page．然後這一千個 page 並不是全部都可以做為使用者資料儲存的用途，因為需要有一些空間用來儲存資料庫的設定與變數等，但我們在此先不討論這些系統所需的空間，我們把 1000 個 page 視為都是可供使用者儲存資料用．而 Page 設計的概念就是我們以前說過的 Linked List 概念，所以 Page 裡會有一個 pointer 指向下一個 Page 在那裡，因此，相鄰的 Page 在實體位址上不一定要在隔壁，他們可以分別位在硬碟裡前後不同的位置上．

所以，假設你現在要寫入一筆資料到一個新的表格，也假設這個表格只有一個欄位，其 data type 是 char(1000)，而且這個欄位是 primary key．當你寫入第一筆資料 "1111" 時，這筆資料就會被記錄在 page 1 的最前面，如果你寫入第二筆資料 "2222" 時，這筆資料也會被記錄在 Page 1 且在 "1111" 的後面，如下圖所示:

在上圖中，假設寬度剛好是 1000 字元，所以你會到 "1111" 在第一行，由於 data type 是 char，所以後面有 996 個空白，而第二行是 "222"，後面接著是 996 個空白字元．如果你繼續寫入更多的資料時，第一個 Page 看起來就會如下:

如果你再繼續寫入資料的話，後面的資料就會從第二個 Page 開始寫．所以 storage manager 在讀取這表格的資料時就會從這個表格的第一個 page 開始讀資料．

假設，此時你要寫入 "4567" 到這個表格中，因為這個欄位是 primary key，所以預設上來看，字元的順序就是實體資料要擺放的順序，因為 "4567" 必須放在 "4444" 和 "5555" 之間．但由於這一個 Page 的空間已被佔滿了，因此 storage manager 只好做一個 page split 的動作，也就是把一個 Page 拆成兩個 Page ，然後再寫入資料．

如果用 List 的動作來看，這就是在一個 List 中插入一個元素的動作．用 storage manager  的角度來看，它要先尋找一個完全沒用過的 Page ，然後將需要分開的資料搬到新的 Page 上，最後再更改 page pointer 位置來讓新 Page 的順序能安排在其中．這個動作並不是一個單純的動作，花費的成本還不小，從這裡就可以了解到，當我們做 insert 或 update 資料時，如果沒有安排好的話很可能就會造成大量的 page split 導致硬碟會很忙碌而形成效能上的瓶頸．

當我們討論到資料庫的讀寫效能時，Page 是一個很好的對象讓我們知道一份資料被讀取時一共讀了多少個 Page，這也就是代表了資料庫引擎的效能．由此可見，對資料庫引擎而言，這是多麼重要的基礎考量．

閱讀全文

#18 資料庫的表格裡有關 nchar 和 nvarchar 的選擇

今天正在思考要來寫個不學術的事情，也就是希望能寫個跟產品相關程度較高的主題，想著想著，突然有個回憶就突然閃過腦子．

大約在十年前，當時還在台灣念碩士班，有位在台灣 IBM 工作的朋友剛好介紹了一個很短期的工作，因為他們急著做一個專案，但臨時抽不出過多的人手來完成這些功能，所以就經由朋友的介紹去參與這項專案的開發，賺一點零用錢，只需要做 5 個 tasks 就行了．當時，我記得是用 Javva 開發，然後資料庫產品是 DB2．不過，當時我做的短暫工作跟資料庫並沒有直接關係．

有一天，我到專案辦公室時，剛好看到 PM 正在輸入一些新的 database schema，我好奇在他旁邊看著那些 schema 資料，然後我就發現了一件頗為特別的事情，所以字串相關的資料欄位都是設計為 nchar，比如 nchar(50)，nchar(100)之類的．於是，我就好奇一問 PM 為什麼所有的字串類的資料都是用 nchar 呢 ? PM 就馬上回答說，DBA 說這樣比較快．當我聽到這回答時，我似乎沒有完全明白為什麼這樣比較快．就這樣這個 nchar 與 nvarchar 的快慢問題就一直放在腦裡，沒特別去找答案，一切看何時有機會能遇到答案．

過了幾年後，我到了美國念書，某一個學期修了一門資料庫的進階課程，而當時的授課教授是一位印度人，他的實驗室有一個拼裝版資料庫引擎．所謂的拼裝版的資料庫引擎就是許多的功能都是由他的學生們經年累月的拼裝而成，有些是自己開發，有些是透過一些 open source 的引用，而當時我要拼裝的功能是 index search．

為了要製做 index search 用的 B-tree，我就必須學會如何透過該資料庫引擎的 storage manager 取得我需要的資料．就在了解 storage manager 的過程中，我無意間發現了一件事情而勾起了多年前的回憶，也就是 nchar 與 nvarchar 的差別．首先，我必需聲明的是 DB2 不一定是用一樣的方法，但我想以本質的精神來說是相似的．

在了解 storage manager 的過程中，我發現到如果資料欄位的 data type 設定為 nchar 時，這個固定長度會反應在硬碟的空間上，例如 nchar(500)，在硬碟上你會發現每一筆資料在硬碟上就一定會有 500 字元的長度，換句話說，你寫入進去的字串也許只有 10 個字元，但最後被放在硬碟上時還是有 500 字元的長度，而前面 10 字元是資料，後面 490 字元是空白．對熟悉資料庫的朋友們來說，這本來就是技術文件上會講的事情，但為什麼 nchar 會比較快呢 ? 那就必須再來看看資料庫引擎是如何處理 nvarchar．比如說 nvarchar(500)，你寫入進去的字串有 10 字元，在硬碟上所使用的空間就只有 10 字元，而不是 500 字元．直覺的反應下，你可能會覺得這樣跟快慢有什麼差別呢 ?

當我繼續往下看 storage manager 的程式碼後，我才發現到答案就在這裡．
我們來舉個簡單的例子，假設有一個表格，它的定義和範例資料如下:

ID - int	公司名- nchar(50)	地址- nvarchar(300)	電話- nchar(12)
1	公司 A	台北市忠孝東路1段1號1樓	02-12345678
2	公司 B	台北市忠孝東路3段300巷10弄100號5樓	02-87654321

ID 是這表格的 Primary Key，所以資料就會按 Primary key 的順序寫在硬碟上，而每一欄位寫的順序也就是跟其定義的順序一下，所以你會看到在硬碟上，寫第一筆資料時，第一個欄位是長度是固定的，第二個欄位也是也是固定的，第三個欄位不是固定的，最長可到 300 字元，而第 4 個資料是固定的．那麼問題就在此時出現了，以我們之前講過的 Array/List 來類比，如果你今天要讀取一個長度是固定的資料，你會怎麼讀取呢 ? 簡單的方法就是你會告訴 storage manager 說我要在某一個位置開始讀取 50 bytes 的資料，這樣對 storage manager 就很省事．如果情況變成長度是不固定的，就像表格的地址欄位，此時 storage manager 就不能如此瀟灑地直接讀取 300 bytes 的長度了，因為第一筆的地址沒那麼長，會把電話也讀進來了．因此，storage manager 就必須要先去 "探索" 一下這一個長度到底有多長才能決定要讀取多少長度的 bytes．就是因為這樣的 "探索" 讓 storage manager 多花費了一些作業成本，因此才變成 nchar 比較快的感覺，這正好呼應了當年在執行那個 IBM 專案時所得到的答案．以上是從讀取的角度來看．若從寫入的角度來看，你就會發現還真的很麻煩．以上述表格的資料為例子，如果今天第一筆的地址要更新成跟第二筆的地址一樣，那該怎麼辦 ? Storage manager 要寫入更長的地址資料時卻發現了原本的的地址長度不夠了，若強行寫入就會把電話資料給覆蓋掉了．你可能會想那就把電話資料往後挪，這樣的話也就會造成第二筆資料都要往後挪，如果這表格有成千上萬筆的資料，你一定不會認為這是個好方法．比較簡單但也是花費較大成本的方式就是 page split．至於什麼是 page，什麼是 page split，這是一個可以做為下一篇文章的好主題．

最後，你以為用 nchar 是最好的嗎 ? 固定長度也不是十全十美，因為固定長度的資料會被全部讀出來，以上述公司名來說，大部份的公司名只有短短幾個字，可能只有少數幾家公司的名字很長，但每次讀取還是會讀取 50 bytes，所以這 50 個bytes 就會從資料庫被讀出來，然後在網路上傳送到客戶端，客戶端的應用程式也是收到 50 bytes，但你需要的資料可能只有 6 bytes 而己，你會發現後面接著一大串的空白，必須自行將空白拿掉.

因此，nchar 和 nvarchar 到底那一個好那一個快，看來就要視你站在什麼角度上來看待了．至少我能告訴你的是以資料庫引擎的角度來說，nchar 的資料的確是簡單處理多了，但這不代表客戶端應用程式或網路效能也一定會如此同意．

這是一個小小的問題但背後連接到一個程式寫法的事情，下次你遇到這問題時，可以問問你的團隊技術領導者，看看他能否給你其他更多的思考．

閱讀全文

#17 客戶說程式碼不能有 recursive function，該怎麼辦 ?

不知大家有沒有被客戶這樣要求過，寫程式一律不準出現 recursive 的寫法．這也是十年前左右的故事了，並不是我個人遇到的狀況，是我朋友們遇過的情況．當時對這樣的要求沒太多的頭緒，不過心裡還是把這問題放著，也許有一天我會知道為什麼．

後來，有一次因為一個考試，突然讓我想到這個問題可能的答案，從技術角度來看的話，我想這應該是客戶的顧慮．情況是這樣的，在作業系統中，每個工作被執行的單位是 Process．一個作業系統裡會有許多的 Process 在執行，分別負責不同的功能，例如，有 Process 是專門負責處理 DNS 封包，有 Process 專門負責與印表機的通訊．所以，我們若自己寫一個程式在作業系統裡執行，這個程式也將是一個 Process，作業系統也就會負責他所需要做的工作內容．

在每個 Process 裡都會有一個獨立的記憶體空間用來儲存該 Process 需要的變數與資訊，其中有一項資訊叫 call stack，簡單的說是你的程式某個 function 呼叫了某個 function，然後再呼叫其他的 function，一直呼叫下去到作業系統的核心．因為這個記憶體空間的大小是有一個固定的量，所以當呼叫 function 一直無窮盡的進去下去的話，就很容易造成這個記憶體空間不夠用了，而形成了 call stack overflow 的情況．一旦這情況發生了，該 Process 就會被迫中止．

如果以作業系統的角度來想，程式裡不包含 recursive 寫法是很重要的．所以，一般的習慣都會採用 iterative 的寫法來取代 recursive 的寫法．在前面的 Binary search 文章裡，我們有介紹到 Binary search 的 recursive 寫法與 iterative 寫法．不同的情況會用到不同的寫法技巧，以 Binary search 來說，就是用兩個額外的 index 來做，如果是 Tree traversal 的話，通常是用 Stack 和 List 來把 recursive 寫法改成 iterative 寫法．

未來遇到適當的內容時，再來說明不同的 recusrive 寫法是如何改成 iterative 寫法.

閱讀全文

#16 我是非電腦科系的，真的需要懂這些嗎 ?

這問題其實一個很好的問題．

我假設你是個非電腦科系畢業出身的軟體工程師，回想一下，你當初憑著自己的邏輯能力學習如何寫程式，也學習如何善用大家所熟知的 framework，便可以應付自己工作上所遇到的問題．我想那是因為你的工作以及所面臨到的專案都是屬於商業型導向的應用程式．我所謂商業型導向的應用程式就像是你在金融界中工作，每個需要處理的就是把資料讀出來做報表，或把資料新增進去到資料庫，或是把這資料用某一種格式包裝起來，然後傳到其他的系統再做更多的資料處理．又比如說你在不同領域裡做該領域的工作，例如在航空公司做訂票系統，在電信公司做帳務系統，在電子商務公司做庫存系統．這些軟體工作其實在台灣是佔大多數的．所以，在這些工作中，若你沒有懂這些資料結構或演算法，你照樣也可以把程式寫出來，系統照樣地可以上線，公司照樣可以營運賺錢．因為我自己也曾有過這一段路，所以我知道是可能的．

不知你是否曾問過自己，我怎麼知道我寫的程式是不是好的，我該怎麼評估，或是別人又會怎麼看待我的寫程式能力．我相信非電腦科系畢業的人在做軟體工程師時一定會有這樣的問題．如果你有這樣的問題，很恭喜你，因為你的內心對知識有了渴望，因為你想知道自己的能力或寫程式的技巧是在什麼程度．所以，最好的方法就是回到事情的本質去找答案．因此，資料結構是需要懂的，演算法也是需要懂的，但我們並不用像 Microsoft 或 Google 工程師那樣了解所有的細節，我們只需要知道最基本的道理，這樣就能幫助你了解當某個產品某個新功能出現時，那些大公司的工程師是怎麼做出來的．比如，之前的文章談過 ArrayList，到底是 Array 還是 List，.Net framework在台灣還算流行，幾年前 Microsoft 把基本的 .net library 都開放原始碼了，所以你可以去看看 Microsoft 的工程師是如何設計 ArrayList，看它到底是 Array 還是 List．

若你從前面的文章一直看到這裡，到目前為止你可以發現我講了很多有關時間複雜度和空間複雜度的事情．所以，你就知道我們寫程式時會在乎的事情就會包括這兩個，而別人看待你的程式好壞時，自然而然也會從這兩件事情來思考．考慮程式的好壞的因素很多，而時間複雜度和空間複雜度算是最基本的要求．

所以，即便是一般的商業型應用程式，你也可以回頭去看看你以前寫的程式碼，是不是有些地方可以用 Hash table 能加快資料處理，是不是有些地方可以用 Binary search 能加快資料搜尋，是不是有些地方可以用了 Stack 讓程式更簡單好寫了．透過這種的改進，我相信你寫的程式一定會更有品質．因此，資料結構和演算法是很重要的，在未來的各項主題中都還是會一直介紹下去．

閱讀全文

#15 資料結構 Tree

Tree 應該是我們所需要介紹的最後一個基礎的資料結構了．在資料庫的領域中，你可以看到 Tree 在那裡發揮的淋灕盡致．以我個人來說，我喜歡把 Tree 看成是一種 List 的變形金鋼．前面在談論到 List 時，你可以發現 List 的元素後面只會接著一個元素，就這樣一個一個串接下去，這種情況就可以用在作業系統的檔案儲存．你可以把一個檔案想成是一個 List，而檔案的內容就會依照固定的大小分割成很多個元素，然後依照順序排好串在一起，這些元素就會散落在硬碟空間中，他們不需要排列在一起，所以同一個檔案的內容在放置時，可能是最後的元素放在硬碟空間前面的位置，因為元素之間都有一個 link 記錄下一個元素的位置在那裡．

對 List 來說，如果一個元素有一個 link 的空間來記錄下一個元素在什麼地方，這稱為 Single link list，也就是說元素往下走了之後就回不來了，除非從頭開始．如果一個元素有兩個 link 空間，一個用來記錄下一個元素在那裡，另一個用來記錄上一個元素在那裡，這稱為 Double link list，可能在一個元素上往前走或是往後走，但這種的實務上的應用比較少些．對於 Tree 來說，它有多個 link 可以記錄下一階層的元素在那裡，所以用畫圖來表示的話，看起來就像下圖．

以上圖來說，Tree 的資料結構是:

Class TreeNode {
    public TreeNode left;
    public TreeNode middle;
    public TreeNode right;
    public string Data;
}

一個元素可以連結到三個元素，這個跟 List 的元素只有連結到一個元素是不太一樣的．也許你會提出問題，連結到一個元素和連結到三個元素或是更多的元素有什麼差別呢 ? 差別當然很多項，以我目前來看，我覺得最大的差別在於找到元素的速度．舉個例子，如果你用一個 List 來儲存一系列的數字，即便是這些數字已經依照某一個規則排列好，你在找時還是要從 List 裡的第一個元素開始，然後一個一個往下找．所以，如果都沒找到的話，你所花費的時間複雜度就是 O(n)．現在，相同的數字依照某個特定的規則製做成 Tree 的結構，而當你找某個數字時，只要從 TreeNode 某一個節點繼續往下找即可，所以每當經過一個節點往下一階層時，你就已經捨棄了 2/3 的內容，只剩下 1/3 的內容要找．所以找起來的時間複雜度是 O(logN)，這裡的 log 是以 3 為底，因為 TreeNode 可分為三個節點．

這時你可能會認為如果 Tree 在搜尋資料上是這麼好用的話，那我們是不是可以多用 Tree 少用 List ? 這就很難有一個正確答案了．雖然 List 的搜尋時間複雜度是 O(n)，不過建立 List 是相當簡單的，但要建立一個 Tree 就不像 List 那麼單純了．如果你建了一個 Tree 而只拿它來用一兩次的話，這實在是不太符合效益原則．而且，Tree 的結構是適合用來做資料尋找的速度加快用的，而不太適合用來儲存資料，你想想如果今天有一堆數字要存在電腦裡，你把它儲存成 Tree 的結構，而接下來要把所有的內容讀出來，你覺得 Tree 結構所採用的方法會比 List 或 Array 來的更方便和簡單嗎 ? 答案顯然是不會的．再說，你把資料弄成 Tree 結構來儲存，在空間使用上並沒有佔到任何便宜．

所以，通常你看到一些資料索引的技術背後的基礎資料結構一定會採用 Tree 結構，原因就是加速資料尋找速度，但真正的資料並不會用 Tree 結構來儲存，只是索引所使用的資料是以 Tree 結構來儲存．許多資料庫的產品為了加速資料尋找的速度，便採用了許多 Tree 結構．我們這邊講的是一個較廣泛的 Tree 結構，在不同的應用情況下，會有特製的 Tree 做為在那些特定情況下的解決方案．以後的文章內容會再談到那些細節．

閱讀全文

#14 資料結構 Queue

在基礎的資料結構裡，Stack有一個好兄弟，長的跟它有一點像，但是提供的行為結果卻剛好相反，它的名字叫 Queue．在 Stack 中有一個可以把資料放入的行為叫 push，而把資料讀出來的行為叫 pop，並且最重要的重點是最先放進去的資料將會後最後被讀取的，所以這是一種先進後出或後進先出的情況．

類似於 Stack，Queue 也提供了方法可以將資料寫進去和讀出來，習慣稱為 Enqeueue 和 Dequeue．而跟 Stack 最大的不同就是 Queue 先寫進去的資料將會是先被讀出來，是一種先進先出或後進後出的情況．

你可以在資料結構的課本看到以上的內容，也可以找到 Queue 是如何被實做的，通常來說用 Array 來實做 Queue 會比較單純一點，只要一個 Array 加上兩個 index 用來記錄資料的起點和結束點．

我們在這邊不談論 Queue 實做的細節，我們來談談在什麼情況下它會派上用場．

在 Stack 的文章裡，你曾聽我講故事提到有關文字編輯程式中常用的 "上一步" 功能，透過 Stack 的實作讓我們可以清楚地製做 "上一步"． 所以，你可以感受到當你在用 Stack 的時候，資料的順序會被倒過來．例如，你放 A B C 三個資料到 Stack，而讀出來時的順序是 C B A．所以，當你遇到需要這種資料巔倒的特性時，別忘了使用 Stack．

那 Queue 的特性呢 ? 你會很直覺地發現它並沒有提供什麼特別的效果，因為 A B C 的資料寫進去之後，讀出來的順序也是 A B C，那它有什麼過人之處需要我用到它呢 ? 若你能這樣直覺地想，其實也沒錯，因為若沒有什麼特別考量的話，資料先進先出的行為是帶來不了太多的好處． 但我想到了一個情況，如果你今天撰寫一個 API ，而你回傳的資料有規定必須要從頭開始讀取，如果你只是回傳一個 List 或一個 Array，那麼拿到資料的人就很容易違反規則，可以從中間或是從最後面開始讀取資料， 如果你回傳的資料結構是一個 Queue，那麼就等於限制了使用資料的人必須要從第一個資料開始讀，而且讀過之後就不能再重覆讀取相同的內容．我想這才是 Queue 所要展現的特性．

所以，Queue 的特點之一就在於第一個資料要被讀取之後，第二個資料才能被讀取． 這樣的特性似乎可以帶來某種程度的資料準確性，因為中間不會有資料被忽略而未被讀取．所以某些作業系統裡面或是某些商業產品便會依據這種特點來做成一個功能或產品，稱為 Queue system，例如在 Windows 作業系統中有 MSMQ (Microsoft Message Queue)，而 IBM 也有 MQ 的產品．只不過這些產品的範圍更大，是用在多台電腦環境下的資料傳送，而傳送的特性就是跟 Queue 一樣，前面的資料要先讀取，後面的資料才能讀取．

在不同的需求情況下，我們可以依據資料結構的特性來找出適合應用的地方，到目前為止，我介紹了基本的資料結構有 Array, List, Stack, Queue 以及 Hash table. 這些基本的資料結構常常在日常的工作中被使用到，而且也幾乎滿足了大部份的工作需要．所以，好好了解這幾個資料結構，對一個不複雜的軟體開發工作來說就相當足夠了．

不過，因為我後面有許多內容會談到資料庫，所以還需要多介紹一個基本的資料結構叫 Tree，這是下一篇的內容.

閱讀全文

#13 利用 Hash Table 來增加你的資料處理速度

還記得十多年前參加一個專案時，自己做了一件不好的資料處理方式，當時的我還不知道什麼是 hash function．在那時候專案部份的工作需要快速地處理大量的資料，透過資料庫連線讀取資料，然後再讀取相關的參考資料，再經過運算，最後把結果再寫回資料庫，如果你的方法是讀一筆寫一筆的話，那肯定會造成大量的資料庫 I/O，所以比較適合的方法是做批次的處理，也就是一次讀取某個足夠數量的資料筆數，處理完成之後再一次寫回去，這樣可以減少資料庫的 I/O，也可以讓程式運行起來速度可以快些．

以上的想法是可行的，但當時有一個小小的挑戰是有關參考資料，因為資料在運算的過程中必需依靠其他的數據才能計算，而這些數據多達 8 萬多筆資料，簡單的說，它是三個欄位構成，第一個是分行 ID，第二個是一個會計科目 ID，第三個資料值．

分行 ID

會計科目 ID

資料值

第一個 ID 和第二個 ID 是有相關的，它們之間是一個 many to many 的關係，也就是說當我要尋找資料值時，我必須要知道這兩個 ID 才行．當時專案所運用的伺服器還有相當足夠的記憶體空間，算一算資料量後，我就決定把那 8 萬多筆資料全部載入到記憶體，心裡想若一開始就把這些資料載入到記憶體之後，這樣資料在批次運算的過程中就可以直接到記憶體取得相關資料，如果一來更大大地減少資料庫的 I/O．心裡打的如意算盤正是如此，但當時我卻笨笨地用 List 結構把載入這 8 萬多筆資料到記憶體中，所以每當我要找資料時，我就用一個 for loop 把這個 List 結構從頭找到尾，只要前面兩個 ID 是相等時，就抓出第三個資料值．當時心裡，資料都在記憶體裡了，就算跑一個 for loop，以 CPU 對記憶體的速度來說也算是很快了．事後跑起來，運算速度也還是改進蠻多的，所以當時不但沒對 List 結構做改善，還一直以為自己做了一件相當聰明的事情．

後來當自己念了資料結構之後才發現到當初用 List 結構是多麼笨的事情，用時間複雜度的角度來看，那是一個 O(n)，其實可以做到 O(1)的．那要怎麼做到 O(1)呢? 以這個例子來說的話，我們就要做一個 hash table 裡面包著一個 hash table.

以 Java 語法為例子的話，其資料結構定義就變成

HashMap< UUID, HashMap<UUID, Integer>>

所以在讀取的時候就變成 hashMap.get( 分行 ID ).get( 會計科目 ID ) ，如果這兩個 ID 都存在的話，則使用 O(1) 就可以得到資料值．雖然資料都載入到記憶體了，透過 Hash function 的運用，我們還是可以讓整個運算再快一點．

Hash 在一般的軟體專案中用途非常的廣泛，常常是我們利用空間來換取時間的最常見的手法，因此熟悉它並且善用它一定會對你的程式執行有極大的幫助．

閱讀全文

#12 利用 Hash Table 來改進 FindSum4()

在 #2 的文章裡曾寫到 FindSum4() 的 Optimization 寫法，其程式碼再重新呈現如下：

當時我們用了 if ( i != j ) 的方式來做為一種 Optimization 的做法，當 ary 的元素越來越多時，整個程式的時間複雜度還是會往 O(n²) 靠近．理論上，這樣程式的時間複雜度還是 O(n²)．

先前的文章介紹了 Hash function 的好處，我們可以運用 Hash 的概念在這一個程式，

(以上是C#程式碼) 整個程式是 O(n).

從時間複雜度的角度來看，我們利用 hash 將程式的 O(n²) 變成 O(n)，而付出的代價是什麼呢 ? 付出的代價就是我們使用了 hash 在記憶體上的空間，最上面的程式是不需要有特別額外的記憶體空間，但第二個程式使用 hash 付出了 O(n) 的空間複雜度，這種用空間換取時間的情況在軟體的世界是非常常見的，因為在大部份的情況下我們比較在乎程式能在多久的時間內完成．

希望這個用 hash 來改進程式空間複雜度的例子能夠激發出你在日常工作上的想像力．

閱讀全文

#11 如何快速搜尋資料 - 利用 Hash function/Hash table

前面文章講了 binary search，這篇文章來介紹另一個好用而且非常常見的分類方法，它叫做 Hash．談到 Hash 時，通常包含兩個部份，一個是 Hash function，另一個是 Hash table．在業界的產品上，如 .Net/Java 等，都有提供業界標準的 hash function 以上一些 Hash table 的應用，如 .Net 的 HashSet, Dictionary 等就是 Hash table 的應用．首先，我們先談 Hash function．

Hash function 有一個很重要的特點是運算快速，那要多快呢? 最好是  O(1)，也就是指運算的速度不應該與輸入量的大小有關．換言之，你可以想像成你有兩個字串要輸入 hash function，其中一個字串很長，另一個字串很短，當你同時輸入到 hash function 運算時，得到結果的時間是一樣的．若用數學來表示，它就是 output = H (intput) ，其中 H 就是 hash function．

實行 Hash 的方法有無數種，你可以寫一個很簡單的．Hash 的實作要怎麼寫，這必須取決於你用 hash function 的目的是什麼．例如，你只是希望把一大堆的資料做一個簡單的分類，那麼你的 hash function 就可以用簡單的 mod (數學的求餘數) 來達成．舉個例子，有一些整數，而你要把他們分類到三個籃子裡，最簡單的方法就是求 3 的餘數，餘數如果是 0，那就放在第一個籃子，如果是 1，那就放在第二個籃子，以此類推．所以，你的整數數字經過 hash function 運算後就會被分成三個群組．今天若有人要找這些整數數字中有沒有 77 這個數字，那麼他只要到第三個籃子 ( 77 mod 3 = 2)，然後把第三個籃子裡面的數字全部找過一遍就知道有沒有 77了．以這例子來看，在尋找 77 的過程中，我們只需要尋找 1/3 的數字，另外有 2/3 的數字放在另外兩個籃子裡是不需要去找的，這等於加快了找資料的時間．所以，從這個例子來看，Hash 的分類法還蠻好用的，如果今天籃子夠多的話，這樣等於每個籃子裡面所儲存的數字越更少，因此找到數字的速度就會更快．

如果你的 hash function 的目的不像前面談的做分類這麼單純的話，則 hash function 的實作就得符合你的目的才行．在一般基本的加解密裡，多多少少會用到一點 hash function 的功能，如果此時 hash function 寫的太過簡單，這將造成加解密不夠 "強"．什麼樣才叫做夠 "強" 的 hash function 呢? 前面說的，output = H(input)，input 是你所定義的輸入範圍，可能是所有的字串，可能是所有的數字，也可能是所有的正整數．output 也是你定義的輸出範圍．通常來說一個夠強的 hash function 都會給出相同長度的 output．也就是說，H(1) = KI87CJDL , H(-100) = O9DI3KJ4 等等．Hash function 的目的並不是要加解密，output / input 的關係不用是一對一，所以一個 hash function 很有可能讓兩個或多個 input 得到相同的 output，例如 H(54839) = H(abcd)，只要你 "很難" 能找到兩個 input 會得到相同的 output，我們就可以稱這個 hash function 夠強，其中 "很難" 的意思就是你得花很多時間才能找到．

當一個 hash function 夠強時，它就具有單向和不可逆的特性，也就是說因為 "很難" 找到兩個 output 會得到同一個 input，因此當你看到 hash function 的 output 時，你就 "很難" 知道 input 會是什麼，就算你找到了一個，也不代表它就是目標 input，因為多個 input 會得到相同 output．"很難" 不代表不可能，只是很難而己．

你只要選到一個適合的 hash function，便能幫你處理很多的事情，適合不等於要夠強，主要符合你的需求即可，如前面說的資料分類功能．Java 和 .Net 平台都提供了業界裡常用的 Hash function，比如 MD5 或 SHA 演算法，提供了不同運算位元長度 ．而 Hash table 就是讓 input 經過 hash function 計算之後，讓 output 值做為放到籃子的依據，就像 Java 的 Hashmap 或 .Net 的 HashSet 之類的資料結構．如前面所說的，籃子越多，資料就能分更多的群組，所以當一樣數量的資料量要分類時，籃子越多的，裡面放的資料就更少．

接下來，你認為把 input 透過 hash function 得到 output 放到一個籃子裡，它的 Big O 怎麼算呢 ? 如果籃子都是空的，那就是 O(1)，因為此時只是一個簡單的數學運算，如前面提的求餘數 mod．這個運算跟資料數量大小沒有關係，如果你自己寫的 hash function 不是 O(1)，那就問題大了，因為這失去了 hash table 的意義．如果籃子不是空的呢 ? 這就要看籃子是用什麼資料結構做的．一般來說都會用 List，所以有一個新的資料放到籃子時，如果籃子已經有資料了，那麼新的資料就會被加到 List 的最前面，這動作也是 O(1)，所以使用 Hash table 時，平均來說，它的 Big O 就是 O(1)，也就是說當你使用 Hash table 時，平均來說，你找到資料是 O(1)，這個比用 Array 的 O(n) 來的快，也比用 Binary search (Olog(n)) 的方式要來的快．

閱讀全文

#10 資料結構 List

List 一般稱為 Linked List，這樣稱呼是因為在 List 裡面的每個元素都是一個連結連到下一個元素，這也稱為單向的 Linked List，如下圖所示：

這種單向的 List 應用在許多的情況下，例如作業系統的檔案寫入到硬碟時所採用的方式就是這樣單向 List 的概念．每個 List 都是由一個或多個元素所組成，而每個元素都有相同的資料結構，以上圖為例，元素裡包含了一個 decimal 和一個 pointer，這個指標所代表的是下一個元素的記憶體位址．所以，如果你要找 List 裡一共有多少元素時，就必須要從第一個元素一直移動到最後一個元素才能得知這個 List 一共有多少的元素．如果要尋找 List 中是不是有某一個元存在，唯一的方法也是得從第一個元素開始，然後沿著 pointer 到下一個元素一直找到最後．以上的動作若用 Big O 來表達都是 O(n)，其中 n 是元素的個數．

顯然跟 Array 比起來，List 在數元素的個數和尋找元素都慢了許多，但 List 也有其優點，由於 List 裡的元素之間是透過 pointer 來指向下一個元素的位址，所以下一個元素的位址可以隨意變更．也就是說當你想要插入或刪除一個元素到 List，這動作就變得相當有簡單．

上圖就是一個刪除元素的結果，只要把 pointer 指向到下下一個元素時，略過中間那一個元素就可以了，最後記得把中間元素從記憶體中釋放即可．其程式碼看起來如下：

nextNode = currentNode.next;
currentNode.next = currentNode.next.next;
free(nextNode);

如果新加入一個元素的話，其程式碼看起來如下：

ListNode newNode = new ListNode();
newNode.next = currentNode.next;
currentNode.next = newNode;

以上兩段程式碼中的 next 就是 pointer 所指向下一個元素的記憶體位址．由於 List 中的元素在實體的記憶體或硬碟空間中不需要相鄰在一起，因此讓插入元素和刪除元素的動作變得簡單．

閱讀全文

#9 Binary search 的 Big O ?

這是一個相當有趣的題目，前面講了 Binary search，因為它利用資料已排序好的特性，所以每次在尋找時可以中候選資料的中間切入來尋找，所以它的 Big O 該如何評估呢 ?

我們之前講到，如果現在找資料的方法是一個一個找，也就是說有十個資料時，最多要找十次，有十萬個資料時，最多要找十萬次，因此我們知道這方法和輸入的資料量成正比，所以是 O(n)．

Binary search 的 Big O 顯然一定比 O(n) 要快，那到底有多快呢 ? 我們可以來觀察一下．每次 binary search 在進行尋找時會從候選資料的中間尋找，然後依照目標值的大小來決定下一次尋找的候選資料是在前面一半還是後面一半，所以每次尋找後都可以將一半的資料給排除，比如說一開始有 100 個資料，經過第一次尋找後，下一回的候選資料就變成 50 個，再下一個就變成 25 個，以此類推．用數學的角度來看就形成了 2^y = n，其中 n 是資料輸入量，而 y 是尋找的次數，把式子轉變一下就形成了 y = log(n) ，其中這個 log 不是以 10 為基底，是以 2 為基底．所以，Binary search 的 Big O 就是 O(log(n))．

未來，寫程式的時候，如果你發現你的資料已排序好，那就記得多利用 Binary search 來做資料尋找，而不要一個一個找．因此，你也知道 O(log(n)) 的程式是比 O(n) 的程式還要來的快．

一般來說，寫 Binary search 有兩種寫法，一種是 recursive，另一種是 iterative.

Recursive :
          bool BSearch(int[] A, int target, int start, int end)
         {
             if (start < end) return false;
             int mid = (start + end) / 2;
             if (A[mid] == target)
                 return true;
             else if (target > A[mid])
                 return BSearch(A, target, mid + 1, end);
             else
                 return BSearch(A, target, start, mid - 1);
         }

Iterative :
         bool BSearch(int[] A, int target)
         {
             int start = 0;
             int end = A.Length - 1;
             while (start < end)
             {
                 int mid = (start + end) / 2;
                 if (A[mid] == target)
                     return true;
                 else if (target > A[mid])
                     start = mid + 1;
                 else
                     end = mid - 1;
             }
             return false;
         }

在沒有其他特別條件限制的情況下，Iterative 的寫法比較容易懂也比較好維護，同時也能避免 stack overflow (未來文章會再介紹) 的問題，所以多建議使用 Iterative 的寫法．

閱讀全文

#8 如何快速搜尋資料 - Binary Search

在以前還沒念電腦科學之前，對於快速搜尋這件事情完全沒什麼概念，唯一知道就是在一堆資料裡面一個一個找了，對於沒念過電腦科學的人來說，一個一個找是最直覺也是最簡單的方法．想像一個情況，一個 Array 裡面有一百個整數，假設每一個整數的值都不一樣，那麼我們想要知道這個 Array 裡面有沒有 77 這個數字，最直接的方法就是從 Array 的第一個元素找到最後一個元素，最好的情況是 77 這數字剛好在 Array 的第一個位置，那麼很快就可以找到了，若最壞的情況是 77 落在 Array 的最後一個位置或是 77 根本不在這裡面，那麼我們就必須從第一個元素找到最後一個元素．從我們之前講的 Big O 來看，這樣的搜尋所花的時間複雜度是 O(n)．這樣的情況有沒有可能更有效率呢?

如果我們今天很幸運得到一個已經排序好的 Array，那麼我們還需要從第一個找到最後一個嗎? 看來不一定喔! 想一想，如果是一個已經排序好的 Array，我們要從什麼地方開始找會比較好 ? 看看下圖的 Array，如果你要找 77 的話，你打算要怎麼找才能快一點．

在電腦科學的基礎課程中提供了一個簡單的方法，簡單的說就是用二分法來找，也就是 binary search．這個方法很簡單，一開始先從中間的位置開始找，以上圖的例子來看，中間是 55，如果我們要找 77 ，我們就知道 77 一定會在後面，不會在前面，原因就是這些元素都已經從小到大排序好了．接著，再用相同的方法，把後面的內容 (64,77,82,97) 再從中間找，而上述的例子剛好就找到了 77，所以一下子就找到了目標.

Binary search 是一個很簡單的概念，也是許多搜尋技術最基礎的想法．當我們再在一堆資料裡面去找某一個特定目標時，如果這一堆資料沒有特別的分類方法時，則很難產生出一個有效率的尋找過程，但如果這一堆資料經過了特別的分類方法，則就有機會產生出一個有效率的尋找過程．以 Binary search 來說，把資料排序好就是這個分類方法，而每次從中間元素開始找就是依這個分類方法而提出的有效率的尋找過程．

如果把層次拉到資料庫的產品，資料庫會有一堆的資料，而資料庫可以建立 B-tree，然後透過這個 B-tree 來尋找資料，所以資料庫引擎才能快速找到目標資料．B-tree 就是上述所說的分類方法，而在 B-tree 上游走就是上述的有效率的尋找過程．

如果把層次拉到像 Google 那樣的搜尋引擎，他們一定有很多的伺服器做索引之用，然後這些伺服器可以為同一個使用者要求來服務，所以當你輸入某個關鍵字時，才能如此快速得到結果，只不過這種層次的分類方法和有效率的尋找過程都是相當複雜的分散式程式．

閱讀全文

#7 系統上線了，我需要拿掉資料庫裡 foreign key 嗎?

前面講了一些基礎的內容，這篇文章來談談一些較實務面的經驗．

還記得許多年前在台北工作的時候，曾經在工作上發生一個經驗，當時我負責幫一個公司做一個小系統．這是一個簡單的小型商業系統，是一個 web application，在前端的部份分成兩項專案，其中一個專案是供給客戶登入各式各樣的資料，另一個專案是供管理者登入做資料的驗證與管理，而後端的部份是一個資料庫．在這個小專案裡，我負責前端客戶登入資料以及資料庫的設計，而管理者資料管理的部份是由該公司的工程師負責．

當整個專案在進行到後期的階段時，工程師們便開始為各項功能做驗證．在當時我並不清楚他們工程師負責的部份寫的如何，但是有件事情我倒是記得很清楚．某一天下午，該公司的工程師不知遇上了什麼技術上的問題，結果他們的主管就跑來找我，一付倚老賣老的姿態來跟我說話．這位主管說，我們過去做案子的情況都是這樣，當系統準備上線時都會把 foreign key 拿掉，以減少程式的執行時發生錯誤．老實說，我當時聽了他的說明，他只是要告訴我移除 foreign key 好讓他們那部份的程式不會出錯．當時我也沒深究他們工程師的程式是怎麼寫的，只是覺得奇怪．但畢竟那是他們的專案，既然他們都這樣要求了，所以就把資料庫裡相關的 foreign key 都移除了．

現在看看，你們公司是不是也會這樣呢 ? 是什麼原因造成你們會決定拿掉 foreign key 呢 ? Foreign Key 是維持資料一致性的其中一個方法，拿掉有什麼好處呢 ? 對資料庫引擎來說倒是變的比較輕鬆，因為某個欄位上如果有 foreign key 的限制，每當該欄位的資料在被修改時，資料庫引擎都得去檢查 foreign key 對應回去的那一個表格是不是有合法的資料存在．如果資料不存在的話，資料庫引擎就必須產生錯誤訊息．因為資料庫引擎做的事變少了，因此完成指令的時間將會變快，這樣聽起來好像蠻不賴的．但如果這麼不賴的話，何必要有 foreign key 的存在呢 ? 前面曾提到，foreign key 是維持資料一致性的其中一個方法．如果你把 foreign key 拿掉了，也就代表資料庫引擎不會為你檢查資料是否合法，所以如果程式撰寫或是邏輯上處理有問題時，就很容易造成幽靈資料．所謂的幽靈資料就是在 foreign key 的欄位上的資料在對應的 primary key 欄位上沒有這樣的資料，因此當你要做 table join 時，那些資料便不會被 join 起來．用一個簡單的例子來看: 資料庫中有兩個表格，第一個表格是客戶表格，第二個表格是訂單表格．客戶表格的 primary key 是 Customer ID，訂單表格的 primary key 是 Order ID，而這兩個表格有一個關聯就是透過 Customer ID 形成的，因此訂單表格的 Customer ID 就是客戶表格 Customer ID 的 foreign key．

Customer ID	Customer Name
A1	客戶一
A2	客戶二

Order ID	Customer ID
O1	A1
O2	A3

如果今天把這訂單表格 Customer ID 的 foreign key 拿掉之後，那就表示當你在新增或更新訂單表格時，Customer ID 並不會受到客戶表格的 Customer ID 所限制，因此就合法可以出現 A3 的客戶編號在訂單表格裡，但麻煩的是客戶表格裡沒有 A3 編號存在，所以訂單編號 O2 就變成了所謂的幽靈資料．

當然，以上是很簡單的例子，你覺得不可能發生，但如果專案夠大，開發的工程師比較多而且整個團隊沒有一個有紀律的開發方法時，當你把資料庫的 foreign key 拿掉，那麼發生幽靈資料的機率便會很高．這時候影嚮的可是整個專案的品質，甚至會影響到客戶的信任度．所以，到底該不該把 foreign key 拿掉，我能給的建議就是，應該是去查看為何程式會出錯，而不該把錯怪在 foreign key 上．只要 database schema 的設計是合理的，foreign key 就不應該出錯，而是程式的邏輯有問題．因此，我還是建議你別拿掉 foreign key，因為我覺得資料庫裡的資料一致性比拿掉 foreign key 所獲得的效能提升還來的重要．

閱讀全文

#6 資料結構 - Stack - part 2

承接上一篇的內容，我們要用什麼方式來做 Stack 的 "容器" 呢? 我們前面提過 Array 和 List，你覺得那一個用來做為 Stack 的容器比較適當?

我們在前面談過 Array 和 List，兩者最大的差異在於物件位於記憶體上的位置是緊連在一起還是允許分散的．如果緊連在一起，則讀取速度快，如果是分散的，則讀取速度慢．光是這一點，我想 Array 就足夠成為我們做為 Stack 容器的人選了．接下來我們用一個簡單的模型來談如何用 Array 做 Stack 的容器．

上圖是一個 Array，這裡頭一開始宣告了 5 個空間，所以可以放 5 個物件，然後有一個變數用來記錄目前最新儲存物件的位置，在上圖用箭頭來表示它，所以一開始並不會有箭頭出現，因為一開始 Array 都是空的．當使用者呼叫 Stack 的 push() 時，就會寫入一個物件，此時箭頭沒有出現，所以這個物件就被放在編號 0 的位置，同時箭號也會出現在這個位置上．接著更多的物件會再進來，於是就往 Array 空的位置上放，但要照順序放，也就是編號 0 放完，就換到編號 1，同時箭頭也更新到編號 1 的位置．

如果使用者呼叫了 Stack 的 pop()，則 Stack 只要將箭頭所在位置的物件回傳出去，然後箭頭往左邊移動就行了，也無需刪除該物件，若有新物件再進來時，那位置上的舊物件就會被覆寫．

透過這樣的方式，你就可以簡單地實做了一個 Stack，透過一個容器和一個箭頭就能達成讓先進來的物件最後才被讀出．

接下來你可能會問一個問題，如果 Array 滿了怎麼處理? 你可以有兩個選擇，第一是丟出錯誤訊息說容器滿了，裝不下新東西了，第二個選擇是再建立更大的容器好應付更多的物件．第二點就和之前談過的 ArrayList 蠻相近的，當 Array 滿的時候，就要建立更大的 Array 或是更多新的 Array，然後再把新進來的物件放到新Array中．

由於宣告一個新的且更大的 Array 並且再把舊 Array 上的元素搬到新的 Array 上，這其實算是個蠻費力的工作，所以我們總不希望這樣的事情常常發生，因此，一開始的 Array 或許不會太大，但我們再建立新的 Array 時，我們可以建大一點．比如說，一開始 Array 長度像上圖一樣是 5，當這個 Array 滿了需要建立新的 Array 時，我們可以建立長度 15 的 Array，如果再滿了，則可以建立長度 45 的 Array．所以你可以看到要建立新的 Array 時，新的長度一定要比原長度還要再多 2 倍以上．因為我們也不知道使用者最後到底要多大的 Stack 來裝他的物件，因此這種循序漸進的變大方式對電腦效能的衝擊會小一點．

所以，當你有機會需要做類似 "undo" 功能的時候，記得用 Stack，比較方便也比較好懂，對後面維護的人來說也易於了解．

閱讀全文

#5 資料結構 - Stack - part 1

還記得以前工作時曾有個一個經驗．有一天，我到同事的辦公室閒聊，聊著聊著他就跟我說他正在做一個新功能，當時我們正在做 Windows desktop應用程式，在這個程式裡面有一個編輯功能的頁面，讓使用者可以輸入產品的許多資料，而我同事正在做的就是為每個編輯動作留下記錄，好讓他可以做出 "undo" 的功能，而且要能一直 "undo" 下去．接著，他展現給我看他的成果，一切都運作的蠻好．接著，我就很好奇問他程式碼是怎麼寫的，接著他就展示相關的程式碼給我，他用了一個 .Net 的 DataTable，然後在這個 DataTable 裡建立了相關的欄位，如動作的序號，資料名稱，資料內容．因此，只要使用者一變動了某一個資料後，這個 DataTable 裡就會多了一筆資料，當使用者執行 "undo" 時，就會從這個 DataTable 裡尋找最大的序號，讀出該序號的資料並且更新 UI，然後將這筆資料從 DataTable 中刪除．如果這是你要做的功能，你會怎樣做呢？

聽完他的解釋之後，我滿臉的疑問馬上問他，你做了這麼多東西，你不覺得累嗎？ 你為什麼不用 Stack 呢? 你知道什麼是 Stack 吧! (因為他是數學系畢業的，我怕他不知道什麼是 Stack) 其實，我倒也不怎麼在乎他如何去實做這功能，只是想到未來有一天我和他都會離開這份工作，總有一天這些程式碼都會交給後面的人繼續開發和維護，我常在想如何未來的工程師們看到這樣的實作方式，不知道他們容不容易懂．

其實，像這樣的功能很常遇到，用 Stack 就對了．人們常說 "凡走過必留下痕跡"，而在軟體世界裡，用 Stack 來留下痕跡就相對地輕鬆．為什麼比較輕鬆呢？ 原因很簡單，抽象上來說 Stack 只提供兩種方法，一個是 push (放物件進去)，另一個 pop (把物件拿出來)，而最後放進去的物件將會是第一個被拿出來的．以上述我那位同事的例子來說，如果他用 Stack，那麼他根本不用去管理序號，也不用在 DataTable 裡去尋找最大的序號，也不用做讀出來的資料在 DataTable 裡刪除，因為 Stack 都幫他做了這些工作．

如果你的工作是程式設計相關，我相信你一定知道什麼是 Stack，這一個基本的資料結構在各大平台與作業系統中都會提供，當然在 java 和 .net 平台也有．接下來，我們討論一下 Stack 是什麼做的? 如果你沒看過 Stack 的實做，先思考一下，如果今天你的工作是寫出一個 Stack，你打算怎麼做呢? Stack 最基本的要求就是可以寫入物件，也可以讀出物件，但是物件的寫入讀取順序一定要按照先進後出，也就是後進先出的方式來進行．因此，我們首先可以想像的是 Stack 一定像是一個容器一樣，因為它要可以容納物件，同時還要有一個管理的機制，好讓先寫入的物件在讀取出會被優先讀出去．如果你能想到這樣，就差不多完成了一半的思考.

待續...

閱讀全文

#4 自己設計的 database schema 是不是好的呢 ?

 前面的幾篇文章都講了些較基礎也較偏向課本的內容，在這篇裡面我們來談談比較實務的題目，那就是你怎麼知道你設計的 database schema 是不是好的?

如果你的工作是軟體專案的成員，這題目一定早就會在你心裡了．市面上的軟體專案有很大的部份都需要資料庫，用來儲存企業內所需的資料，而幾乎大部份市面上的專案所需要的資料庫都是關聯式資料模型 (Relational Database)，因此 database schema 的設計便是整個專案內容的設計中其中一個項目，也就是你要了解什麼是 ERM (Entity Relationship Model)．也許你之前念過一些課本的內容或是上過一些課，但若沒有真正自己參與設計的話，有時你心裡一定會覺得我這樣的設計是不是好的呢?

這篇文章的內容不是要教你如何設計 database schema，其實你只要遵循著課本裡面所教你的原則來設計，設計出來的結果就不會有太意外的錯誤．比如，你知道什麼是 Entity 和 Relationship，相信你一定知道如何把 Entity 轉成資料庫中的表格以及如何用表格和欄位來實現 Relationship．我的看法是只要你正確地遵守了這些原則並且嚴格確保了正規化 (Normalization) 的存在 (一般業界的軟體專案所做的正規化至少要到 3rd normal form)，設計出來的 database schema 應該都可以有八十分．以上是從資料庫的角度來看 schema 的設計，而接下來的二十分，我們就要從程式與效能的角度來思考．

在專案一開始的時候，很有可能資料庫的設計已經完成了，但是程式架構尚未完成，所以 database schema 的設計是否適當，這很難決定，畢竟存取資料的不是人，而是工程師們寫的程式，而資料存取會不會快，那就要看工程師們是怎麼寫程式了．所以你會發現，一個好的 database schema 很難在一開始就完成，除非那是個很簡單又單純的專案．

通常來說，你所設計的 database schema 能不能是個很好的設計，最大的影響是程式讀取的快慢，我們暫不考慮產品與硬體的影響，通常來說，當你的 schema 裡有很多的表格，程式在讀取資料時常常需要 join 很多的表格，這將會大大影響效能，因為 table join 雖然在關聯式資料庫中是一個很平常的事情，但也是一項成本高的運算．因此，你可以思考改進的第一個方向就是如何在不違背 ERM 和 Normalization 的原則之下將會被做 table join 的資料庫表格的數量降到最低．未來的內容，我們再來討論為何 table join 是一個成本高的運算．

第二個可以參考的方向是 Index，不論是做 table join 還是單純在一個表格上尋找資料，如果事先做好了 Index ，它將會幫助資料庫引擎能夠更快速的找到資料，因此就能更快速地完成 table join 或其他的資料存取動作．我們也會在未來的內容裡來說明 Index 如何幫上忙．

最後還有一點 De-normalization (反正規化)．相信大家在課本上或實務上都會聽過這個名詞，據說它的做法能夠提升效能，但在電腦的世界裡是沒有白吃的午餐．以我個人的經驗而言，其實我不是很喜歡這東西，重點不是簡不簡單或難不難，而是它會改變了一些基本的思考而造成系統後續維護的問題. 我舉一個很簡單的例子，比如你有一個資料庫系統，裡面有一個表格，這個表格很簡單，只有兩個欄位，一個是 user id，另一個是 function id，如下所示:

User ID	Function ID
User A	Func A
User A	Func B
User B	Func A

想像這是一個很長的表格，它記錄了那些使用者可以使用那些功能．現在的情況是大部份的使用者都可以使用所有的功能，所以你可以想像使用者多功能多時，這表格有很多的筆數．你的老闆說這表格實在太長了，管理起來真麻煩，於是他想要弄一個東西，也就是如果某個使用者可以使用全部的功能的話，那麼就用 * 來代表所有的功能．

User ID	Function ID
User A	Func A
User A	Func B
User B	Func A
User C	*

如上面表格所示，這代表 User C 可以使用所有的功能，這就是一種 De-normalization 的結果，如果你經驗不多，可能會一時覺得好像很方便，因為表格的資料筆數可以減少，同時要讀取 User C 的功能數量時也很變快，因為只有一筆資料．但你想想，你願意配合做這樣的改變嗎 ? 如果你是軟體工程師，你可能會不太高興，因為你會發現必須要寫一些 "特別" 的程式碼來處理 *．更慘的是，如果這些都是前人的工作，沒人告訴你什麼是 *，你可能要花點時間才能搞懂它的目的．

我在這裡要說的重點是並非所有的 De-normalization 都是好的，這樣的做法的確對資料庫引擎是有益的，因為資料讀取的成本變少了，但卻在程式邏輯上增加了更多的程式碼來處理．這樣一來一回的情況下很難評估是不是真的有好處．以整個系統的角度來看，除非你真的感受到很多的好處，不然就無需 De-normalization 了．

閱讀全文

#3 我需要懂資料結構嗎 ?

如果你的工作是系統管理或是網路工程領域，那麼資料結構可能對你不會有太大的影響，如果你的工作是程式設計或資料庫方面的領域，那麼資料結構對你將會是很重要的主題．若你的工作是程式設計類或資料庫類，即便你沒念過書本上的內容，我相信你對資料結構也有基本的認識．資料結構可以說是整個電腦科學裡相當基礎的知識，如果你把電腦科學用國中國小數學來比喻的話，則資料結構就像小學的四則運算一樣的基礎，必須要了解它才能通往更高級的方程式．

以目前的電腦架構來看，你可以把CPU視為一個做運算的單位，比如做加法運算或除法運算等等，而記憶體和硬碟的空間就像是一條有限長度的磁帶，你可以將資料寫在這條磁帶上，而記憶體這條磁帶比較短，但它讀取寫入速度較快，硬碟這條磁帶比較長，它讀取寫入速度較慢，所以當 CPU 運算時所需要的資料都是在記憶體和硬碟這兩條磁碟裡．接下來，當 CPU在運行時，要透過什麼規則來讀取寫入以及運算資料，那就會因為不同的程式應用而不同，所以在電腦科學裡就會因為不同的應用而定義出適合的資料結構．因此，簡單的來說，資料結構就是定義資料該如何儲存，該如何讀取，以及如何運算．

不論是那一種電腦系統，運行在該電腦上的作業系統一定都會提供一些基本的資料結構，例如 Array, Stack, Queue, List等等，而每個資料結構都有個自的特色以及運用的時機和技巧．比如，Array 的特色就是它的元素在記憶體空間中需要連在一起，也就是只要找到了 Array 的開始位置後，找第一個元素和找最後一個元素所需的時間都是一樣的，因為 Array 裡面的元素都是同一種 data type，所以每個元素在記憶體所佔的大小也都相同，因此很簡單就可以算的出來．List 跟 Array 在這方面剛好就有點不同，List 裡面的每個元素也都是一樣，但它並不需要把每個元素把放在記憶體中連續的空間，List 的元素可以東放一個，西放一個，在儲存位置的選擇上比較有彈性空間，也正是因為這樣的彈性空間，所以每個元素裡面需要有一個特別的位置 (我們稱它為pointer)，用來記錄下一個元素的位置在那裡，透過 pointer，我們才能從第一個元素一直走到最後一個元素，所以當你要存取 List 裡面某一個元素時，它的位置就不能像 Array 是用算出來，而必須從第一個元素開始走，一直走到你要的元素為止，所以每個元素的尋找時間是不一樣的．

接下來你可能會問，Array 和 List 看起來有點像，其實又不太一樣，我們該怎麼知道什麼情況下要用那一種呢? 這是一個很好的問題，有時很難給出很好的答案，但基本上我能給的答案是，如果你知道你所需要的元素個數，那麼你就用 Array，因為 Array 一開始必須要宣告它裡面能裝幾個元素，若情況剛好相反，你不確定你要裝多少個元素，而且存取元素的時間也不是你所在意的，那麼用 List 就提供了一些彈性．

如果你曾用過 java 或 .net 平台提供的 ArrayList，你可能曾想過這到底是 Array 還是 List 呢? 簡單地說，它是長的像 List 的 Array，本質上它還是 Array，但也提供了一些 List 的存取方式讓你來寫入或讀取裡面的元素．同時，它加上了改變 Array 長度的功能，也就是說你一直新增元素進去的話，那勢必會塞滿原有的 Array，所以若要再裝進更多的元素，則需要改變 Array 的長度．但是 Array 一旦宣告了之後就不能改變長度，所以有兩個可能的解決方法．
第一，宣告一個更長 Array，然後把原有 Array 的元素放到新的 Array 上，此時新的 Array 就有更多空間可以裝新的元素，然後把原有的 Array 從記憶體中釋放．
第二，宣告另一個一樣長度的 Array 來裝新的元素．此時就要做一些管理的動作，這樣 ArrayList 來讀取寫入資料時，才知道那一個 Array 是第一個，那一個 Array 是第二個．
可能還會有其他的方法，總之都是在做類似 Array 管理的動作，主要就是解決 Array 長度的問題．

未來文章再機會來談談這些基本的資料結構.

閱讀全文

#2 BIG O - 有關程式執行的快慢 - Optimization

從上一次寫的文章中可以看到如何辦別一個程式執行的好壞，那些都是相當基本而簡單的例子，但在工作中時，我們需要利用這技巧嗎? 答案當然是 YES，但在一般業界中 BIG O 的評估，有時並不是那麼單純，因為我們都習慣用了其他公司寫好的 framework 來進行我們的程式撰寫，比如用 Java platform 或 .Net platform ，所以一個 API 內部會如何執行，我們看不到原始碼就不太能準確知道，所以這一部份只能靠著多使用這些 framework 所得的經驗來知道那一個 API 比較好．

比如，前一篇文章曾講到 string1.Contains(string2)，要寫 Contains() 可以很簡單，你可以把 string 看成是一個 array，在這個 array 裡的元素就是字串裡的每個字母，而今天你要在這字串裡面尋找是否包含另一個子字串時，最簡單的方法就是寫 2 個 loops，外面的 loop 是用來記錄目前比對的位置，裡面的 loop 是用來比較 string1 從記錄點開始有沒有跟 string2 一樣的字元．以 Contains() 的角度來看，我們在評估 BIG O 時只看輸入參數的影響，所以我們不會去管 string1 的長短，在 string1 一樣的情況下，去看 string2 從很短到很長時對執行步驟的變化．這個是最簡單的寫法，難道你認為你用的 framework 就一定這樣寫嗎? 那可不一定. 這些產品工程師們總是有可能想到更好的寫法，所以有時候若有機會去看看這些 framework 的原始碼時，相信會對於你寫程式的功力將大有幫助.

BIG O 談的是輸入參數變化量對程式本身影響的一個趨勢，在業界中，當然會利用這個技巧來討論，除此之外，在業界中還更需要做一些 optimization. 什麼是 optimization 呢? 簡單的說，就是去掉一些沒有用的執行. 讓我們來看上一篇 FindSum4() 的例子.

bool FindSum4(int[] ary, int target) {
    for (int i = 0; i < ary.length ; i++) {
        for ( int j = 0 ; j < ary.length ; j++) {
            if ( i != j ) 
            {
                int sum = ary[i] + ary[j];
                if ( sum == target ) {
                    return true;
                }
            }
        }
    }
    return false;
}

你看看上面寫的例子還有沒有可以改進的地方呢? 可以改進的地方就是有些運算其實是重覆了．其實重覆的地方很多，比如 i = 0 , j = 1 和 j = 0 , i = 1 的運算是一樣的，因為都是抓 ary 的第一個元素和第二個元素來做加法運算. 所以你可以看到 loop 的次數其實可以不用跑那麼多次的，我們只要改一下

bool FindSum4(int[] ary, int target) {
    for (int i = 0; i < ary.length ; i++) {
        for ( int j = i + 1 ; j < ary.length ; j++) {
            if ( i != j ) 
            {
                int sum = ary[i] + ary[j];
                if ( sum == target ) {
                    return true;
                }
            }
        }
    }
    return false;
}

把第二個 loop 的 j = 0 改成 j = i + 1，這樣就大大減少了 loop 內容執行的次數了，而且 if ( i != j ) 還是多餘的．雖然這不一定是最完美的 optimization，但相信你抓住我所要講的重點，那就是去除掉一些重覆的執行動作，雖然以上的兩個程式的 BIG O 都是一樣的，但在工作時，我們還是會要求工程師要做優良的 optimization. 畢竟你輸入的 ary 不可能是無窮大，電腦記憶體是有限的，所以做優良的 optimization 的確是可以幫助你讓程式別重覆做同樣的動作．

話說回來，那像 FindSum4() 是不是還有更好的寫法呢? 答案是有的，以後在適當的內容時會再說明．

閱讀全文

#1 BIG O - 有關程式執行的快慢

如果前面的文章所提，在十多年前時我還沒有電腦科學的基礎知識，在當時很難辦別自己寫的程式是不是好的，後來念書了之後才知道原來在課本裡有一些理論的方法來讓你做評估，而這篇文章的主題就是要來談這項評估.  評估的方法不只一種，而且還有一些數學推論，不過我將會儘量跳過數學推論的部份，而且只談論業界中最流行的一種評估方法，它叫做 O (我們將它念成 big O).

O 的數學基礎是你的程式所需執行的時間會因為輸入參數的不同而有所變化，比如你有一個程式要算1+2+3+4+5的答案，若你懂基本的程式，你就知道輸入參數是5，然後寫一個 loop 來做 5 次的加法就可以得到最後的答案. 一旦你的輸入參數是 10，那麼你寫的那個 loop 的內容就會執行十次.

int answer=0;
for (int i = 1; i <= n ; i++ ) {
     answer += i;
}

所以以上的程式就可以用一個數學的多項式來表達所需要執行的步驟. 以此例子來說是 f(n) = n ，所以 n = 5 時，程式要做 5 次加法, n=10 時，程式要做 10次加法. 如果以 n為x軸，以加法次數為y軸時，你就可以為這程式畫出一條線. O 的方法就是找一個比你的程式 f(n) 還要高一點的g(n)，所謂高一點就是從 x,y軸的位置來看，所以我們稱g(n)為f(n)的上限，講白話一點就是不會超過g(n)，所以g(n)可以視為程式在執行時最費時的情況，不會再比它更慘了，所以才叫做上限. 然後當輸入參數漸漸變大，就會發現g(n)和f(n)會越來越接近.

因此，O就是找出上述的 g(n).

所以，我們在評估程式時很難去用執行時間來評估，因為不同的電腦架構和程式語言都會影響，我們也不會用程式寫了幾行來評估，而是用上述的方法來評估.

在課本上，我們稱它為時間複雜度 (Time Complexity)，在業界中最常用 O 來表達，所以當你使用一些業界的 SDK 時，有時你會看到某個 API 是多少的 O，比如O(n), O(n²)等等.

以上是比較偏向用數學的角度來解釋，接下來我們用更簡單的方法來說明找出一個程式的 O.

int FindSum2(int n) {
    int answer = 0;
    int n = n + 1;
    for( int i = 1; i <= n ; i++) {
        answer = answer + i;
    }
    return answer;
}

上面這一個 FindSum2() 跟上面的程式幾乎一樣，只是有一個小小的變化，在 for 之前多了一個 n = n +1; 所以你可以看到當你輸入 n = 0 時，會執行一次的加法, n=1時，會執行二次加法，以此類推，當 n 越來越大時，加法執行的次數就是 n+1. 所以這個程式就是 O(n+1)，通常我們會忽略掉一些舉無輕重的執行次數，因為當你的 n 變的很大很大的時候，後面那一個 +1 似乎就變的相當不起眼，因此我們會直接說 O(n).

寫程式有趣的地方就是在這裡，因為當程式的輸入參數很小時，程式都能表現的很好，但程式寫的好不好就看它在輸入參數很大時的表現了. 相信大家在業界工作時，在許多項目都會有這樣的感覺，就像網路上只有十台電腦時，網路速度還蠻快的，但變成一百台電腦時，事情就不一樣了.

另外，我們再來看一個例子

int FindSum3(int n) {
    int answer = 0;
    for( int i = 0 ; i < 10 ; i++ ) {
        answer = answer + 2;
    }
    for( int i = 1; i <= n ; i++) {
        answer = answer + i;
    }
    return answer;
}

上面的 FindSum3() 和 FindSum2() 相差了一個 for loop. 我們可以用上述的觀念做找出 FindSum3() 的 O. 你認為是多少呢?

是的，他們兩個是一樣的! 也許你會說這兩個明明是不一樣的，執行的加法次數也不一樣，沒錯，他們執行的加法次數的確不一樣，誠如之前所說，一旦 n 變的很大時，其實也可以說是一樣的，比如執行十億次的加法和執行十億又十次的加法所需的時間，你覺得你會在乎那十次嗎? 我想你比較在乎十億次才對. 所以，到這裡你就可以知道 O 所要表達的並不是一個精確數字的情況，它所要表達的是一個趨勢.

我們再來看看另外一個例子.

bool FindSum4(int[] ary, int target) {
    for (int i = 0; i < ary.length ; i++) {
        for ( int j = 0 ; j < ary.length ; j++) {
            if ( i != j ) 
            {
                int sum = ary[i] + ary[j];
                if ( sum == target ) {
                    return true;
                }
            }
        }
    }
    return false;
}

FindSum4() 輸入參數是一個陣列 ary 和一個數字 target，要來找出陣列裡是否有兩個元素的和等於 target. 猜猜，FindSum4() 的 O 是多少? 記得，在 FindSum4() 中，那一個參數會影響它的執行時間? 沒錯，就是陣列，陣列如果很短，程式執行時間也短，陣列如果很長，執行時間也較長，你看到有兩個 for loop, 而 loop 裡面的內容要執行幾次完全是由陣列的長度所決定 (ary.length)，所以你可以把陣列的長度來做當 n，而 FindSum4() 的 O 是 n². 答對了嗎 ? 所以，如果你可以想到另一種程式寫法只要 O(n)，那麼你的程式在時間複雜度上就打敗了我寫的 FindSum4()，也因為如此，我們才能說你想到的那個程式執行的比我的 FindSum4() 還要快.

以上是我們用加法執行的次數為例子來說明 O，簡單的運算用來表達執行次數是很單純的，所以千萬別以為所有的程式都可以這樣分析，因為你還要確定你所呼叫的每個 API 是不是都像加法那樣單純. 因為現在許多高階的程式語言，像java, C#等，都包裝的很好，有時你並不會看到內部的運作機制，比如 string.Contains() 不像加法那麼單純，其實 Contains() 裡面很可能就會有一個 loop，而且這個 loop 執行的次數會取決於 string 的長短.

希望透過以上這些簡單的例子能讓你了解怎麼以時間複雜度的角度來看程式執行的好壞，同時也了解基本的 O，以及推論出 O 的函數值.

閱讀全文

#0 寫在最前面 - 網誌的內容與目的

我還記得很多年前在台北工作的時候，台灣的資訊業界和電子產業比起來算是較小的，但儘管如此，仍是會有許多機會遇到許多非電腦科系畢業的朋友在資訊業界中工作，比如，我曾遇過財經科系畢業的朋友從事網路工程的工作，或是其他理工科系的朋友從事程式撰寫的工作，甚至包括我自己也是. 我大學是念機械系，但進入社會後卻從沒有做過機械業的工作，而我所從事的全部都是資訊業中的工作.

因為有著不同的背景，後來才又跑回學校重拾課本，把許多該有的基本知識學了起來，能像我這樣做的朋友畢竟算是少數，所以這個網誌的目的就是把我過往的經驗寫下來，專門寫給非電腦科系畢業而在資訊業界中工作的朋友們. 電腦領域裡有許多的科目，我也不是全部都懂，所以往後的內容只著重在資訊業界中比較常會遇到情況，而這些情況的確是需要有念過課本裡所提供的知識才能清楚明白的. 這是什麼意思呢 ? 來舉一個例子，相信許多人都用過資料庫的產品，不論是那一種資料庫產品，它們一定都會提供一個功能，叫Index search，也就是說當你所設計的 table 針對某些資料欄位建立起 Index 之後，這會幫助你所下的 search query 可以更快的找到資料. 我相信若你有過一些資料庫的經驗的話，你一定知道這件事情，但是對於非電腦科系畢業的朋友們來說，我們可能就不知道為什麼可以讓資料尋找變快了，因為這是一般的產品文件裡不會提到的概念. 而在這個網誌的內容裡就會以簡單的描述來說明資料庫是如何達成的.

所以，當你看到這裡之後，你就比較能夠明白這網誌的目的了. 接下來，可能有人會問為什麼要寫這些內容呢? 就如同一開始說過的，在我過往的經驗發現在資訊業工作的非主修電腦系的朋友還不算少數，包括我自己也是其中一個，由於我自己的個性是屬於好奇寶寶型，所以喜歡知道許多背後的原因，這也是我後來決定再回去學校重拾課本的原因，也是因為這樣的際遇，所以才打算把這些背後的原因能記錄下來，希望這些能對其他有興趣的朋友提供幫助與參考.

我預計寫的內容將會是一般在資訊業界中常遇到的情況，大致上會包含的範圍有作業系統，程式寫作，資料庫，與分散式系統等相關的內容. 我相信這些內容也符合大多數非電腦科系在資訊業工作中朋友們的領域.

閱讀全文