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

閱讀全文