-
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. 進階應用 - 資料結構 + 問題分析
這類文章還真不好寫，想了好幾天，才擠的出一篇文章。第一篇已經講了一堆教條了，第二篇也舉了簡單的例子，說明挑對資料結構的重要性，接下來這篇會把主題放在更複雜的例子上，到底那些地方該注重技術，而那些地方該把重點放在基礎的資料結構及演算法身上。
-
得獎了 :D~~~
雖然上禮拜就知道了，不過獎品還沒拿到，當然要忍一下再發表... 哈哈!
花了幾個晚上拼了猜數字的程式，運氣不錯，順利拼到冠軍了。除了寫程式，把心得貼到 BLOG 也花了不少時間.. 主要貼的這四篇:
- Thread Sync #1. 概念篇 - 如何化被動為主動?
- Thread Sync #2. 實作篇 - 互相等待的兩個執行緒
- [C#: yield return] #1. How It Work ?
- [C# yield return] #2. 另類的應用 - Thread Sync 替代方案
蠻有意思的比賽。雖然過去也參加過不少比賽，運氣不錯也騙到一些獎品...，不過這次倒是寫的最起勁，因為其它比賽都是 "廠商" 讚助，不是 Microsoft 就是 Cisco ... 都要想儘辦法把他們的技術發揮出來才能得獎，老實說寫起來跟工作差不多，總是要滿足那些 "市場" 的需求。
這次題目老實說很 "不實用"，純粹是比 code 誰寫的又快又好而已，不過還蠻合我胃口的 :D。正好這次碰到誰呼叫誰這種結構上的問題，就是上面四篇文章一直在討論的 GameHost 為主還是 Player 為主的思考方式，解決這問題花的工夫還比較多。想到這兩套解決方式，我覺的收穫是蠻值得的，至少我多學到兩種不同的設計模式。
最後當然要感謝一下主辦人，下班專程騎車過來頒獎... 哈哈，獎品對我還蠻實用的，算是大獎一枚! 正好是我需要的東西，看來可以開始物色新硬碟，還有要準備來更新我的 SERVER 了 :D
-
該如何學好 "寫程式" #2. 為什麼 programmer 該學資料結構 ??
自從貼了上一篇 該如何學好 “寫程式” 一文，原本以為這種老生常談的內容沒什麼人會看，沒想到還有人給我回應.. :D 原來這種文章還是有市場的。接下來這篇，是延續上一篇，來談談要成為合格的 programmer, 我認為應該要俱備的 “內功” 是什麼。上篇我提到，我認知的 programmer，就是要有實作 (CODING) 的能力。要有能力把技術規格 (像是輸入格式，操作介面等等) 具體的寫成可以執行的程式碼。當然是要寫的又快又好，穩定不當機又沒 BUG …。
