#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)) 的方式要來的快．

閱讀全文