#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 長度的問題．

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

閱讀全文