#81 出神入化的用介面 第四集 修改共用的介面 part.2

這一篇文章是上一集的延伸，再來說明新版本 interface 的後續實際使用的情況．先將此篇文章要解決問題再描述一次．想像一家公司出版了一套軟體，而這個產品裡包含了許多的元件檔案 (.dll)，而且每一個元件是由不同的團隊產生．每個元件可以有獨立的發行時間，也就是說當 A 團隊要釋出新功能的版本時，他們可以自行釋出．在客戶端裡，可以透過該軟體裡的更新程式來下載並且安裝 A 團隊所製做的新版本元件．由於各元件釋出的時間並非一致，因此元件之間的互動將變得有挑戰性．

A 團隊裡的某些功能是透過 B 團隊的元件所完成的．例如，A 團隊提供的功能裡有一項是計算產品折扣，而這項功能的細節實作者其實是 B 團隊，因此 B 團隊會提供 interface component 給 A 團隊使用，如:



因此，在 A 團隊的程式碼裡，將可能利用下述的程式碼得到實做該介面的物件，然後來進行折扣計算，如:



接著，A, B 團隊從產品經理接收到新需求，他們必須提供一個新的功能 - 回饋金 (cash back)．因此，比較簡單的做法便是將上述的 interface 加以延伸．但如上一集文章所提，B 團隊不能直接改 IProductUtils，所以他們必須要製造一個新的 interface，並且繼承自 IProductUtils．



A 團隊接著將他們的程式碼修改如下:



若 A 團隊用上述的方式更改程式，則有可能發生錯誤．當某個用戶端使用新版的 A 團隊程式而且用了舊版的 B 團隊程式，則執行到上述程式碼時，就會發生 TypeLoadException 的錯誤，因為此時電腦裡是舊版的 B 團隊元件，所以 runtime 看不懂 IProductUtils2，對它而言，這是一個 unknown type．

為了防止上述的錯誤發生，A 團隊必須採用一些方法來辨別 runtime 所載入的是舊版或新版的元件．可能的方法如下:

讓 B 團隊為不同版本的元件使用不同的檔案名稱．如 BContract.1.dll 和 BContract.1.1.dll 等．B 團隊發行新版本時，可將兩個新舊兩版的 contract dll 一起釋出，同時在實做的程式碼裡也會同時實做新舊兩版的 interfaces．所以，A 團隊若用舊版 (BContract.1.dll)，則 A 團隊只會看到 IProductUtil，若用新版 (BContract.1.1.dll)，可看到 IProductUtil 和 IProductUtil2．這樣做的好處是讓新舊兩版的 interface 位於不同的元件裡，當其他團隊取得舊版時，其他團隊只能看到 IProductUtil．使用新版時，則可看到兩個 interfaces．利用實體檔案區別同一個功能的新舊版本．壞處就是可能會造成過多的元件檔案．

讓 B 團隊將新舊版本的 interfaces 寫在同一個元件檔案裡，如 BContact.dll．這樣做將讓 A 團隊無法從元件檔名上知道他們正使用的是新版還是舊版．因此，就必須透過程式碼來解決這問題．A 團隊為了處理新舊兩版的情況，當他們載入 B 團隊的元件時，他們可先嘗試使用 IProductUtil2，若 IProductUtil2 使用時發生 TypeLoadException，則表示 B 團隊的元件是舊版的．此時 A 團隊便可以把回饋金功能的相關 UI 畫面關閉．請參考下列程式碼來看 A 團隊如何使用正確的版本．



透過上述的方式，當 runtime 執行到 line 12 準備進入 TryGetNewVersion() 時，如果此時 A 團隊使用的是舊版 B 團隊元件，則 runtime 便會發生 TypeLoadException 的錯誤，因為 line 28 的 IPorductUtils2 是一個 unknown type，並且此錯誤會在 line 18 被抓住．接著 A 團隊便可以關閉回饋金的相關功能．如果 A 團隊使用新版本，則不會發生 TypeLoadException．只要能順利取得正確的物件就能呼叫 GetCashBack() 來得到回饋金的金額．若用這個方法，則 A 團隊必須使用 B 團隊的新版本元件在他們的編輯環境裡，才不會發生 build fail (unknown type) 的情況．

這一篇文章提到的情境應該不會是大多數人的情境，畢竟同一個軟體產品裡每一個元件可以有不同的釋出時程是很少見的．如果你的工作情況真的有符合這樣的情境，希望這篇文章能給你一種解法來解決這情境的問題．若你的解法不同，也歡迎你分享給我．

Hope it helps,

閱讀全文

#80 寫程式的參考準則 (coding guideline) - C# 篇

曾有一些朋友問我，在微軟公司裡是否有寫程式的準則 (coding guideline)．這件事因不同的團隊而異，大部份的團隊都會依循 MSDN 文件裡的建議，但並非每一個團隊都有文件記錄這些準則．以前我在 Windows 部門裡的某個團隊就正好有文件說明 C# coding guideline．除了 C# coding guideline 以外，還有其他的文件，例如 code review 文件, database 開發文件等等．在這篇文章中，我將從 C# coding guideline 開始寫起．這些 coding guideline 不是什麼秘密，很多都是來自 MSDN 的文件．若你的團隊也需要一份 C# coding guideline, 希望能派的上用場．

1. 在一份 C# 原始碼裡，別有 Tab , space 並存．這一個可以善用 Visual Studio 的編輯器設定幫你解決．一般來說，我們用 space 來取代 tab，例如一個 tab 等於四個 spaces.

2. 一行程式碼的字數通常設定在 120 個字元左右．為了方便閱讀，若有一個 api 有多個參數需要傳入，將多個參數分行排列，如下例


3. 有關設定變數 (variable)，盡可能地將其 scoping 範圍找小一點的．

4. 變數宣告時不一定要馬上給初始值 (initialize)．用到此變數時在給即可．若需要給一個初始值，請給一個有意義的值做為初始值．這邊所謂有意義的初始值不代表該資料結構的預設值．如 int count = 0; ，這是多此一舉的行為．

5. Global field 前面加上 _ ．若是 local variable，則不用．
如 int _memberCount;  
     int memberCount;

6. 相同型別的變數要分行宣告．別擠在一行一起宣告，應分行．如:
int foo;
int bar;
int baz;

7. 對於常數型的變數 (內容不會變動) 記得使用 const 宣告. 如:
private const int _defaultCount = 100;

另外，對於這類常數型變數，最好能加上一個 comment 用來說明為何選用此內容. 如:
// 100 is chosen because of the size limit of the queue
private const int _defaultCount = 100;

8. 對於多個性質相關的常數型變數，可以考慮將他們整合在一個 static class 裡宣告並使用，如:

可改成


9. 用 string.Empty 來取代 ""

10. 用 string.IsNullOrWhiteSpace() 來檢查字串是否為 null 或是空白.

11. 對於一些 “應用值”，不應該 “hard-code”，而是該透過其他較彈性的方式取得 (像 Configuration)．如
網路連線重試次數，timeout 時間, thread 數量, 資料庫連線字串等等

12. 在 if , while , for, foreach, return 前多個空行，以便於閱讀.

13. Class 裡的 method 之間有一個空白行．

14. 若有需要，善用 #region, #endregion 將相關的程式放在同一個區塊裡．同時 #region 之間也該有一個空白行.

15. 善用 IDE 裡的編輯器幫助你處理好空白的事情．如


16. 遇到一些特別情況時，善用 comment 以便未來工作．寫 comment 時不用一行一行寫 (inline)，請在適當地方用一塊區域來說明程式的運作目的．


17. 對於 public method 都該檢查輸入參數是否符合你的預期．如:


18. 該有括號的地方都打上去，別偷懶不打．如:


19. public method, property 等一律使用 PascalCasing ，而非 public 改用 camelCasing. 如:
public int GetMyReward();
public string MyName {get; set;}

private int getMyReward();
private string _myName;

20. 為 variable, property, method, class, interface 取名是件重要的事情．取一個完整的名稱，別用簡稱．如 使用 GetConsoleWindow() 而不用 GetConWin()

21. Namespace 命名以 PascalCasing 方式，名字應以名詞為主．如: System.Security

22. Class 命名以 PascalCasing 方式，名字應以名詞為主，如 StreamReader, DataCollector 等

23. Interface 命名以 PascalCasing 方式，通常在最前面加上 I ，名字應以名詞為主，如 IList, IReadOnlyCollection 等

24. Variable 與 parameter 命名以 camelCasing 方式，名字應以名詞為主，如:
public int ToInt32(string itemValue, int itemCount);

25. Method 命名以 PascalCasing 方式，名字應以動詞為主，如:
ToString(), Write(), ExecuteCommand();

26. Property 命名以 PascalCasing 方式，名字應以名詞為主，如:
public int Length { get; set; }

27. Event 命名以 PascalCasing 方式，名字應以動詞為主，如:
public event EventHandler ObjectChanged;

28. Public field 命名以 PascalCasing 方式，而 private field 以 camelCasing 方式，名字應以名詞為主，如:
public TimeSpan Timeout;
private TimeSpan _firstTimeout;

29. Enum 命名以 PascalCasing 方式，名字應以名詞為主，如:
FileMode
{
Open,
Create,
Append,
}

30. Class 的名字通常和對應的 Interface 名字有關係，如:


31. 大部份的情況下, Enum 最好要加上 None 元素用來代表該 enum 用不到的情況下，並且將它設定為 0．如:


32. Enum 若是 Flags 的屬性，別在名字加上 Flag，可用複數名詞來代表. 如


33. 為了便於閱讀和 code review，將關聯性高的 class 成員寫在相鄰的位置．

34. 一個檔案最好只有一個 class，並且檔案名字與 class 名字一致．若是 nested class 或是一些簡單且臨時在程式間用的 class 除外．

35. 所有的宣告都應加上 public, private, internal．若是只在一個 method 裡使用的臨時變數可以忽略．

36. 在 switch 裡要加上 default: ，即使它的內容是空的，也要加上．

37. 要產生準確的 exception．如，當你檢查參數是否為空時，就該用 ArgumentNullException 而不是用 ArgumentException．

38. 產生 exception 時，要產生有意義且可知道錯誤細節與解決方法的 exception，不該把許多可能會發生錯誤的 code 放在一個 try block 裡，然後只有一個 catch (Exception ex).

39. 當處理商業邏輯時，很可能找不到適合的 exception type，此時應自行建立自訂的 exception．

40. Exception 產生時不應該影響程式的正常流程，並且 exception 產生時需被處理，例如 log．

41. 在 try-catch 裡若使用到一些資源，可在 finally block 裡釋放．如:


42. 在你的程式裡，在最上層 (可能是在 UI 層) 要能抓住所有可能會發生的 exception，做好相對應的處理或畫面顯示，避免程式中斷．

43. 在 catch block 裡應該都為該 exception 做些處理動作，而不是空白 (什麼事都不做)．除非，程式裡已有邏輯在處理那段錯誤，如:


44. 不用重覆拋出 exception．應該加一些錯誤處理機制並且只需要 throw 即可．如:


45. 對於有實做 IDisposable 的 class 應善用 using 來確保資源能適時適當地被釋放．如:


別在 try-finally 裡使用 Dispose，如:


46. 盡可能使用 generic collection 來儲存物件，例如使用 List<T> 而不用 ArrayList．

47. 所有的 public class, property, method 都應該要有 XML 文件註解，如:


48. 有適合的語法糖時就使用，以便於閱讀．如:


49. 在不影響程式邏輯的情況下，應把程式碼編排縮排量減少．如:


50. Public method 的參數應盡量使用 interface，如:


51. 若無特別需求，為每個非同步呼叫加上 ConfigureAwait(false)

52. 若無特別需求，不自行建立 Thead ，一律使用 Task 讓 .NET threadpool 來管理相關資源．

53. 多個 Task 有執行順序時，善用 ContinueWith(), WhenAll(), 或 WhenAny()，而不該用 Task.Delay．

閱讀全文

#79 貪心策略 - Greedy (2)

上一篇文章談了貪心策略的基本想法，但並沒有提到任何的程式碼來說明貪心策略是怎麼進行的．其實貪心策略並沒有一個很明顯程式碼撰寫方式，如果硬是要湊出一個程式碼外型的話，我覺得它的長相可能如下:

while ( 依問題條件來決定是否要繼續下一步 )
{
    // 1. 依照問題，在這一個步驟裡取得最佳解
    // 2. 根據步驟一得到的最佳解來決定程式的下一個狀態
    // 3. 將程式目前的狀態移動到下一個狀態，下一個狀態將會更接近最終的答案
}

老鼠走迷宮是很典型資料結構 Stack 作業，它的內容是假設一個方形的土地，這土地用畫分成許多面積相等的小格子，就像棋盤那樣．每一個格子都是一種地形，如山，河，平地．老鼠只能走平地，不能爬山也不能過河．老鼠將從起點走到終點，起點是在這土地的左上角，而終點是在右下角．這個作業就是要讓老鼠能走出一條路從起點到終點．如果沒有路存在，則最後的答案是 null，若有路存在，則最後的答案是每個格子的座標集合．老鼠走迷宮用貪心策略來展現其演算法，它的程式結構如下:

while ( 老鼠未到達終點 )
{
    1. 在目前格子，依順時鐘順序找到一個可以走的格子，並且這個格子沒走過而且其地形不是山或河
    2. 如果所有可走的格子都已走過或都是山河等地形，則下一個格子是上一個步驟的格子．
    3. 將老鼠移動到下一個格子
}

在老鼠走迷宮的例子中，老鼠在每一個格選擇下一個格子時，此時便是要求一個 “當下” 的最佳解．走過的格子不能走，地形是山或河的格子也不能走，所以只剩下一般的平路．在 “當下” 的情況下，下一個格子是平路的情況可能超過一個方向，此時我們無法得知下一個格子之後的狀態，因此，可以依序或隨機選擇一個格子來走．畢竟都是平路的格子，所以在 “當下” 來說都是最佳解．

誠如上一篇文章所說，這樣的解法通常不會是最佳解．在老鼠走迷宮的問題中，最佳解通常是指最短路徑．如果老鼠走的土地剛好只有一條路可以走的話，那麼用貪心策略寫出來的程式找到的路徑剛好就是最短路徑，因為只有一條而己．但現實中的問題裡，幾乎很難會遇到這種情況．

另外，你也能感受到貪心策略只考慮 “當下” 而己，不會再多考慮下一步，所以你也能看到貪心的策略並不用利用其他的資料結構去記錄一些有關那一條才是最佳路徑的事情．也是因為如此，程式寫起來才比較簡單，因為你只需要用一個 Stack 來記錄走過的格子，而不需要為每一個格子去記錄所有可能的狀態．由此，你也能感受到求最短路徑就不是那麼簡單直覺的事情了．

Hope it helps,

閱讀全文

#78 貪心策略 - Greedy (1)

前面的文章曾提過，在這世界上有很多不同類型的問題，基本上我們太不可能找到一個方法來解決所有的問題．所以，不同類型的問題就會有不同的解法．有的解法很好理解並且單純，有的解法不易理解．解法本身並沒有所謂的好壞，只有適不適合使用的情況．通常來說，難的問題若要有好的執行結果，通常那個解法不見得簡單，就算是簡單，也絕非容易可以想的出來．這也許就是演算法美妙的地方，或許可以說是邏輯之美．廣泛地也可以說成是數學之美，都是宇宙空間裡所擁有的一些特質．

今天要提的解法是一種貪心 (Greedy) 的 “精神”．若你沒念過演算法這門課，恭喜你可以免除這個宇由特質的迫害，可以遠離那種整晚埋頭寫作業的崩潰時光．我想我是比較笨的，所以我以前寫演算法和計算理論的作業時，常常抱著頭在燒．如今，回頭看看，這些都是人生裡蠻有趣且值得回憶的時光．演算法課本裡，前面一半的內容中主要是提到一般市面上對問題的 “解法” 有那些．一個問題可以有多種不同的解法，就像你的工作上要達成某一個任務，可以用不同的技巧或手法來達成該任務．因此，解法可以說是一種邏輯思考的過程，也可以說是一種寫程式的過程．基本上，寫程式就是一種邏輯思考的具體呈現．因此，演算法的課程裡前面一半就是在教你如何 “邏輯思考” 來解決問題，其中最簡單的思考方式就是 "貪心" (Greedy)．

貪心的精神在於在解決問題的過程中選擇一個 "當下" 最好的決定來繼續往下執行程式．這是什麼意思呢 ? 舉一個相當簡單的例子．假設你對台北的街道並不熟悉，而你現在位於台灣大學的校園裡，你接到一個任務是要找出徒步走路到陽明山的路徑．想一想，你會如何思考來解決這個問題呢 ? 別忘了，前提是你對台北的街道並不熟悉，但是你知道陽明山在北邊，因為天氣好時你能看到陽明山．”貪心” 的精神就在於，位於所在位置，在此時那一條路是最好的選擇就走那一條路．由於不熟悉台北街道，你只好依照陽明山的方向前進，可能沿著敦化南北路一直往北走後，結果你發現松山機場卡在前面，不僅如此，機場旁邊還有一條基隆河．只好在機場前做出往右走或往左走的決定，來找到橋讓你渡過基隆河，然後再一直依著陽明山的方向前進．這種邏輯思考就是每走到一個路口，再來決定下一個方向要如何走．如果運氣不好，剛好走到沒有橋能跨越基隆河的路口，那只好再依當下的情況做出最好的決定．往左走或往右走不代表一定會有橋可以過，所以你也可以感受到這種 “貪心” 的解決方法似乎有點風險. 因為 "貪心" 提供的解答通常不會是最好的答案，所謂最好的答案像是最短路徑，最省時的路徑等．除此之外，你也能感受到依照 "貪心" 方法，要寫出這方法的程式還蠻直覺和容易的． 因此，不同方法都有不同的優缺點．要決定用什麼方法之前就必須對你的問題有完整的了解．

再舉另外一個例子，在前面的文章裡曾提到 #48 老鼠走迷宮 ．在這文章所提供的程式碼就是一種 "貪心" 的解法，因為從這一步走到下一步時，只單純考慮是否可以通行，不會考慮其他因素．因此，經由 "貪心" 得到的路徑是一條 "可以走" 的路，但不一定是 "最短" 或 "最省力" 的路．如果你找到的路剛好是最短或最省力，那只是說明你當下的運氣好，並不代表 "貪心" 解法能帶給你最佳值．

你可以想一想，在你的工作中，是不是用了很多 "貪心" 的方式來寫程式呢 ? 我相信大部份朋友們的程式碼一定讓 "貪心" 佔據了大部份，因為 "貪心" 並不需要人類特別去想像才能發明出來的方法，它本身就是最單純的思考方式．如果有一個問題連 "貪心" 都無法解決時，那這問題應該真的可以稱上是超級難題了．

完全沒寫到任何程式碼來解釋 "貪心"，不知道這樣效果如何 ?

Hope it helps,

閱讀全文

#77 部落格的原始動機與人生所需的財務智商

這篇文章來分享二個主題，第一是為何我開始寫這個部落格，第二是人生所需的財務智商．

我在 "大毛電腦科學筆記" 裡從 2015 年 3 月開始寫下第一篇文章到現在已經有三年半的時間了．剛開始的第一年，由於我沒有設計任何的讀者回饋方式，因此第一年並不知道寫的內容是否有用．後來第二年開始加入 Google Form 讓讀者們可以留下回饋資訊，並且也為網站上加入 Google Analytics 用來查看網站的流量資訊．大約一年前成立了 Facebook 社團以及舉辦公益課程來做為另一種推廣此部落格的管道．從去年 (2017) 開始，我陸陸續續收到一些讀者們的回饋，有些是單純地謝謝我寫這些淺顯易懂的內容，也有些是來問我一些工作上的問題．謝謝大家的捧場和問題讓我知道這個部落格已經發揮了一些作用．其實，我最早的想法並不是寫部落格，而是打算把所有的資訊匯集成冊出版用．早在十年前，我收集了以前在台灣和美國念的上課筆記，打算將這些內容寫成書來出版．但可惜，後來因為搬家緣故，那一大本的筆記已下落不明，所以把筆記匯集成書的想法便中斷了．但我並沒有忘記要分享電腦科學的基礎知識這件事．後來心想，匯集成冊需要大量時間並且有出版時程的壓力，於是 2015 年初便改用部落格的方式進行分享．這樣一來，沒有時間壓力，可以一篇一篇慢慢寫．最主要的想法是要將電腦科學裡的基礎知識分享給在資訊界裡非本科系畢業的資訊人．與其說是分享，也可以說是一種對自己人生中某幾段求學和工作過程的記錄．誠如我在 "有關作者" 的頁面裡所寫的，我自己在大學時念的是機械工程，但因緣際會的人生巧合，我轉換跑道到電腦科學，在台灣待過一般的軟體專案公司，然後也在美國待過所謂的大型軟體公司進行軟體產品的開發工作．這一路走來，像我這樣在大學時學非所用然後因好運氣而進入到大公司參與軟體產品開發的人應該是相當少見，也因此更激勵我把許多知識和心得分享出來．一方面希望能幫助或鼓舞其他人，另一方面也為自己的 IT 人生留下一些深刻而明確的記錄．在這三年半的時間裡，記錄了文章大致上有資料結構，資料庫系統，些許的程式設計，以及正在撰寫的演算法．後續的內容還會有更多的程式設計，作業系統，分散式系統，甚至影像處理，人工智慧，以及其他大家有興趣的內容．我自己並未設限要寫到什麼情況下才算結束，就一切隨緣吧! 根據這一年來的網站流量資料，每個月大約有二百個連線拜訪這個部落格，若以網站經營的角度來看，這是一個流量超級低的網站．不過，這部落格不是以營利為出發的網站，除了 domain name 要花些錢註冊以外，其他都是免費資源，因此沒有營利需求．大部份拜訪到此部落格的使用者都是經由 Google search 而來的．這些網路上來的使用者都是經由關鍵字搜尋而找到此部落格，例如搜尋 Heap file, database B-tree 等等．因此，有緣來拜訪此部落格的朋友都會對這裡的文章感到興趣，也是這樣的情況，我才會從去年開始陸續收到網站拜訪者的留言與回饋．若你有任何建議，也別忘了留言告訴我．

之前我曾在 IT人生 的系列文章中提到一個與銀行戶頭有關的文章．簡單地講就是 "錢"．這也是一般年輕人比較容易忽略的事情，但這件事情卻又是如此地重要．對我自己而言，錢能提供的不是成就感，而是一種安全感．在你依照自己的目標追尋自己的成就感時，有點錢在身邊是一種安全的保障，能幫助你應付一些緊急的狀況．也許你可能會覺得找份工資高的工作不就好了，我也希望事情有這麼簡單就好了．以許多進步的國家來看，來自國家所設計的保障在未來都是有倒閉破產的風險，像是台灣的勞工保險 (非勞工退休金)，在未來某一天也會因繳的人少且領的人多而面臨入不敷出的情況，既便是像美國的 Social Security 在未來的十幾二十年後也是會面臨同樣的問題，這樣的問題在許多國家都存在．因此，只想要依靠當初政府所設計的保險制度來領取退休金的人們要小心了，因為錢不一定領的到．我相信大部份的讀者都是二三十歲的人，離退休還有很長的一段路．因此，要讓自己保有良好的 "財務智商" 是相當重要的事情．不論你從事什麼樣的工作或是領多少薪水，財務計畫和規畫是每一個人都不該錯過的課題．自己的退休金最好還是要自己先準備好．所以，我才會特別強調這件事情讓還沒準備的讀者們要想一想這件事．如果你願意花假日的時間去上課學習一些新的軟體產品與開發技術，那何不也花一些時間讓自己學習有關 "錢" 的事情．你花時間學了一個新的產品或技術，頂多只能用個三四年，然後就有新的版本或新的技術需要學習，成本是很高的．若你學習有關 "錢" 的事情，那是一輩子受用的事情，不會有什麼每隔幾年得重新學習的情況．最近，我在 YouTube 上看到兩個年輕的台灣網紅 (柴鼠兄弟)，他們錄製了許多的短片，每一個短片都用淺顯易懂的方式來說明與投資理財有關的內容，這就像我喜歡用淺顯易懂的方式來描述許多電腦科學裡的知識一樣，因此我非常喜歡他們的影片．我強烈建議對 "錢" 還沒什麼概念的讀者們可以看看他們的影片來增加自己的財務智商，為你未來的生活增加財務上的安全感．

Hope it helps,

閱讀全文

#76 演算法裡一個基本的觀念 - Reduction

Reduction 是一個在演算法知識裡基本且簡單的觀念．其實在各位的工作中也一定常用到這觀念，只是你不知道而己．在這文章裡一如往昔，不用學術理論的描述方式，而是用平常寫程式的例子來讓非電腦科系畢業的資訊人了解什麼是 Reduction．

接下來用寫程式的角度來看什麼是 Reduction．假設你需要寫一個影像辨識的程式，這個程式需要辨識一個圖片裡是否含有某個數字，所以你寫的 function 可能會像下列:



以上的程式碼尚未完成，部份內容先暫以文字描述表示．你可能不是一個影像辨識的專家，完全不知道該怎麼做數字辨識．所以你一定會尋找可能的方法來執行這項任務．最後，你找到一個程式可以做這項工作，它的程式碼如下 (數字辨識的內容用文字描述代替):



由於 DetectNumber() 是別人完成的程式，假設你僅知道它是可用的，但無法了解其中的運作內容．你可以將它視為一個黑盒子．至於黑盒子裡面是怎麼運作的，由於能力與知識不及，所以暫時無法了解．但不了解也不代表不能使用，你只要知道這個黑盒子需要的輸入和輸出是什麼資料型別，就可以將它套用到你的程式裡．

接下來，我們將 DetectNumber() 套用到 ContainNumber() 裡面，所以完成後的 ContainNumber() 如下:



如此一來， ContainNumber() 就能做到它需要的功能了．從寫程式的角度來看，你會覺得這不就是每天工作在做的事情嗎 ? 是的，你每天寫程式所做的事情都是讓程式呼叫東呼叫西，在這一連串呼叫的過程完成自己所需要達成的功能．當一個演算法呼叫另外一個演算法來達成某項功能時，這就是一個 Reduction．也就是說，ContainNumber() 要做的事情，其實 DetectNumber() 也能做的到，差別只是輸入輸出的資料型別不同而己．將 ContainNumber() 的輸入型別轉換一下，就能形成 DetectNumber() 的輸入型別，然後將 DetectNumber() 的輸出型別轉換一下，就能變成 ContainNumber() 的輸出型別．再換個角度想，ContainNumber() 和 DetectNumber() 要處理的問題核心其實是同一個，只是問法和要求的答案有點小差別而己．在演算法的世界裡，某些問題的解法能變成另一些問題的解法，靠的就是這種 Reduction 的技巧．只要你能找出問題的本質是一樣時，解法就很接近了．

Hope it helps,

閱讀全文

#75 將問題和演算法分類

學習基礎的演算法過程中，許多課本最常用的方式是將問題分類好，然後對每一類問題進行討論並給出一些著名的演算法來解決這一類的問題．因此，要了解自己面對的問題屬於那一類型的問題便是件重要的課題．在這一系列的文章中，我的目的並不是要告訴你大學課程的演算法內容，而是希望用一種比較實際工作上會遇到的普遍情況來說明在工作中可能會碰到跟演算法課本內容有關係的課題．就像上一篇文章提過的，演算法的內容就像是你寫的程式裡某一個 function，每一個 function 一定有一個特定的目的．因此，你可以想像世界上存在許多的演算法，每一個演算法都有一個目的．當你認識了許多演算法時，有一個簡單的方法來分類演算法的種類，就是按照目的來分類．只要你知道你的問題是屬於那一類，這樣你就知道該去找那一類的演算法．例如，你的工作裡某一個任務需要將資料庫中的訂單做排序，因此，你就可以在市面上找到許多的排序演算法，挑一個適合用在你的工作裡．排序是一個相當簡單的例子，你甚至不用找演算法，因為這類基礎的演算法都已被實做在許多產品裡．另外一個例子，你的工作是做一個檢查文章裡的英文字是否拼錯，如果拼錯的話，必須列出一些建議清單來讓使用者選擇．這一類的演算法通常不會在一般的 class library 裡面內建好，因此你得自行尋找可用的演算法．這類的演算法比較像在算字和字之間的相似度，或稱為字和字之間的距離，如 nprth 是使用者誤打的字，可能正確的字是 north，因為 o , p 在鍵盤位置上就是隔壁而己．有一個演算法能幫你計算字和字之間的距離，請參考 https://en.wikipedia.org/wiki/Levenshtein_distance

透過上述的說明，你可以明白若進入一個自己不懂的領域，要針對該領域的問題找出適合的演算法來解決問題，這是需要花費時間學習．另外還有一個簡單的分類方式是用實做的方法來進行分類．例如，你的工作安排工廠裡產線的機器，每個機器會有不同的維修周期，不同種類的機器也會有不同的處理量，而產線上機器之間的順序是不會變的，就像一定得先把模具做出來，才能做各式機械加工處理，完成後才能噴塗料等等的程序．你老闆希望你能設計一個機器運作方式讓機器運作的情況是最佳的，也就是說產線的產量是最大的．像這樣看起來就是一個 “最佳化” 的問題，在演算法課本裡面會談到許多最佳化的問題．以這問題來說，採用 linear programming (未來文章會介紹) 是一個可能的解法之一．但要注意的是，並不是所有 “最佳化” 的問題都能用 linear programming 來找到最佳值，上述問題的限制給的很多，因此無形中幫你把問題的範圍縮小，解法也相對變簡單．如果問題的限制變少了，如加工製程的順序是不重要的，拿掉就個限制就讓整個問題變得很難用一個簡單的演算法找到最佳解，難的不是找不到答案，而是一旦問題的輸入量變大 (機器變多)，找出解答的時間 (演算法內的步驟) 就會以不成比例的方式往上增加，也就是說演算法的 Big O 變大．用寫程式的角度來看，一旦限制條件變少，程式就必須做更多的步驟來尋找各種可能以得到最佳值，這相當於 for loop 會變多了．Big O 漸漸變大時，此時你就得思考其他的解法方法，如果你的情境不需要最佳解，則採用一些近似解法來尋找接近最佳解的解答，而且通常近似值解法的速度都會比最佳值解法的速度來得快很多．

分類的情況實在太多了，無法一一描述．在這邊希望帶給非電腦科系畢業的資訊人一個觀念就是學習演算法的過程中，要先了解把問題分類，並且也知道一些常見問題分類裡一些著名的演算法．我們不需要發明什麼了不起的演算法，以我個人的經驗是，能夠善用許多聰明人為解決某些問題而想出來的演算法，這就已經夠利害了，同時也能幫助你寫出好程式．畢竟，對非本科畢業的資訊人來說，不是遇到一個不會的問題就用暴力法來解決．即便是一個看似很簡單的工作人員排班表的事情，用暴力法，它的 Big O 可是很大的．又比如你是做地圖導航的工程師，你要安排一個最短路徑從某一個點到另一個點，若沒有好的演算法，你能想像你用暴力法來解決，那將是什麼程度的 Big O 嗎 ?

最後，你可能會問，你明白分類的重要性，則到底有那些分類呢 ? 老實說，我回答不出來有那些分類．通常我的方法是看問題的資料輸入類型和問題的重點來決定．例如，問題是一個最佳化問題，例如找出成績最好的前十名學生，或是訂單金額最高的前十名，資料輸入類型是一個 List 或 Array，一堆資料庫來的訂單或學生清單，而問題的重點是在最佳解，像最大值，最小值，或某些子項目是符合某個條件，這一類的解法通常像之前一些 Coding面試文章的解法那樣．再困難一點，問題是一個觀光路徑排列的問題，資料輸入類型是一個 Tree 或 Graph，像一個地圖，而問題的重點是依照某個條件做排序，例如觀光景點參觀順序從低海拔排到高海拔，此時除了要了解基本的 Tree, Graph 的資料結構運作之外，最後還得讓排序演算法派上用場．不論怎麼分類，其實你都能感受到問題都是傾向某一種 “最佳” 的方向靠近，而且善用好的演算法就是希望結果能快速地被運算出來，也就是 Big O 盡可能低．如果問題不需要傾向某一種 “最佳” 的方向靠近，那麼程式隨便亂寫，最後能跑出答案就行了．

雖然每個演算法都有特定目的用來解決特定問題，不同的問題之間有可能用相同的演算法來解決嗎 ? 答案是有可能的，這是下一篇文章的重點．

Hope it helps,

閱讀全文

#74 演算法從零開始

資料結構和演算法算是最基礎而且重要的知識．若沒有這兩個科目的足夠知識的話是很難在其他電腦科學領域有所進步的，其中也包括程式設計這一條路．基本上來說，程式設計這條路需要強大的邏輯基礎，除了你得對 if .. else .. for loop 用的很熟練外，你還得了解你所用的 SDK, framework 的優缺點，這樣使用起來，你才知道你的 SDK, framework 為你的程式做了什麼事情．除此之外，你便需要知道資料結構和演算法的基本知識，這兩個學科是能幫助你寫出好程式的關鍵．

從前面的文章裡，我談了許多資料結構及其應用，也談了許多面試考題．當你看完那些文章後，你應該能抓到一個重點，這重點就是儘量地省時間 (省運算步驟)，不然的話，就得用空間來換時間 (提高空間複雜度來降低時間複雜度)．雖然每一種問題的情況都不一樣，不見得都能用空間換時間，但至少這是一個讓你思考的方向．演算法在這過程中扮演了重要角色，因為這門學問能幫助你辨別問題，知道什麼樣的問題 “應該” 要用什麼樣的解法．如果沒有好的解法時，也可以得到盡可能好的解法．

你可能會覺得，有這麼神奇嗎? 基本上是的，大學裡學的演算法只是一個開始，並不是包山包海．這門學問可幫助我們辨別問題，同時提供好的解法．許多特定領域的問題，如人工智慧，資料庫等領域，都是需要演算法的基礎知識才能繼續在該領域裡研究和學習．常常也會發現類似的演算法或想法被用在不同的系統中．例如，資料庫常用 B-tree 來幫助快速搜尋資料，相同的做法也能放在作業系統中用來快速尋找檔案．這是典型的用空間換時間的做法，同時也是演算法中 Divide & Conqure 的概念．

說了這一些，到底演算法是什麼 ? 在演算法的課本裡你可以找到正式的學術說明來定義什麼是演算法．以下是我用不學術的方式來簡單定義演算法: 演算法是一連串的運算，這運算會有輸入端 (你的問題)，然後會有輸出端 (問題的答案)．演算法也可以視為一段程式碼，既然是一段程式碼，之前在資料結構裡提到的空間複雜度和時間複雜度也同樣適合在這裡做分析用途．但有一個重點，演算法裡這一連串的運算應該是有盡頭的，也就是能夠跑的完，而不是一直無窮迴圈跑下去．所以，每個演算法的目的就是解決問題 (輸入端)，然後產生解答 (輸出端)．如果用你工作上的專案來看的話，在你程式裡的大部份的 method 都是一個演算法，因為這些 method 都接收輸入然後產生輸出，這些都是在你專案裡用來解決特定的問題或是達成特定的目標．

當你看到這裡時，你可能會認為演算法就像是一般的程式一樣，這樣想也沒什麼不可．但為什麼演算法常給人一種好像是個高深學問或是很難的感覺，我只能說你可能從網路上看到的先進應用都是需要特別的演算法，這些特別演算法不是那麼容易可以想的出來的，自然而然給你一些既定印象認為演算法好像很難．如前面所提的，大學課程裡面教的演算法並非是為了解決特定問題，而是把世界上常見的問題做分類，並且介紹每一個分類裡一些著名的演算法用來解決這些問題．

把這篇文章做為介紹演算法的第一篇文章，正式開啟演算法之路．

閱讀全文

#73 Coding面試 LeetCode#14 Longest Common Prefix

原題目網址是 https://leetcode.com/problems/longest-common-prefix/description/

這一題在 LeetCode 的難易度分類屬於簡單級，題目的意思是你會得到一個 string array，然後你得從這個 string array 裡面找到最長從頭開始的共同子字串．在題目裡有給了簡單的範例，例如 Input: ["flower","flow","flight"] , 則答案就是 "fl"．如果找不到合適的子字串，就直接回傳空字串．同時題目也告訴你，input 字串只有 a 到 z 之間的小寫字母，不會有其他的符號，這個條件大大降低了答案的難易度，因為可以少一些大小寫辦別或特殊字元或文化上的處理．

解法的邏輯也相對單純．找出最短長度的字串，以它為基礎，然後去比對每一字串從頭開始的字母，以此類推做到有一個字母是不符合條件或是最短長度已經到達．

參考的程式碼如下:



這解法的時間複雜度是 O(n²)，空間複雜度是 O(n)．也許有更快速的解法等待你的尋找．

Help it helps,

閱讀全文

#72 一秒38萬個交易的故事 - 資料庫引擎篇

與資料庫有關的文章到目前為止已張貼了二十二篇文章，這些文章所談論的內容大部份都是描述資料庫引擎裡 Storage 和 Transaction 的內容．資料庫引擎裡的內容當然不只這些，還包括 SQL query parser, query optimizer, logging manager, 以及一些基本的功能如 security control 等等．光是有關 storage manager 的故事就能寫一本書了，除非你想做資料庫引擎的專家才需要知道所有的細節，不然的話，只要了解一些基本的設計便能幫助你在工作上做到更好的境界．在這些二十二篇與資料庫引擎有關的文章，我寫的那些內容其實簡化或跳過不少的細節，但那些細節並不會影響你對資料庫引擎設計的了解，只讓你可以用比較高層次的角度來檢視資料庫引擎會為你做的事情．畢竟這些內容主要的對象是給非電腦科系畢業的資訊人所參考用，因此忽略了許多數學上的推導與比較．若你是電腦科系的學生正在學習資料庫理論，請以課本內容為主，因為課本內容裡面會用一些數學來明確表達運作成本等事情．為什麼要說這些呢 ? 這當然是和本篇文章的主題有關，一個一秒38萬個交易的故事．

這句話是去年阿里巴巴在雙十一的購物節活動後，阿里巴巴的大老闆馬雲所講的．他用總交易數量除以總交易時間，得到一個值就是阿里巴巴的系統在購物節活動時能處理一秒三十八萬筆交易．這是一個相當驚人的數字，也證明了阿里巴巴的工程團隊能得到這樣的水準．其實這樣的水準，既便是連 Amazon 也不見得能有這機會達成，畢竟以美國的人口數和使用量，要一秒鐘達成三十八萬交易數量，似乎蠻難的．中國有更龐大的人口再加上雙十一購物節的熱潮，自然而然能在短時間內形成非常高的使用量．反觀台灣呢 ? 若我記憶正確的話，高鐵訂購系統曾因大家搶票而掛了，江蕙退隱歌壇演唱會的訂票系統也曾發生這樣的事．想想台灣人口才多少人，瞬間能產生的使用量一定遠遠不如阿里巴巴遇到的情況，但很可惜系統掛掉的事情仍是發生了．可能的原因大概有兩種，一種是工程人員無法勝任工作，另一種原因是電腦資源不足．不論是那一種原因所產生的結果都是會令人產生負面的印象．

一個能處理一秒三十八萬筆交易的系統是一個龐大的系統，每個部份都有許多故事可以講，接下來的內容只討論一些與資料庫引擎有關的內容．在網路上我曾看過一篇文章談到阿里巴巴的資料庫交易系統裡為效能改進所做的一些事情，其中最讓我印象深刻的事情是預先建立訂單資料．以資料庫引擎的角度來看，預先建立訂單資料等於把所需要的 page 先建立完成，因此在系統運行的過程中，不會有 page split 的事情產生．請參考之前的文章

• http://www.woolycsnote.tw/2015/07/19-page.html
  
• http://www.woolycsnote.tw/2015/08/21.html
  
• http://www.woolycsnote.tw/2015/08/22-page-3.html
  
• http://www.woolycsnote.tw/2016/04/45-page-fill-factor.html
  

以上這幾篇文章與 page 有關，看完後，你便能了解為何 page split 是件大事，並且也能了解預先建立訂單資料就相當預先把這些 page 都建立完成．等系統運行時，資料庫引擎便不需要在當下建立這些 page，而是直接使用這些 page．簡單的說就是不用做 insert table, 只要 update table 即可．

除此之外，把 foreign key 拿掉也是件對效能有幫助的事情．因為把 foreign key 拿掉就等於讓資料庫引擎不用去檢查 foreign key 對應 primary key 的正確性，也就是讓資料庫引擎少做事情．但這樣做有某種程度的風險，請記得要搭配一些必要的配套措施．這方面的內容請參考之前的文章 http://www.woolycsnote.tw/2015/04/7-foreign-key.html

另外還有一個比較常用的技巧是將 database schema 做 de-normalization 的處理．如果你的程式需要做很多的 table join 時，你得好好考慮 de-normalization 這件事．平常使用量不高時，table join 也許不會造成你太大的影響，一旦使用量一高時，table join 將是個高成本的動作．所以在特別的情況下，將資料做 de-normalization 減少 table join 這能讓資料庫引擎少做許多事情．這方面的內容請參考之前的文章

• http://www.woolycsnote.tw/2018/03/68-table-join.html
  
• http://www.woolycsnote.tw/2018/04/69-table-join.html
  

當整個系統過了尖峰時刻後，再將結果的資料回復到 normalization 的情況下即可．

如果為了特別的目的而需要讓資料庫引擎少做一些事情以讓它達到最大效能的運行情況，都需要進行一些特別處理，上面所講的都是不錯的特別處理，可以有效讓資料庫引擎少做一些事讓它達到盡可能好的運行效能．當然可行的方法不只是這些，還有許多其他從資料角度或硬體角度來思考的方法．這篇文章的主要目的就是幫助大家明白在做這些特別處理的事情時背後所用的原理 (原因) 是什麼，讓你有足夠強大的理由相信這樣做的確是有幫助的，這也是這個部落格的目的．

Hope it helps,

閱讀全文