1. 生產者 vs 消費者 - BlockQueue 實作

    過去寫了好幾篇跟執行緒相關的文章,講的都是如何精確控制執行緒的問題。不過實際上有在寫的人就知道,那些只是 "工具",最重要的還是你該怎樣安排你的程式,讓它能有效率的用到執行緒的好處,那才是重點。大部份能有效利用到多執行緒的程式,大都是大量且獨立的小動作,可以很簡單的撒下去給ThreadPool處理,不過當你的程式沒辦法這樣切,就要想點別的辦法了。

     

    開始看 code 前先講講簡單的概念。這篇要講的是另一種模式: "生產者 v.s. 消費者"。這是個很典型的供需問題,唸過作業系統 (Operation System) 的人應該都被考過這個課題吧 @_@。簡單的說如果你的程式要處理的動作可以分為 "生產者" (產生資料,載入檔案,或是第一階段的運算等等) 及消費者 (匯出資料,或是第二階段的運算等等) 這種模式,而前後兩個階段各自又適合用執行緒來加速的話,那你就值得來研究一下這種模式。第一手資料就是去看看作業系統的書,恐龍書足足有一整章在講,足夠你研究了。本篇重點會擺在怎樣用 C# / .NET 實作的部份。

     

    舉個具體一點的例子,如果你想寫個程式,從網站下載幾百個檔案,同時要把它們壓縮成一個 ZIP 檔,在過去你大概只能全部下載完之後,再開始ZIP的壓縮動作。第一階段都是 IO (網路) bound 的程式,第二階段則是 CPU bound。如果是完全獨立的兩個程式,很適合擺在一起執行,因為它們需要的資源不一樣,不會搶來搶去。但是就敗在他們要處理的資料是卡在一起的。

     

    把這個動作想像成我們有兩組人分別負責下載及壓縮的動作,下載的部份可以多執行緒同時進行沒問題,但是下載好一個檔案,就可以先丟給後面的那組人開始壓縮了,不用等期它人下載完成。如果下載的暫存目錄空間有限,我們甚至可以這樣調整: 當 TEMP 滿了的話,下載動作就暫停,等到 TEMP 裡的東西壓縮好清掉一部份後再繼續。而壓縮的部份則相反,如果 TEMP 已經空了就暫停,等到有東西進來再繼續,直到完成為止。

     

    image

    前後兩階段該如何利用多執行緒,我就跳過去了,過去那幾篇就足以應付。這種模式的關鍵在於前後兩階段的進度該如何平衡。有些範例是有照規矩的把這模式實作出來,不過... 你也知道,看起來就是像作業的那種,完全不像是可以拿來正規的用途。

     

    我認定 "好" 的實作,是像 System.Collections.Generics 之於 DataStructure 那樣,能很漂亮的把細節封裝起來,很容易重複利用的才是我認為好的實作。不能容易的使用,那就只能像作業一樣寫完就丟...。這個問題看過有人用 Semaphore 來做,也是作的很棒,不過我比較推薦的是 QUEUE 的作法。

     

    從上圖來看,生產者跟消費者都很簡單,就是過去講的多執行緒或是執行緒集區就搞定,關鍵在於中間的控制。我的想法是把庫存管理的東西實作成佇列 (QUEUE),生產者產出的東西就放到 QUEUE,而消費者就去 QUEUE 把東西拿出來。不過現成的 QUEUE 不會告訴你 QUEUE 滿了,QUEUE 空了也只會丟 EXCEPTION 而以。這次我做了個 BlockQueue 就是希望解決這個問題。

     

    我期望這個 QUEUE 能跟一般的 QUEUE 一樣使用,但是要有三個地方不一樣:

    1. 要設定大小限制,當 QUEUE 達到容量上限時 EnQueue 的動作會被暫停 (Block),而不是丟出例外。
    2. QUEUE 已經空了的時後,DeQueue 的動作會被暫停 (Block),而不是丟出例外。
    3. 要多個 QUEUE 關機的動作 (SHUTDOWN),以免生產者都不出貨了,消費者還苦苦的等下去的窘況。

     

    先看看這樣的 QUEUE 我希望它怎麼被使用。看一下簡單的範例程式 (主程式,不包含 BlockQueue):

    使用 BlockQueue 來實作的生產者/消費者範例[copy code]
            public static BlockQueue<string> queue = new BlockQueue<string>(10);        public static void Main(string[] args)        {            List<Thread> ps = new List<Thread>();            List<Thread> cs = new List<Thread>();            for (int index = 0; index < 5; index++)            {                Thread t = new Thread(Producer);                ps.Add(t);                t.Start();            }            for (int index = 0; index < 10; index++)            {                Thread t = new Thread(Consumer);                cs.Add(t);                t.Start();            }            foreach (Thread t in ps)            {                t.Join();            }            WriteLine("Producer shutdown.");            queue.Shutdown();            foreach (Thread t in cs)            {                t.Join();            }        }        public static long sn = 0;        public static void Producer()        {            for (int count = 0; count < 30; count++)            {                RandomWait();                string item = string.Format("item:{0}", Interlocked.Increment(ref sn));                WriteLine("Produce Item: {0}", item);                queue.EnQueue(item);            }            WriteLine("Producer Exit");        }        public static void Consumer()        {            try            {                while (true)                {                    RandomWait();                    string item = queue.DeQueue();                    WriteLine("Cust Item: {0}", item);                }            }            catch            {                WriteLine("Consumer Exit");            }        }        private static void RandomWait()        {            Random rnd = new Random();            Thread.Sleep((int)(rnd.NextDouble() * 300));        }        private static void WriteLine(string patterns, params object[] arguments)        {            Console.WriteLine(string.Format("[#{0:D02}] ", Thread.CurrentThread.ManagedThreadId) + patterns, arguments);        }
    
       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),結果是這樣:

    image

    Producer 的進度大約就是領先 Consumer 的進度 10 筆資料左右,領先的幅度就暫停了,不會無止境的成長下去。證明卡在 QUEUE 內的數量受到控制。接下來再來看看調高 Consumer 的執行緒數量的結果:

    image

    好像 iPhone 上市搶購熱潮一樣 @_@,供不應求,Producer 提供的資料馬上被搶走了...。

     

    效果不錯,看來這樣的實作有達成它的目的。最後來看的是 BlockQueue 的程式碼:

     

    BlockQueue<T> 實作的完整程式碼[copy code]
        public class BlockQueue<T>    {        public readonly int SizeLimit = 0;        private Queue<T> _inner_queue = null;        private ManualResetEvent _enqueue_wait = null;        private ManualResetEvent _dequeue_wait = null;        public BlockQueue(int sizeLimit)        {            this.SizeLimit = sizeLimit;            this._inner_queue = new Queue<T>(this.SizeLimit);            this._enqueue_wait = new ManualResetEvent(false);            this._dequeue_wait = new ManualResetEvent(false);        }        public void EnQueue(T item)        {            if (this._IsShutdown == true) throw new InvalidCastException("Queue was shutdown. Enqueue was not allowed.");            while (true)            {                lock (this._inner_queue)                {                    if (this._inner_queue.Count < this.SizeLimit)                    {                        this._inner_queue.Enqueue(item);                        this._enqueue_wait.Reset();                        this._dequeue_wait.Set();                        break;                    }                }                this._enqueue_wait.WaitOne();            }        }        public T DeQueue()        {            while (true)            {                if (this._IsShutdown == true)                {                    lock (this._inner_queue) return this._inner_queue.Dequeue();                }                lock (this._inner_queue)                {                    if (this._inner_queue.Count > 0)                    {                        T item = this._inner_queue.Dequeue();                        this._dequeue_wait.Reset();                        this._enqueue_wait.Set();                        return item;                    }                }                this._dequeue_wait.WaitOne();            }        }        private bool _IsShutdown = false;        public void Shutdown()        {            this._IsShutdown = true;            this._dequeue_wait.Set();        }    }
    
       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

    2008/10/18 系列文章: 多執行緒的處理技巧 .NET C# 作品集 作業系統 多執行緒 專欄 技術隨筆 有的沒的 物件導向

  2. 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, 裡面提供了三種演算法,光看名字還真搞不懂它是啥... 分別查了一下,是這三個... 找到的都是教授或是考古題之類的網站 ... 咳咳...

    1. Dijkstras Algorithm (代克思托演算法): ... 這種名字難怪我記不住 @_@,這演算法就是我在第三篇提過比較好的演算法,由起點一路擴散出去的作法。
    2. Kruskals Algorithm: 這名字大概太難翻了,沒人把它翻成中文的.. 哈哈,這演算法是找出 minimal spanning tree (最小生成樹),這篇不講教條了,跳過跳過,有興趣自己看 :D
    3. Prims Algorithm (普林演算法): 這名字好記多了... 一樣是找最短路逕 minimal spanning tree 的演算法

    來看看原本我寫了上百行的程式 (請參考上一篇),用這個 LIB 改寫有多簡單吧! 先來看看建地圖的部份。Graph<T> 的 T 是指圖的節點型別。暫時不管收費站的問題,因為 GRAPH 的模型裡,只有路逕是有成本的,點本身沒有。直接用 string 來識別點 (vertex),兩個點跟它的距離就當作路段 (edge)。建資料還真有點囉唆,打了不少字:

    利用 NGeneric 的 Graph 來建立高速公路的模型[copy code]
                Graph<string> highway = new Graph<string>(false);            highway.AddVertex("基金");            highway.AddVertex("七堵收費站");            highway.AddVertex("汐止系統");            // 以下略            highway.AddEdge(                highway.GetVertex("基金"),                 highway.GetVertex("七堵收費站"),                4.9 - 0);            highway.AddEdge(                highway.GetVertex("七堵收費站"),                 highway.GetVertex("汐止系統"),                 10.9 - 4.9);            // 以下略
    
       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]
                Graph<string> result = GraphAlgorithms.DijkstrasAlgorithm<string>(                highway,                highway.GetVertex("機場端"));            Console.WriteLine(result.GetVertex("基金").Weight);
    
       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

    2008/10/14 .NET C# MSDN Tips 技術隨筆 有的沒的

  3. 終於升速了!

    都什麼年代了,台北市宣稱光纖覆蓋率要達到八成,結果我家這邊到現在還是沒 FTTB 可以用... 決定把龜了很久的 ADSL 從 2M/256K 升級到 8M/640K ... 上傳速度提升了 2.5 倍,多少應該有快一點吧?

    雖然填單變更速率的過程碰到一堆鳥狀況,不過總算升速成功了 :D

    特此留念

    2008/10/10 敗家 有的沒的

  4. 該如何學好 "寫程式" #3. 進階應用 - 資料結構 + 問題分析

    接續前文:

    1. 該如何學好 "寫程式" ??
    2. 該如何學好 "寫程式" #2. 為什麼 programmer 該學資料結構 ??
    這類文章還真不好寫,想了好幾天,才擠的出一篇文章。第一篇已經講了一堆教條了,第二篇也舉了簡單的例子,說明挑對資料結構的重要性,接下來這篇會把主題放在更複雜的例子上,到底那些地方該注重技術,而那些地方該把重點放在基礎的資料結構及演算法身上。 這次不囉唆半天了,先來回顧一下第一篇,我出的題目是這樣: 以台灣高速公路為題 (中山高、北二高、國道二號),你有辦法寫程式,讓使用者指定起點跟終點的交流道,然後替它找出建議的路線嗎? (把延路經過的交流到跟收費站列出來就好)。 舉這個題目,是怕前面的例子被嫌太簡單,一點都不能符合實際的情況。沒錯,絕大部份的情況都不會像上一篇的範例一樣,放一堆資料在記憶體裡 SEARCH 出來就了事那麼簡單。高速公路的問題核心一樣是在資料結構,不過這次多了必需自己實作的演算法。 跟我一樣五六年級的人,都聽過這句話吧,PASCAL 之父 (Niklaus Wirth) 講的這句名言: "程式 = 資料結構+演算法",沒錯,這個範例就需要用到這兩種能力才搞的定。依我的看法,解決這問題有三道關卡要闖:
    1. 你該用什麼樣的方式來儲存這樣的地圖資訊? 這裡會用到的知識,是資料結構裡的 GRAPH,典型的方法就是分成點跟線來記錄..
    2. 你該用什麼樣的演算法,找出你要的最佳路線? 最基本的是要找出所有可走的路線 (走迷宮),再找出其中最便宜的一條路。
    3. 你的程式的結構該如何設計? 這部份跟課本比較無關,講的是你對程式語言及可用的函式庫/工具的掌握,還有架構等等。
    這三道關卡,要依序破解,前一關的決定會影響到後面的解決方式。先從資料來說,連該怎麼記錄這些資料,就別想解題了。最基本的 GRAPH 需要點 (NODE) 及點跟點之間的連線 (LINK) 組成。很直覺的就可以定出這兩個類別:
    描述交流道/收費站的 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]
    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
        }
    }
     
    好像沒什麼特別的,每個點除了搭配 List<Link> 來記錄所有經過它的路段 (Node.Links) 之外,也標上了這個點的名字 (Node.Name),跟過路費 (Node.TollFee)。而每個路段則記錄了它兩個端點 (Link.FromNode, Link.ToNode) 之外,也額外記錄了路段的距離 (Node.Distance),及它是屬於那一條高速公路的資訊 (Link.Road)。 接下來就要載入資料了。我偷個懶,只記中山高跟北二高新竹以北的部份,還有機場國道。實在是沒力氣把全部的路段打完... 哈哈。資料來源是參考國道高速公路局的網頁。以下是 Map 類別的部份程式碼,及載入部份地圖資訊的程式碼:
    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:  }
    先來看看結果。主程式是要找出 "機場端" 跟 "基金" 交流道之間的最經濟路線,看看程式跑出來的結果:
    image 不相信的人就拿紙筆畫一畫算一算吧! 應該是沒算錯啦。這個例子我就不像上一個例子,放上千萬個節點來拼拼看速度到底多快了,因為我沒有現成的資料啊,這東西要產生假資料也麻煩的多,就略過這個步驟了。不過我們倒是可以回過頭來看看,目前這段程式有什麼可以改進的? 首先,在資料數量遽增的情況下,演算法的改善一定是第一要務。你會發現程式碼從五行變成三行,或是從 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 為主。這時邏輯及觀念,還有資料結構等等基礎的知識是我認為的重點。也許有些讀者很不以為然,我猜想的大概會有這幾個理由:
    • 我不會這些,程式還不一樣寫的好好的?
    • 都什麼年代了,現在講求的是程式架構!
    • 物件導向不是都講求封裝? 幹嘛還要去挖這些?
    • 現在資料都放資料庫了,還學這幹嘛?
    • ...
    其實這些論點也沒錯,不過上一篇可以看到,不懂得這些基礎的話,現成的物件給你挑也不見得知道要挑那一個,更慘的是連之間的差別都不曉得。還有,資料結構通常包含兩個層面,一個是怎麼 "描述" 你的資料? 另一個是怎麼去應用你的資料? 以這題為例,如果你都不曉得要把地圖拆成點跟線來記錄,你會知道 TABLE 該怎麼建嗎? 另外,很多資料庫上面效能的問題,也都跟資料結構有關。就跟上一篇該挑那一種 Collection 一樣,資料庫也可以把它當成一個更巨大,功能更多的 Collection 來看待,因此能不能有效的利用它,資料結構也是很重要的觀念之一。 再來講到架構的部份,我覺的這位網友在他的 blog (我不認得他本人,只是常看他文章) 發表的這兩篇文章很不錯: 1. 程式設計的兩個觀點 (1/2) 2. 程式設計的兩個觀點 (2/2) 他這兩篇講的就是兩個極端,一個講求效率跟演算法,另一個則是講求架構跟程式的美感。而這兩者通常不容易兼顧。以我來說我比較偏後者,效能的部份,我會捨棄一些小地方以換來程式碼的可擴充性,可讀性,架構等等。不過我不會放棄的是資料結構跟演算法的正確性,就如同前面寫的例子一樣,程式碼有沒有最佳化,差的是 xx % 的效能,但是演算法跟資料結構的差距,則是好幾倍。我一向認為不會跑就要學飛,遲早會跌下來的,所以才會寫這三篇針對 programmer 的文章。 接下來,就換到 software engineer 了。這個階段就不只是把程式碼 "寫對" 或是 "寫出來" 而以,而是要開始考慮怎樣才 "寫的好" 了。有興趣的讀者們請耐心等待續集 :D   -- 範例程式下載: Taiwan-Highway.zip

    2008/10/08 系列文章: 如何學好寫程式 .NET C# Tips 作品集 專欄 技術隨筆 有的沒的

  5. 得獎了 :D~~~

     IMG_9142

     

    雖然上禮拜就知道了,不過獎品還沒拿到,當然要忍一下再發表... 哈哈!

    花了幾個晚上拼了猜數字的程式,運氣不錯,順利拼到冠軍了。除了寫程式,把心得貼到 BLOG 也花了不少時間.. 主要貼的這四篇:

    1. Thread Sync #1. 概念篇 - 如何化被動為主動?
    2. Thread Sync #2. 實作篇 - 互相等待的兩個執行緒
    3. [C#: yield return] #1. How It Work ?
    4. [C# yield return] #2. 另類的應用 - Thread Sync 替代方案

     

    蠻有意思的比賽。雖然過去也參加過不少比賽,運氣不錯也騙到一些獎品...,不過這次倒是寫的最起勁,因為其它比賽都是 "廠商" 讚助,不是 Microsoft 就是 Cisco ... 都要想儘辦法把他們的技術發揮出來才能得獎,老實說寫起來跟工作差不多,總是要滿足那些 "市場" 的需求。

    這次題目老實說很 "不實用",純粹是比 code 誰寫的又快又好而已,不過還蠻合我胃口的 :D。正好這次碰到誰呼叫誰這種結構上的問題,就是上面四篇文章一直在討論的 GameHost 為主還是 Player 為主的思考方式,解決這問題花的工夫還比較多。想到這兩套解決方式,我覺的收穫是蠻值得的,至少我多學到兩種不同的設計模式。

    最後當然要感謝一下主辦人,下班專程騎車過來頒獎... 哈哈,獎品對我還蠻實用的,算是大獎一枚! 正好是我需要的東西,看來可以開始物色新硬碟,還有要準備來更新我的 SERVER 了 :D

    2008/10/02 .NET C# Tips 作品集 多執行緒 技術隨筆 有的沒的 物件導向 當年勇