-
該如何學好 "寫程式" #4. 你的程式夠 "可靠" 嗎?
撐了很久，續篇來了。這次要進階一點，直接從 software engineer (軟體工程師) 的階段開始。 所謂的軟體工程師，我對它的定義是在這個領域已經算是資深人員了。programmer 該作的是把程式寫好，要挑正確的方式及技術寫好你的程式 (如之前幾篇介紹的演算法及資料結構等等)。而軟體工程師呢? 之前介紹的那些已經不夠了，你該好好的安排你的 code 及工具，要能把你的 solution (如會用到的演算法及資料結構)，跟你手上能運用的資源 (如程式語言、開發工具及函式庫) 作最佳化的搭配及整合。因此我認為在這階段的重點有幾個:
- 先成為一個好的 programmer (廢話)
- 程式要有足夠的可靠性 (穩定、沒有BUG、易讀、對於未知問題的防禦能力)
- 要有足夠的系統知識 (比如作業系統/API/系統服務/記憶體管理等等 OS 提供的環境及功能)
- 程式要有好的結構 (正確/優秀的類別設計、好維護、有足夠的擴充及應變能力)
- 要有解決未知問題或是未知 BUG 的能力，有自行學習新知的能力。
試卷 (QUIZ.xml)[copy code]再來代表答案卷的檔案 (PAPER-PERFECT.xml)，這份看來是天才寫的，每一題都答對了... @_@<?xml version="1.0" encoding="utf-8" ?> <quiz> <question score="20"> <body>那一隻熊最勵害?</body> <item correct="false">白熊</item> <item correct="false">黑熊</item> <item correct="false">棕熊</item> <item correct="true">灰熊</item> </question> <question score="40"> <body>誰發現萬有引力?</body> <item correct="false">鼠頓</item> <item correct="true">牛頓</item> <item correct="false">虎頓</item> <item correct="false">兔頓</item> </question> <question score="40"> <body>下列那些東西是可以吃的?</body> <item correct="false">東瓜</item> <item correct="true">西瓜</item> <item correct="true">南瓜</item> <item correct="false">北瓜</item> </question> </quiz>答案卷 (都是正確答案，PAPER-PERFECT.xml)[copy code]<?xml version="1.0" encoding="utf-8" ?> <quiz> <question> <item checked="false" /> <item checked="false" /> <item checked="false" /> <item checked="true" /> </question> <question> <item checked="false" /> <item checked="true" /> <item checked="false" /> <item checked="false" /> </question> <question> <item checked="false" /> <item checked="true" /> <item checked="true" /> <item checked="false" /> </question> </quiz>而我交待的算分規則也很簡單，就一般考試的計算方式: 每題有自己的配分，以複選題來算，答對幾個選項就照比例給分，答錯會倒扣。新人工程師果然好用耐操，不一會就交給我這份 Library 的程式碼:第一版計分程式[copy code]很中規中舉的程式，把天才寫的答案卷 (paper-perfect.xml) 套進去算，也真的拿到滿分，於是工程師就很高興的把程式 shelve 給我... 各位回頭想想上面的問題。這段程式以作業的標準來說勉強及格了。但是以實際系統運作的角度來說有那些缺陷? 原則上程式只要是人寫的都會有 BUG，不過我也是人，沒辦法一眼看穿所有程式的問題... 只能事事抱著懷疑的態度，試一試再說。我不是天才，所以寫不出滿分的答案，我另外準備了一份答案卷 (PAPER-NORMAL1.xml):public static int ComputeQuizScore(XmlDocument quizDoc, XmlDocument paperDoc) { int questionCount = quizDoc.SelectNodes("/quiz/question").Count; int totalScore = 0; for (int questionPos = 0; questionPos < questionCount; questionPos++) { XmlElement quiz_question = quizDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement; XmlElement paper_question = paperDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement; totalScore += ComputeQuestionScore(quiz_question, paper_question); } return totalScore; } public static int ComputeQuestionScore(XmlElement quiz_question, XmlElement paper_question) { int totalScore = 0; int itemCount = quiz_question.SelectNodes("item").Count; // // 題目的配分 // int quiz_score = int.Parse(quiz_question.GetAttribute("score")); // // 答對一個選項的分數 // int item_score = quiz_score / itemCount; for (int itemPos = 0; itemPos < itemCount; itemPos++) { XmlElement quiz_item = quiz_question.SelectNodes("item")[itemPos] as XmlElement; XmlElement paper_item = paper_question.SelectNodes("item")[itemPos] as XmlElement; // // 算成積 // if (quiz_item.GetAttribute("correct") == paper_item.GetAttribute("checked")) { totalScore += item_score; } else { totalScore -= item_score; } } return totalScore; }只答對第一題的答案卷 (PAPER-NORMAL1.xml)[copy code]見鬼了，算出來是 40 分... 蠢才也是有尊嚴的，不用平白無故送我 20 分吧... @_@，我把 BUG 丟回去給工程師，最後他抓出 BUG 在那裡了，第二題第三題我完全沒作答，應該視為放棄才對，結果程式也照規則給我算分... 運氣好多賺了 20 分.. 工程師又改了一版給我，這次加上了放棄此題的判斷 (第八行):<?xml version="1.0" encoding="utf-8" ?> <quiz> <question> <item checked="false" /> <item checked="false" /> <item checked="false" /> <item checked="true" /> </question> <question> <item checked="false" /> <item checked="false" /> <item checked="false" /> <item checked="false" /> </question> <question> <item checked="false" /> <item checked="false" /> <item checked="false" /> <item checked="false" /> </question> </quiz>修正後的程式 #2: 放棄的話不算分[copy code]有了上一次經驗，直覺告訴我我還得再測一測，搞不好還有其它 BUG ... 這次找了丁丁來考試，丁丁果真是個人才，交了一份全都錯的答案卷給我，前兩題放棄，第三題全選錯 (PAPER-NATIVE.xml):public static int ComputeQuestionScore(XmlElement quiz_question, XmlElement paper_question) { int totalScore = 0; int itemCount = quiz_question.SelectNodes("item").Count; // // 如果都沒作答, 此題放棄 // if (paper_question.SelectNodes("item[@checked='true']").Count == 0) return 0; // // 題目的配分 // int quiz_score = int.Parse(quiz_question.GetAttribute("score"));丁丁的答案卷: 倒扣 (PAPER-NATIVE.xml)[copy code]<?xml version="1.0" encoding="utf-8" ?> <quiz> <question> <item checked="false" /> <item checked="false" /> <item checked="false" /> <item checked="false" /> </question> <question> <item checked="false" /> <item checked="false" /> <item checked="false" /> <item checked="false" /> </question> <question> <item checked="true" /> <item checked="false" /> <item checked="false" /> <item checked="true" /> </question> </quiz>果然有柯南的地方就有密室殺人事件... @_@，又被我抓到一個問題。這次得到的總分是 -40，那有人扣到負的? 工程師又被我叫來唸了一頓，這次改了這版程式給我 (第十一行，最低是0分):修正後的程式 #3: 倒扣到0分為止[copy code]"閃開! 讓專業的來..." 哈哈，來看看鄉民... 不，專家該怎麼解決這種問題。怕程式錯就加上一堆檢查就好了。上面舉的例子真的只是 BUG 而以，其它還有更多不可預測的問題，像是題目跟答案卷跟本搭不起來，或是沒有答案卷等等鳥問題都有可能發生。那怎辦? 可憐的工程師被我訓了一頓，只好摸摸鼻子加了一堆令人哭笑不得的 check code, 像這樣:public static int ComputeQuizScore(XmlDocument quizDoc, XmlDocument paperDoc) { int questionCount = quizDoc.SelectNodes("/quiz/question").Count; int totalScore = 0; for (int questionPos = 0; questionPos < questionCount; questionPos++) { XmlElement quiz_question = quizDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement; XmlElement paper_question = paperDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement; totalScore += ComputeQuestionScore(quiz_question, paper_question); } return Math.Max(0, totalScore); }金融業最重視的就是錢了，銀行的程式連一毛錢都不能算錯，而在線上考試的系統也一樣，連一分都不能算錯。只是當你的老闆這樣要求你的時後，你是謹記在心，還是照一般方式寫程式嗎? 還是你有什麼有效的措施可以預防這些問題? 這時才是顯示你專業的地方啊... 套句鄉民的慣用語:多了一堆 CHECK 及印出 DEBUG MESSAGE 的程式碼[copy code]public static int ComputeQuestionScore(XmlElement quiz_question, XmlElement paper_question) { int totalScore = 0; int itemCount = quiz_question.SelectNodes("item").Count; if (quiz_question == null) { throw new Exception("沒有題目卷"); } if (paper_question == null) { throw new Exception("沒有答案卷"); } // // 如果都沒作答, 此題放棄 // if (paper_question.SelectNodes("item[@checked='true']").Count == 0) { Console.WriteLine("偵測到沒作答的答案，此題放棄"); return 0; } // // 確認題目跟答案的選項數目一致 // if (paper_question.SelectNodes("item").Count != quiz_question.SelectNodes("item").Count) { throw new Exception("此題的選項跟題目定義不符合"); }老實說這範例我也寫不下去了，加這麼多 check 是好事，不過事情都有黑暗面，我覺的不妥的地方有幾個:- 可讀性變差 太多的 check / debug code, 完全把正常流程的 code 淹沒了，一眼看去看不出什麼邏輯...
- 效能變差 對我來說，有些問題是輸入造成的 (如沒有給答案卷)，有些是鳥程式自己沒寫好 (如前面的例子)。並不是所有的 check 都需要寫在程式裡。
- 花在寫 check 程式的時間太多 沒錯，寫個程式五分鐘就搞定，寫 check 要多花廿分鐘...
套用 TRACE / ASSERT 的程式碼[copy code]那真的不正常的話會怎樣? 我特地拿掉倒扣扣到 0 分為止的 check, 用新版的 code 執行看看。public static int ComputeQuizScore(XmlDocument quizDoc, XmlDocument paperDoc) { Trace.Assert(quizDoc != null); Trace.Assert(paperDoc != null); Trace.Assert(quizDoc.SelectNodes("/quiz/question").Count == paperDoc.SelectNodes("/quiz/question").Count); int questionCount = quizDoc.SelectNodes("/quiz/question").Count; int totalScore = 0; for (int questionPos = 0; questionPos < questionCount; questionPos++) { XmlElement quiz_question = quizDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement; XmlElement paper_question = paperDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement; totalScore += ComputeQuestionScore(quiz_question, paper_question); } totalScore = Math.Max(0, totalScore); Trace.Assert(totalScore >= 0); return totalScore; } public static int ComputeQuestionScore(XmlElement quiz_question, XmlElement paper_question) { int totalScore = 0; int itemCount = quiz_question.SelectNodes("item").Count; //if (quiz_question == null) //{ // throw new Exception("沒有題目卷"); //} //if (paper_question == null) //{ // throw new Exception("沒有答案卷"); //} //// //// 確認題目跟答案的選項數目一致 //// //if (paper_question.SelectNodes("item").Count != quiz_question.SelectNodes("item").Count) //{ // throw new Exception("此題的選項跟題目定義不符合"); //} Trace.Assert(quiz_question != null); Trace.Assert(paper_question != null); Trace.Assert(paper_question.SelectNodes("item").Count == quiz_question.SelectNodes("item").Count); // // 如果都沒作答, 此題放棄 // if (paper_question.SelectNodes("item[@checked='true']").Count == 0) { //Console.WriteLine("偵測到沒作答的答案，此題放棄"); Trace.WriteLine("偵測到沒作答的答案，此題放棄"); return 0; } // // 題目的配分 // int quiz_score = int.Parse(quiz_question.GetAttribute("score")); // // 答對一個選項的分數 // int item_score = quiz_score / itemCount; for (int itemPos = 0; itemPos < itemCount; itemPos++) { XmlElement quiz_item = quiz_question.SelectNodes("item")[itemPos] as XmlElement; XmlElement paper_item = paper_question.SelectNodes("item")[itemPos] as XmlElement; // // 算成積 // if (quiz_item.GetAttribute("correct") == paper_item.GetAttribute("checked")) { totalScore += item_score; } else { totalScore -= item_score; } } Trace.Assert(totalScore >= (0 - quiz_score)); Trace.Assert(totalScore <= quiz_score); return totalScore; }我特地把之前加的亂七八糟的 check code 用註解留下來，各位可以看看用 TRACE / ASSERT 前後的差別有多少。ASSERT是其中的精華。你可以到處都加上 ASSERT ，來說明你對於程式執行到某個地方的 "假設"。舉例來說，你 "假設" 呼叫你 FUNC 的人一定會傳 quizDoc 跟 paperDoc 給你，你又不想為了它寫一堆 IF ....，你就可以簡單的加上這一行 ASSERT( quizDoc != null), 代表只有 quizDoc 不是 NULL 時才是 "正常" 的。
在 .NET 裡 ASSERT 觸動後就是這個樣子。那 TRACE 呢? 我們進 DEBUG MODE 來看看:
TRACE Message 直接被收到 Visual Studio 的 Output 視窗內。不過在 .NET 環境下，這兩者的行為已經跟書上講的廿年前作法有很多不同了。這些機制仍然可以開關，不過已經不是靠 DEBUG / RELEASE MODE 來切換，而是在 .NET configuration 裡用設定檔的方式來切換。
------------------------------------
果然寫到一半寫不完 @_@，先做個小結。這些技巧都是一般人寫程式不會注意的，然而這些才是你寫的程式品質有沒有比別人好的關鍵，要讓你的程式可靠，做好預防措施是很重要的。你沒有辦法在所有地方都派警衛防守，但是你至少可以張貼警告標示，ASSERT 就是這樣的東西。下一篇會更進一步的以這例子為延申，ASSERT 還有更強大的應用。也許有人看到這裡會想說:
"怎麼跟單元測試有點像? 我們直接用 UnitTest 就好了啊"
沒錯，單元測試其實就是從最基本的 Trace / Assert 衍生出來的，一直到這幾年才成為顯學。後續幾篇也會再對這些議題做討論，敬請期待 :D
-
生產者 vs 消費者 - BlockQueue 實作
過去寫了好幾篇跟執行緒相關的文章，講的都是如何精確控制執行緒的問題。不過實際上有在寫的人就知道，那些只是 "工具"，最重要的還是你該怎樣安排你的程式，讓它能有效率的用到執行緒的好處，那才是重點。大部份能有效利用到多執行緒的程式，大都是大量且獨立的小動作，可以很簡單的撒下去給ThreadPool處理，不過當你的程式沒辦法這樣切，就要想點別的辦法了。
開始看 code 前先講講簡單的概念。這篇要講的是另一種模式: "生產者 v.s. 消費者"。這是個很典型的供需問題，唸過作業系統 (Operation System) 的人應該都被考過這個課題吧 @_@。簡單的說如果你的程式要處理的動作可以分為 "生產者" (產生資料，載入檔案，或是第一階段的運算等等) 及消費者 (匯出資料，或是第二階段的運算等等) 這種模式，而前後兩個階段各自又適合用執行緒來加速的話，那你就值得來研究一下這種模式。第一手資料就是去看看作業系統的書，恐龍書足足有一整章在講，足夠你研究了。本篇重點會擺在怎樣用 C# / .NET 實作的部份。
舉個具體一點的例子，如果你想寫個程式，從網站下載幾百個檔案，同時要把它們壓縮成一個 ZIP 檔，在過去你大概只能全部下載完之後，再開始ZIP的壓縮動作。第一階段都是 IO (網路) bound 的程式，第二階段則是 CPU bound。如果是完全獨立的兩個程式，很適合擺在一起執行，因為它們需要的資源不一樣，不會搶來搶去。但是就敗在他們要處理的資料是卡在一起的。
把這個動作想像成我們有兩組人分別負責下載及壓縮的動作，下載的部份可以多執行緒同時進行沒問題，但是下載好一個檔案，就可以先丟給後面的那組人開始壓縮了，不用等期它人下載完成。如果下載的暫存目錄空間有限，我們甚至可以這樣調整: 當 TEMP 滿了的話，下載動作就暫停，等到 TEMP 裡的東西壓縮好清掉一部份後再繼續。而壓縮的部份則相反，如果 TEMP 已經空了就暫停，等到有東西進來再繼續，直到完成為止。
前後兩階段該如何利用多執行緒，我就跳過去了，過去那幾篇就足以應付。這種模式的關鍵在於前後兩階段的進度該如何平衡。有些範例是有照規矩的把這模式實作出來，不過... 你也知道，看起來就是像作業的那種，完全不像是可以拿來正規的用途。
我認定 "好" 的實作，是像 System.Collections.Generics 之於 DataStructure 那樣，能很漂亮的把細節封裝起來，很容易重複利用的才是我認為好的實作。不能容易的使用，那就只能像作業一樣寫完就丟...。這個問題看過有人用 Semaphore 來做，也是作的很棒，不過我比較推薦的是 QUEUE 的作法。
從上圖來看，生產者跟消費者都很簡單，就是過去講的多執行緒或是執行緒集區就搞定，關鍵在於中間的控制。我的想法是把庫存管理的東西實作成佇列 (QUEUE)，生產者產出的東西就放到 QUEUE，而消費者就去 QUEUE 把東西拿出來。不過現成的 QUEUE 不會告訴你 QUEUE 滿了，QUEUE 空了也只會丟 EXCEPTION 而以。這次我做了個 BlockQueue 就是希望解決這個問題。
我期望這個 QUEUE 能跟一般的 QUEUE 一樣使用，但是要有三個地方不一樣:
- 要設定大小限制，當 QUEUE 達到容量上限時 EnQueue 的動作會被暫停 (Block)，而不是丟出例外。
- QUEUE 已經空了的時後，DeQueue 的動作會被暫停 (Block)，而不是丟出例外。
- 要多個 QUEUE 關機的動作 (SHUTDOWN)，以免生產者都不出貨了，消費者還苦苦的等下去的窘況。
先看看這樣的 QUEUE 我希望它怎麼被使用。看一下簡單的範例程式 (主程式，不包含 BlockQueue):
使用 BlockQueue 來實作的生產者/消費者範例[copy code]1: public static BlockQueue<string> queue = new BlockQueue<string>(10);
2: public static void Main(string[] args)
3: {4: List<Thread> ps = new List<Thread>();
5: List<Thread> cs = new List<Thread>();
6: for (int index = 0; index < 5; index++)
7: {8: Thread t = new Thread(Producer);
9: ps.Add(t);10: t.Start();11: }12: for (int index = 0; index < 10; index++)
13: {14: Thread t = new Thread(Consumer);
15: cs.Add(t);16: t.Start();17: }18: foreach (Thread t in ps)
19: {20: t.Join();21: }22: WriteLine("Producer shutdown.");
23: queue.Shutdown();24: foreach (Thread t in cs)
25: {26: t.Join();27: }28: }29: public static long sn = 0;
30: public static void Producer()
31: {32: for (int count = 0; count < 30; count++)
33: {34: RandomWait();35: string item = string.Format("item:{0}", Interlocked.Increment(ref sn));
36: WriteLine("Produce Item: {0}", item);
37: queue.EnQueue(item);38: }39: WriteLine("Producer Exit");
40: }41: public static void Consumer()
42: {43: try
44: {45: while (true)
46: {47: RandomWait();48: string item = queue.DeQueue();
49: WriteLine("Cust Item: {0}", item);
50: }51: }52: catch
53: {54: WriteLine("Consumer Exit");
55: }56: }57: private static void RandomWait()
58: {59: Random rnd = new Random();
60: Thread.Sleep((int)(rnd.NextDouble() * 300));
61: }62: private static void WriteLine(string patterns, params object[] arguments)
63: {64: Console.WriteLine(string.Format("[#{0:D02}] ", Thread.CurrentThread.ManagedThreadId) + patterns, arguments);
65: }主程式很簡單，你知道怎麼寫多執行緒程式的話那麼一看就懂了。一開始替 Producer / Consumer 各建立三個執行續，而每個 Producer 只作很簡單的事，就是連續生產 30 個字串放到 BlockQueue, 當所有的 Producer thread 都執行完後，會呼叫 queue.Shutdown( ); 通知 QUEUE 已經全部生產完畢。
Consumer 也很簡單，每個 Consumer 只是去 Queue 拿東西出來，顯示在 Console 上。直到 Dequeue 動作失敗，接到 Exception 之後就結束。
要試試生產者/消費者模式的各種狀況，可以試著調整兩者的執行緒數量。舉例來說，調大 Producer 執行緒數量時 (P: 10 / C:5)，結果是這樣:
Producer 的進度大約就是領先 Consumer 的進度 10 筆資料左右，領先的幅度就暫停了，不會無止境的成長下去。證明卡在 QUEUE 內的數量受到控制。接下來再來看看調高 Consumer 的執行緒數量的結果:
好像 iPhone 上市搶購熱潮一樣 @_@，供不應求，Producer 提供的資料馬上被搶走了...。
效果不錯，看來這樣的實作有達成它的目的。最後來看的是 BlockQueue 的程式碼:
BlockQueue<T> 實作的完整程式碼[copy code]1: public class BlockQueue<T>
2: {3: public readonly int SizeLimit = 0;
4: private Queue<T> _inner_queue = null;
5: private ManualResetEvent _enqueue_wait = null;
6: private ManualResetEvent _dequeue_wait = null;
7: public BlockQueue(int sizeLimit)
8: {9: this.SizeLimit = sizeLimit;
10: this._inner_queue = new Queue<T>(this.SizeLimit);
11: this._enqueue_wait = new ManualResetEvent(false);
12: this._dequeue_wait = new ManualResetEvent(false);
13: }14: public void EnQueue(T item)
15: {16: if (this._IsShutdown == true) throw new InvalidCastException("Queue was shutdown. Enqueue was not allowed.");
17: while (true)
18: {19: lock (this._inner_queue)
20: {21: if (this._inner_queue.Count < this.SizeLimit)
22: {23: this._inner_queue.Enqueue(item);
24: this._enqueue_wait.Reset();
25: this._dequeue_wait.Set();
26: break;
27: }28: }29: this._enqueue_wait.WaitOne();
30: }31: }32: public T DeQueue()
33: {34: while (true)
35: {36: if (this._IsShutdown == true)
37: {38: lock (this._inner_queue) return this._inner_queue.Dequeue();
39: }40: lock (this._inner_queue)
41: {42: if (this._inner_queue.Count > 0)
43: {44: T item = this._inner_queue.Dequeue();
45: this._dequeue_wait.Reset();
46: this._enqueue_wait.Set();
47: return item;
48: }49: }50: this._dequeue_wait.WaitOne();
51: }52: }53: private bool _IsShutdown = false;
54: public void Shutdown()
55: {56: this._IsShutdown = true;
57: this._dequeue_wait.Set();
58: }59: }重點只在重新包裝 Queue 的 Enqueue / Dequeue ，及追加的 Shutdown( ) 裡做的執行緒同步機制。在 BlockQueue 尚未 Shutdown 之前，Enqueue / Dequeue 都不會引發 Exception, 取代的是用 ManualResetEvent 的 WaitOne( ) 來暫停這個動作，直到另一端資料準備好為止。
然而當 Shutdown 被呼叫過之後，Queue 就不再接受新的東西被塞進來了，而東西拿光因為不再補貨，所以就維持原本 Queue 的設計扔出 Exception。
其實真的要挖的話，這個 Queue 可以進一步的改善，以資料結構來看，這種有固定 SIZE 上限的 QUEUE，最適合用 CircleQueue 來實作了。有興趣的朋友們可以換上回介紹過的 NGenerics 改看看，我就不再示範了。其實還有其它變型，像是 Priority Queue, 進去跟出來的順序不一定一樣，意思是你地位比較高的話是可以 "插隊" 的，後加入 QUEUE 的物件，可以優先被拿出來。這些機制都是可以進一步改善 "生產者/消費者" 模式的方法，有需要的讀者們可以朝這個方向思考看看!
這篇只是個開始，運用這種機制，可以進一步延伸出 Pipeline 模式 (生產線)，甚至更進一步運用到串流 (Stream) 的應用。運氣好的話下個月應該看的到完整的探討跟解說吧 ...，敬請期待 :D
-
NGenerics - DataStructure / Algorithm Library
其實本來沒打算寫這篇的，不過之前在寫第二篇: [該如何學好 "寫程式" #2. 為什麼 programmer 該學資料結構 ??] 時，寫的太高興，忘了查 System.Collections.Generics.SortedList 的 KEY 能不能重複... 結果貼出來後同事才提醒我，SortedList 的 KEY 一樣得是唯一的... Orz
實在是不想自己再去寫這種資料結構的作業... 一來我寫不會比較好，二來自己寫的沒支援那堆 ICollection, IEnumerable 等 interface 的話，用起來也是很難用... 就到 www.codeplex.com 找了找，沒想到還真的找到一個: NGenerics :D 找到之後才發現挖到寶了，裡面實作的資料結構還真完整，Heap, BinaryTree, CircularQueue, PriorityQueue... 啥的一應俱全，好像看到資料結構課本的解答本一樣 @_@，有興趣研究的人可以抓它的 Source Code 來看..
這套 LIB 的實作範圍很廣，除了我前兩篇介紹很基本的那幾個之外，其它連一些數學的跟圖型，甚至是各種排序法的實作都包含在內。要看介紹就到它的官方網站看吧! 很可惜的是它的文件不像 MSDN 一般，有明確的標示時間複雜度... 不過它有附 Source Code, 拼一點的話還是可以自己看程式... 哈哈 :D
我就拿 NGenerics 來改寫之前我提供的範例程式吧，那個查通訊錄的程式就不用再改寫了，看不大出來效果差在那。我們來改寫複雜一點的，也就是高速公路的例子。
先來看看有什麼東西可以用? NGenerics.DataStructures.General 這個 Namespace 下竟然有現成的 Graph 類別!! 而 NGenerics.Algorithms 下也有現成的 GraphAlgorithm 這演算法的實作... Orz, 裡面提供了三種演算法，光看名字還真搞不懂它是啥... 分別查了一下，是這三個... 找到的都是教授或是考古題之類的網站 ... 咳咳...
- Dijkstras Algorithm (代克思托演算法): ... 這種名字難怪我記不住 @_@，這演算法就是我在第三篇提過比較好的演算法，由起點一路擴散出去的作法。
- Kruskals Algorithm: 這名字大概太難翻了，沒人把它翻成中文的.. 哈哈，這演算法是找出 minimal spanning tree (最小生成樹)，這篇不講教條了，跳過跳過，有興趣自己看 :D
- Prims Algorithm (普林演算法): 這名字好記多了... 一樣是找
最短路逕minimal spanning tree 的演算法
來看看原本我寫了上百行的程式 (請參考上一篇)，用這個 LIB 改寫有多簡單吧! 先來看看建地圖的部份。Graph<T> 的 T 是指圖的節點型別。暫時不管收費站的問題，因為 GRAPH 的模型裡，只有路逕是有成本的，點本身沒有。直接用 string 來識別點 (vertex)，兩個點跟它的距離就當作路段 (edge)。建資料還真有點囉唆，打了不少字:
利用 NGeneric 的 Graph 來建立高速公路的模型[copy code]1: Graph<string> highway = new Graph<string>(false);
2: highway.AddVertex("基金");
3: highway.AddVertex("七堵收費站");
4: highway.AddVertex("汐止系統");
5: // 以下略
6: highway.AddEdge(7: highway.GetVertex("基金"),
8: highway.GetVertex("七堵收費站"),
9: 4.9 - 0);10: highway.AddEdge(11: highway.GetVertex("七堵收費站"),
12: highway.GetVertex("汐止系統"),
13: 10.9 - 4.9);14: // 以下略
都是我一行一行慢慢打的 @_@... 地圖建完後，怎麼找出兩點之間的最短路逕? 只要這段...
找出 [機場端] 到 [基金] 的最短路逕[copy code]1: Graph<string> result = GraphAlgorithms.DijkstrasAlgorithm<string>(
2: highway,3: highway.GetVertex("機場端"));
4: Console.WriteLine(result.GetVertex("基金").Weight);
因為每個路段的 weight 我是填上油錢 (一公里兩塊錢)，所以印出來的就是兩端要花的油錢。那麼被我們忽略掉的收費站怎麼算? 因為圖型的 MODEL 裡，點是沒有 weight 的，因此我們必需把路段改成有方向的，也就是南下及北上分別算不同的路段 (edge), 同時把過路費加到 weight 裡。
這個演算法的實作有個小缺點，它只傳回結果，沒把過程傳回來...，所以我們只能算出要花多少錢，沒有很簡單的方法拿到該怎麼走。不過好在它有附原始碼，需要的人就拿來改一下吧 :D，多傳個 delegate 或是用它定義的 IVisitor 讓它走完所有的點，你就可以取得沿路的資訊了。
這篇主要是介紹這個意外發現的LIB，就不深入的挖這些細節了，有興趣的讀者們可以自己試看看，不難的。見識到這類演算法函式庫的威力了嗎? 用起來一點都不難，不過要知道怎麼用還真的要好好研究一下...。整套 NGenerics 都是這類的東西，有興趣的讀者好好研究吧 :D
-
終於升速了!
都什麼年代了，台北市宣稱光纖覆蓋率要達到八成，結果我家這邊到現在還是沒 FTTB 可以用... 決定把龜了很久的 ADSL 從 2M/256K 升級到 8M/640K ... 上傳速度提升了 2.5 倍，多少應該有快一點吧?
雖然填單變更速率的過程碰到一堆鳥狀況，不過總算升速成功了 :D
特此留念
-
該如何學好 "寫程式" #3. 進階應用 - 資料結構 + 問題分析
接續前文:
這類文章還真不好寫，想了好幾天，才擠的出一篇文章。第一篇已經講了一堆教條了，第二篇也舉了簡單的例子，說明挑對資料結構的重要性，接下來這篇會把主題放在更複雜的例子上，到底那些地方該注重技術，而那些地方該把重點放在基礎的資料結構及演算法身上。 這次不囉唆半天了，先來回顧一下第一篇，我出的題目是這樣: 以台灣高速公路為題 (中山高、北二高、國道二號)，你有辦法寫程式，讓使用者指定起點跟終點的交流道，然後替它找出建議的路線嗎? (把延路經過的交流到跟收費站列出來就好)。 舉這個題目，是怕前面的例子被嫌太簡單，一點都不能符合實際的情況。沒錯，絕大部份的情況都不會像上一篇的範例一樣，放一堆資料在記憶體裡 SEARCH 出來就了事那麼簡單。高速公路的問題核心一樣是在資料結構，不過這次多了必需自己實作的演算法。 跟我一樣五六年級的人，都聽過這句話吧，PASCAL 之父 (Niklaus Wirth) 講的這句名言: "程式 = 資料結構+演算法"，沒錯，這個範例就需要用到這兩種能力才搞的定。依我的看法，解決這問題有三道關卡要闖:- 你該用什麼樣的方式來儲存這樣的地圖資訊? 這裡會用到的知識，是資料結構裡的 GRAPH，典型的方法就是分成點跟線來記錄..
- 你該用什麼樣的演算法，找出你要的最佳路線? 最基本的是要找出所有可走的路線 (走迷宮)，再找出其中最便宜的一條路。
- 你的程式的結構該如何設計? 這部份跟課本比較無關，講的是你對程式語言及可用的函式庫/工具的掌握，還有架構等等。
描述交流道/收費站的 class[copy code]public class Node { public string Name = null; public int TollFee = 0; public List<Link> Links = new List<Link>(); public Node(string name, int tollFee) { this.Name = name; this.TollFee = tollFee; } }描述兩個點之間的路段 (Link) 的 class[copy code]好像沒什麼特別的，每個點除了搭配 List<Link> 來記錄所有經過它的路段 (Node.Links) 之外，也標上了這個點的名字 (Node.Name)，跟過路費 (Node.TollFee)。而每個路段則記錄了它兩個端點 (Link.FromNode, Link.ToNode) 之外，也額外記錄了路段的距離 (Node.Distance)，及它是屬於那一條高速公路的資訊 (Link.Road)。 接下來就要載入資料了。我偷個懶，只記中山高跟北二高新竹以北的部份，還有機場國道。實在是沒力氣把全部的路段打完... 哈哈。資料來源是參考國道高速公路局的網頁。以下是 Map 類別的部份程式碼，及載入部份地圖資訊的程式碼:public class Link { public double Distance = 0D; public Node FromNode = null; public Node ToNode = null; public RoadNameEnum Road; public Link(Node from, Node to, double distance, RoadNameEnum road) { this.FromNode = from; this.ToNode = to; this.Distance = distance; this.Road = road; } public enum RoadNameEnum { Highway1, Highway2, Highway3 } }MAP[copy code]public class Map { private Dictionary<string, Node> _nodes = new Dictionary<string, Node>(); public Map() { // // construct / load map data // this.AddNode("基金", 0); this.AddNode("七堵收費站", 40); this.AddNode("汐止系統", 0); this.AddNode("樹林收費站", 40); // 略 this.AddLink("基金", "七堵收費站", 4.9-0, Link.RoadNameEnum.Highway3); this.AddLink("七堵收費站", "汐止系統", 10.9-4.9, Link.RoadNameEnum.Highway3); // 略 } private void AddNode(string name, int tollFee) { Node n = new Node(name, tollFee); this._nodes.Add(name, n); } private void AddLink(string n1, string n2, double distance, Link.RoadNameEnum road) { Node node1 = this._nodes[n1]; Node node2 = this._nodes[n2]; Link link = new Link(this._nodes[n1], this._nodes[n2], distance, road); node1.Links.Add(link); node2.Links.Add(link); } public Link FindLink(string name1, string name2) { foreach (Link way in this._nodes[name1].Links) { if (way.GetOtherNodeName(name1) == name2) return way; } return null; } }第一步準備動作完成了。接下來就是想辦法在 class Map 裡加上 FindBestWay( ) method, 來找出最佳路線。在這邊先定義一下什麼叫最佳路線。一般不外乎是找最短的路線，或是通過最少的收費站，我們來點實際的，以油價每公升 30 元為例，車子就假設一公升可以跑 15 公里好了，因此每跑一公里要花兩塊錢。最佳路逕就是花的油錢跟過路費最少的為準。沒唸過資料結構的朋友們，現在大概卡住了。該怎樣找出最佳的路逕? 電腦什麼不行，就是計算很快，這種最佳解的問題，通常都可以用暴力法解決。只要把所有的路線找出來，然後找出總花費最便宜的那個路線就好。雖然資料結構的書通常會舉其它更有效率的演算法，其中一個演算法的名字我不記得了，大致的步驟是由起點開始往外擴散，先算走一步可以走到那些點，再往外推，如果到同一點有兩條以上的路線，就保留便宜的那個... 直到推到終點為止。 不過這方法寫起來比較麻煩，我挑另一個簡單一點的 (相對的比較沒效率)，就是搭配 STACK 走迷宮的方法，把所有路線試過一次，找出所有能從起點到終點的路線，再從其中挑出最經濟的。 為什麼我會挑這個? 只是因為它的邏輯比較簡單易懂，畢竟這個程式不是在比賽，要去拼最快的話就不用了.. 哈哈。資料結構在講到 TREE 一定會講到怎麼樣把 TREE 的每個節點都走一次的方法，就是要搭配 STACK，把走過的點都 PUSH 進去，當作麵包屑來用，等走到沒路了就 POP 退回上一步，改走第二個分岔，直到所有的點都走完為止。 接下來就要把 GRAPH 切掉幾條線，把它想像成長的不大整齊的 TREE，就從起點開始走下去。因為 GRAPH 不像 TREE，有可能會走回原點，因此我們在走的過程中需要跳過已經走過的點，免的最後都在兜圈子繞不出去。 這邊我搭配了遞迴 (RECURSIVE) 的方式來簡化問題。其實就邏輯來說，遞迴幾乎可以跟 STACK 劃上等號。因為遞迴的過程中也是有 STACK 在輔助 (就是 CALL STACK)。不過我偏愛 RECURSIVE，因為藉著 CALL STACK 加上 FUNCTION CALL 傳遞的參數，可以自動幫我處理不少 push / pop, 及替每個階段保存暫時的資料，程式看起來會簡單很多。找出最經濟路線的程式碼[copy code]1: private double _cost = 0; 2: private string[] _best_path = null; 3: private Stack<string> _path = null; 4: private void Search(string startName, string endName, double current_cost) 5: { 6: this._path.Push(startName); 7: if (startName == endName) 8: { 9: if (this._cost == 0 || current_cost < this._cost) 10: { 11: this._cost = current_cost; 12: this._best_path = this._path.ToArray(); 13: } 14: this._path.Pop(); 15: return; 16: } 17: foreach (Link way in this._nodes[startName].Links) 18: { 19: string next = way.GetOtherNodeName(startName); 20: if (this._path.Contains(next) == false) 21: { 22: this.Search( 23: next, 24: endName, 25: current_cost + this._nodes[next].TollFee + way.Distance * 3); 26: } 27: } 28: this._path.Pop(); 29: } 30: public string[] FindBestPath(string startName, string endName, out double cost) 31: { 32: try 33: { 34: this._cost = 0; 35: this._path = new Stack<string>(); 36: this.Search(startName, endName, 0); 37: cost = this._cost; 38: return this._best_path; 39: } 40: finally 41: { 42: this._cost = 0; 43: this._path = null; 44: } 45: }先來看看結果。主程式是要找出 "機場端" 跟 "基金" 交流道之間的最經濟路線，看看程式跑出來的結果:
不相信的人就拿紙筆畫一畫算一算吧! 應該是沒算錯啦。這個例子我就不像上一個例子，放上千萬個節點來拼拼看速度到底多快了，因為我沒有現成的資料啊，這東西要產生假資料也麻煩的多，就略過這個步驟了。不過我們倒是可以回過頭來看看，目前這段程式有什麼可以改進的?
首先，在資料數量遽增的情況下，演算法的改善一定是第一要務。你會發現程式碼從五行變成三行，或是從 100ms 進步到 90ms, 這種程度的改善相較之下都是微不足道的，一來這種改善程度通常是固定的，因為演算法沒有變，整體來說可能只是從 100sec 進步到 90sec，我是客戶的話，還不如換顆快一點的 CPU 就好了...。但是演算法的改進，則是讓你迴圈的次數變少，或是比較的次數變少等等，改變幅度通常是以倍數來算，隨便就提升好幾倍的效能。這就不是升級 CPU 可以解決的問題...。還記得上個例子嗎? 從 List 換成 SortedList, 搜尋速度差了 6000 倍... 你要花多少錢才買的到運算速度快 6000 倍的電腦?
除了演算法之外，程式也是有其它地方可以改善的。看到第 20 行程式碼了嗎? 就是找出下一步是不是已經走過了的程式碼:
if (this._path.Contains(next) == false)
其中 _path 是 Stack<string> 物件，養成好習慣，順手查查它的時間複雜度吧，在 MSDN 裡是這麼寫的:
http://msdn.microsoft.com/en-us/library/xeaek790.aspx
This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.
看起來它的效果跟 List 一樣，搜尋都很慢，有幾筆就要比對幾次。還記得上一篇提過什麼方法? 如果排序過的資料，要花的時間是 O(log n), 如果是採用 HashTable 結構的，則只要 O(1)... 再把 MSDN 拿出來翻翻看，發現除了 Dictionary<TKey, TValue> 之外，還有另一個更適合的 HashSet (.NET 3.5 only):
http://msdn.microsoft.com/en-us/library/bb359438.aspx
The HashSet<(Of <(T>)>) class provides high performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order.
The capacity of a HashSet<(Of <(T>)>) object is the number of elements that the object can hold. A HashSet<(Of <(T>)>) object's capacity automatically increases as elements are added to the object.
馬上看一下，新增一筆及找出某一筆需要的時間複雜度:
HashSet<T>.Add( T ):
If Count is less than the capacity of the internal array, this method is an O(1) operation. If the HashSet<(Of <(T>)>) object must be resized, this method becomes an O(n) operation, where n is Count.
HashSet<T>.Contains( T ):
This method is an O(1) operation.
看起來沒什麼好挑的了。把資料塞進去跟找出來的時間都是固定的，當地圖的節點夠多，你要找的目標夠遠，多花一倍的空間另外放一份 HashSet 絕對是值得的。也因為 HashSet 有這樣的特性，因此它特別適合拿來作集合的運算。比如兩堆資料要找出交集 (Intersection)，聯集 (Union) 等等都很方便。既然都講了就順手查看看:
HashSet<T>.IntersectWith(Hash<T>):
If the collection represented by the other parameter is a HashSet<(Of <(T>)>) collection with the same equality comparer as the current HashSet<(Of <(T>)>) object, this method is an O(n) operation. Otherwise, this method is an O(n + m) operation, where n is Count and m is the number of elements in other.
---------------------------
本系列文章 [該如何學好 "寫程式"] 第一部份就先到這裡。在這裡作個小結。既然第一部份我是在探討要成為一個好的 "programmer" 該具備的能力，我自然是把重點放在怎樣把你拿到的需求，忠實且正確的寫成 code 為主。這時邏輯及觀念，還有資料結構等等基礎的知識是我認為的重點。也許有些讀者很不以為然，我猜想的大概會有這幾個理由:
- 我不會這些，程式還不一樣寫的好好的?
- 都什麼年代了，現在講求的是程式架構!
- 物件導向不是都講求封裝? 幹嘛還要去挖這些?
- 現在資料都放資料庫了，還學這幹嘛?
- ...
Search
Facebook Pages
Sponsor Ads
My Popular Repositories
WebServerClock
能透過 Http Response Header (Date) 偵測網站的時鐘, 顯示該網站目前的時間的小工具。 通常在搶購演唱會門票，購物網站限時搶購，或是連續假期訂購車票時，都需要在開放購買的那一秒鐘按下按鈕，此時搭配這個工具就能精準地掌握 server 的時間。
MeetUp.ApiTokenDemo
介紹跨網站傳遞授權資訊時的安全問題，用100行以內的程式示範數位簽章如何解決這個問題。也示範了這樣的技巧能解決那些更複雜的授權問題。有文字版本可以閱讀，也提供介紹的錄影，以及相關的 PPT 跟 source code.
CommunityOpenCampDemo
Microsoft 主辦的社群活動研討會: Community Open Camp，我主講的場次 windows container 範例及投影片內容
SDKDemo
示範 API 與 SDK 之間的版本相容性開發範例。示範的開發過程，採用 git flow 的方式來進行版本控制，也包含了透過單元測試，同時採用舊版的 client 測試新版的 server, 確保 API 升級時的相容性問題。
Course.Microservices.201612
2016/12/15, Microservice Training Course, 企業內訓, 分為四次課程, 每次 3hr, 共計 12 hr