12/19/2009 11:47:05 PM

[設計案例] 清除Cache物件 #2. Create Custom CacheDependency

543 | C# | CS | Microsoft.NET | MSDN | 小技巧 | 技術隨筆 | 物件導向 Facebook Share

上一篇廢話了這麼多,其實重點只有一個,我這次打算利用 CacheDependency 的機制,只要一聲令下,我想移除的 cache item 就會因為 CacheDependency 的關係自動失效,而不用很辛苦的拿著 cache key 一個一個移除。

我的想法是用 tags 的概念,建立起一套靠某個 tag 就能對應到一組 cache item,然後將它移除。開始之前先來想像一下 code 寫好長什麼樣子:

透過 tags 來控制 cache items 的範例程式[copy code]
   1:      static void Main(string[] args)
   2:      {
   3:          string[] urls = new string[] {
   4:              "http://columns.chicken-house.net/",
   5:              // 共 50 組網址... 略
   6:          };
   7:          foreach (string url in urls)
   8:          {
   9:              DownloadData(new Uri(url));
  10:          }
  11:          Console.ReadLine();
  12:          TaggingCacheDependency.DependencyDispose("funp.com");
  13:          Console.ReadLine();
  14:      }
  15:      private static void Info(string key, object value, CacheItemRemovedReason reason)
  16:      {
  17:              Console.WriteLine("Remove: {0}", key);
  18:      }
  19:      private static byte[] DownloadData(Uri sourceURL)
  20:      {
  21:          byte[] buffer = (byte[])HttpRuntime.Cache[sourceURL.ToString()];
  22:          if (buffer == null)
  23:          {
  24:              // 直接到指定網址下載。略...
  25:              buffer = null;
  26:              HttpRuntime.Cache.Add(
  27:                  sourceURL.ToString(),
  28:                  buffer,
  29:                  new TaggingCacheDependency(sourceURL.Host, sourceURL.Scheme),
  30:                  Cache.NoAbsoluteExpiration,
  31:                  TimeSpan.FromSeconds(600),
  32:                  CacheItemPriority.NotRemovable,
  33:                  Info);
  34:          }
  35:          return buffer;
  36:      }
  37:  }

 

 

這段 sample code 做的事很簡單,程式準備了 50 個網址清單,用 for-loop 一個一個下載。下載的 method: DownloadData(Uri sourceURL) 會先檢查 cache 是否已經有資料,沒有才真正下載 (不過下載的細節不是本篇要講的,所以就直接略過了...)。

而主程式的最後一行,則是想要把指定網站 ( funp.com ) 下載的所有資料,都從 cache 移除。為了方便觀看程式結果,我特地加上了 callback method, 當 cache item 被移除時, 會在畫面顯示資訊:

image

由執行結果來看,果然被移出 cache 的都是來在 funp.com 的網址... 接著來看看程式碼中出現的 TaggingCacheDependecny 是怎麼實作的。相關的 code 如下:

TaggingCacheDependency 的實作[copy code]
   1:  public class TaggingCacheDependency : CacheDependency
   2:  {
   3:      private static Dictionary<string, List<TaggingCacheDependency>> _lists = new Dictionary<string, List<TaggingCacheDependency>>();
   4:      public TaggingCacheDependency(params string[] tags)
   5:      {
   6:          foreach (string tag in tags)
   7:          {
   8:              if (_lists.ContainsKey(tag) == false)
   9:              {
  10:                  _lists.Add(tag, new List<TaggingCacheDependency>());
  11:              }
  12:              _lists[tag].Add(this);
  13:          }
  14:          this.SetUtcLastModified(DateTime.MinValue);
  15:          this.FinishInit();
  16:      }
  17:      public static void DependencyDispose(string tag)
  18:      {
  19:          if (_lists.ContainsKey(tag) == true)
  20:          {
  21:              foreach (TaggingCacheDependency tcd in _lists[tag])
  22:              {
  23:                  tcd.NotifyDependencyChanged(null, EventArgs.Empty);
  24:              }
  25:              _lists[tag].Clear();
  26:              _lists.Remove(tag);
  27:          }
  28:      }
  29:  }

 

30行不到... 其實程式很簡單,TaggingCacheDependency 繼承自 CacheDependency, 額外宣告一個靜態的 Dictionary<string, List<TaggingCacheDependency>> 來處理各個標簽及 TaggingCacheDependency 的關係,剩下的就沒什麼了。呼叫 DependencyDispose( ) 就可以通知 .NET Cache 機制,將相關的 cache item 移除。

用法很簡單,當你要把任何物件放進 cache 時,只要用 TaggingCacheDependency 物件來標示它的 tag:

把物件加進 Cache, 配上 TaggingCacheDependency ...[copy code]
   1:  HttpRuntime.Cache.Add(
   2:      sourceURL.ToString(),
   3:      buffer,
   4:      new TaggingCacheDependency(sourceURL.Host, sourceURL.Scheme),
   5:      Cache.NoAbsoluteExpiration,
   6:      TimeSpan.FromSeconds(600),
   7:      CacheItemPriority.NotRemovable,
   8:      Info);

在這個例子裡 (line 4), 直接在 TaggingCacheDependency 物件的 constructor 上直接標上 tags, 在此例是直接把網址的 hostname, scheme 兩個部份當作 tag, 未來就可以依照這兩種資訊直接讓 cache 裡的相關物件失效。

而要下令讓 Cache 內有標上某個 tag 的 cache item 失效,只要這行:

 

將標為 "funp.com" 的 cache item 設為失效的 cache item[copy code]
   1:  TaggingCacheDependency.DependencyDispose("funp.com");

 

結果就會如同上面的程式範例一樣,還留在 cache 的該網址下載資料,在這一瞬間通通都會被清掉...

 

用這種方式,是不是比拿到 key 再去呼叫 Cache.Remove( key ) 的方式簡單多了呢? 同時也能夠更快速的處理複雜的移除機制。其實運用 tagging 的方式只是一例,需要的話你也可以設計合適的 CacheDependency 類別。

以下是本篇文章的兩個附加參考檔案:

Download File - URL清單



12/19/2009 4:29:29 AM

[設計案例] 清除Cache物件 #1. 問題與作法

ASP.NET | C# | CS | Microsoft.NET | MSDN | 小技巧 | 技術隨筆 | 物件導向 Facebook Share

每次心裡有什麼好點子想寫出來時,第一關就卡在想不出個好標題... 想來想去的標題,怎麼看就是既不顯眼又不聳動... 果然是個老實的工程師性格 =_= ...  這次要講的,是 .NET HttpRuntime 裡提供的 Cache 物件的操作心得。這個東西我想不用我多作介紹,大家都用到爛掉了吧? 不過好用歸好用,有個老問題其實一直困擾著我很久了...

" 我該怎麼手動的把某個物件從 cache 裡移除? "

老實說,這問題蠻沒水準的... 老叫別人要翻 MSDN,我自己怎麼沒翻? 不不... 容我花點篇幅先說明一下問題。Cache物件,是個典型的 Dictionary 型態的應用 (雖然它沒有 implement interface: IDictionary… ), 透過 key 就可以拿到 cached item. 要從 cache 裡移除某個 item, 簡單的很,只要用 Remove 這個 method, 一行就搞定了:

從 key 移除指定的 cache item[copy code]
   1:  HttpRuntime.Cache.Remove(“cache-key”);

別小看這一行,實作起來障礙還不少。首先,你得額外去記著 cache key 的值。當你要移除的 cache item 有多個的時後,或是移除的 items 之間的關係有點複雜時,這些 code 就不怎麼漂亮了。下一個問題是:

" 我該如何得知所有存在 Cache 內的 keys 有那些? "

這個問題單純的多,那些把 intelligent sense 當購物網站的人 (平常不看文件,只會按下 . 然後挑個順眼 method 來用的人),可能這次就碰壁了... Cache 物件不像一般的 Dictionary 一樣,有提供 Keys 這樣的 property ... 它藏在 GetEnumerator 這 method 內,它會把所有的 keys 給巡一遍,你需要所有的 keys 的話,可以這樣用:

跑過 cache 裡每一個 key[copy code]
   1:  foreach (string key in HttpRuntime.Cache) { 
   2:      // … 
   3:  }

不過這樣的風險也是蠻高的,誰曉得你拿到 key 後的下一秒,這個 cache item 還在不在 cache 內?

 

 

 

--------------------------------------------------------------

本文正式開始! 哈哈,前面那一段只是廢話 + 碎碎唸,現在才是正題。前面想表達的只是,因為 cache 的不確定性 (資料隨時都會被 remove), 操作起來變的要格外小心, 即使它用起來像一般的 Dictionary 一樣。

我舉個案例,來說明我應用 cache 的情況。假如我想實作一個簡單的 web browser, 透過網路下載資源是很慢的動作,每種 browser 都會有某種程度的 cache 機制。我們就拿 Cache 物件替代 IE 的 "temporary internet files” 目錄吧。這時很簡單,只要用 URL 當作 KEY,下載的 content 就當物件塞進去就好...

不過事情沒那麼簡單。如果程式運作了一陣子,我想提供使用者手動清除 "部份" cache 的功能的話,那該怎麼辦? 我舉幾種情況:

  1. 從 cache 裡刪除所有從某個特定網站 (如: columns.chicken-house.net) 下載的資料
  2. 從 cache 裡刪除所有特定類型的資料 (如: content-type 為 image/jpeg 的圖檔)
  3. 從 cache 裡刪除所有透過特定 protocol (如: https) 下載的資料

這樣的要求應該不算過份吧? 用前面提到的兩種作法,你會想哭吧 XD .. 用這些基礎,你大概只能選這幾種作法 (各位網友有好作法也記得提供一下):

  1. 自己另外管理所有下載過的 URL, 用盡各種適合的資料結構,讓你可以順利的挑出這些 match 的 key, 然後移除它。

    缺點: 都作這麼多,你乾脆自己重寫個 cache 機制好了... 何況時間一久,你管理的 key, 那些對應的資料搞不好老早就通通從 cache 裡清掉了...
  2. 聰明一點,用 regular expression … 從 GetEnumerator( ) 一筆一筆過濾出要移除的 URL, 然後清掉它...

    缺點: 這作法只會檢查還留在 cache 內的 URL,不過這樣的 cache 隨便也有成千上萬個,每次都要 looping 掃一次實在不怎麼好看... 有違處女座有潔癖的個性...

 

這些方法 code 寫起來實在不怎麼漂亮,我就不寫 sample code 了,請各位自行想像一下寫起來的樣子。抱歉,如果你用的正好是上面的作法... 那請多包含... :D   這些都是 workable 的作法,但是看起來就是沒什麼設計感;程式可以動,不過就效能、簡潔、可讀性、美感來看,就是覺的不夠精緻 @@。跟朋友討論到這個問題時,我想到一個爛主意...

" 用蠢方法,這些 cache item 先分好類,每一類去關聯一個檔案,設 CacheDependency … 要清掉時去 touch 一下這個檔案,一整組的物件就會自動被清出 cache 了…。”

老實說,我覺的這是個既聰明又愚蠢的作法。聰明的是它很漂亮的解決我要如何移除某一群 item 的問題...,愚蠢的是這種單純程式內可以解決的事,竟然要繞到外面不必要的 file system I/O 動作... 而這通常是最慢的...

 

--

咳,寫太晚,實際的程式碼明天待續...



10/3/2009 2:24:00 PM

[設計案例] 生命遊戲 #6, 抽像化 (Abstraction)

C# | 小技巧 | 技術隨筆 | 物件導向 Facebook Share

原定 #4 就提到的 "抽像化",竟然被我連拖兩期,拖到 #6 才提到它... 人老了果然比較囉唆... 在前面的幾篇,重點都在如何 "具體" 的描述 "生命遊戲" 裡的細胞。不過現在要把這程式擴大到能容納各種不同的生物,先作好抽像化的工作是必要的...。

一般物件導向所指的 "抽像化",是指你對某些事物的一般概念。比如有人問你:

"你會開車嗎?"

你腦袋裡想的應該是一般印像中的車子,有方向盤,排檔打下去,油門踩了就會前進,煞車踩了就會停下來...,這就是你對 "車子" 的抽像化。你不會去管車子是什麼牌的,什麼顏色,是二門跑車,或是休旅車之類的細節... 而你 "會" 開的車,也不會因為這些細節,有太大的不同。

這樣的抽像化概念,套用到考駕照這件事來說,你只要知道方向盤,油門等等的用法,同時也練習過,能正確的控制教練車,通過測驗,監理所就會發張駕照給你,證明你會開一般的車子。就算是在你學會開車後十年才上市發表的新車也是一樣。

看起來沒什麼了不起的描述,在電腦的世界裡可不是這麼一回事。Microsoft Word 1.0 想要順利開啟 Microsoft Word 6.0 的檔案,大概想都不用想,因為 1.0 版設計之初,有太多 6.0 版的變化是無法事先預料的,自然無法設計出能正確操作的程式,這現像在電腦的世界很正常。不過如果你兩年前考到的駕照,碰到兩年後的新車你就不會開了,甚至監理所還要求你重考張新的架照... 那這駕照等於一點用都沒有。中間的差別,就在於駕駛者對於開車的認知,跟實際的車子,中間是隔著一層 "抽像化" 的概念,而只要能掌握這抽像化的定義,就能順利操作未來的車種。

因此物件技術不斷的想要模擬這樣的關係,就發展出繼承這樣的方式,來表達這個概念。先用一個類別 (base class) 或是介面 (interface) 來表達這個 "抽像化" 的概念,而不表達細節。其它要跟它互動的程式,只能透過這個抽像化型別來溝通,而其它的細節或實作,則被藏在裡面,或是衍生類別。中間的故事我就不再多說了,再說我就直接去寫 OOP 的書好了 =_=,有興趣可以參考這本經典 [世紀末軟體革命],有復刻版喔。套用到我們的 "生命遊戲" 裡,要定義的就是 "世界" 如何跟 "生命" 互動? 之間的關係是什麼? 另外就是 "生命" 有各種不同的型態,所有的 "生命" 型態是否都能順利的在同一個 "世界" 裡生存?

先試著用簡單文字來描述吧。在我們的定義裡,世界是個 M * N 的棋盤,每一格都能放一個生物。每個生物有自己的狀態 (生/死),也會隨著時間與環境的不同,讓生物的狀態產生變化。畫成 UML 的 class diagram, 大概就像這樣 (手邊沒工具,用 power point 大概畫一下… Orz):

image

我們在撰寫程式時,就必需思考題目中講到的生物各種特性,那些是所有的生命共有的特色? 這部份要把它定義在 Life … 另一部份是某種細胞特有的,則要放在衍生類別 Cell 裡。而世界必需要能跟生命作適當的互動,讓生命的進行能繼續下去。這樣的架構好處是,未來如果有第二種 Cell 或是其它的生物,只要是從 Life 繼承下來,都能很順利的在 World 裡活著,因為物件導向技術的 "抽像化" 概念,保證這樣程式的可行性。

好,我們就以需要跟 World 接觸跟互動的部份為主,把原程式的 Cell 抽離出來,放到它的上層類別 Life 裡。這也是物件技術裡常提到的 "generalization" (一般化),越一般的特性要越往上層類別移動,而越往下就是 "specialization" (特殊化),底層的類別要去實作特殊的部份,或是特有的細節。

先把原程式作好調整吧。原 Cell 的程式碼,部份被搬移到 Life, 同時這兩個類別有了繼承關係,如下:

 ClassDiagram1

Life 的部份,定義了所有 Life 都該表達出來的特性,也就是我們對於 Life 的認知,都應該描述在裡面,像是 Life 活在 World (CurrentWorld) 裡,會有它的座標 (PosX, PosY), 也會有它在這個棋盤內顯示的方式 (DisplayText) 等。而跟 World 互動的方面,Life 則透過 GetNextWorldTask( ) 來讓 World 來讓 Life 驅動它生命的進行。

在 World 的這邊,不管是那種 Life 衍生類別的物件,一律都當成 Life 的 "抽像概念" 來操作。這樣的優點,在還不曉得未來這世界到底還有多少種不同的 Life 會在裡面生活時,主要程式就能開發了。未來 Life 可以一直擴充,衍生出多種不同的 Life 子類別,而 Life / World 之間的互動及規範,則可以完全不用修正。

接下來就要讓這遊戲的規則,變的更真實一點了。實際的情況下,應該是我們已經知道會有那些不同的生物,經過歸納 (一般化及特殊化) 之後,可以設計出我們需要的類別架構。不過實際寫起程式來可沒這麼好命 (就像 USER 永遠不會一次給你完整確定的需求一樣),很多時後你得去 "猜" 或是 "假設",因此跟本沒有 "一般化" 這回事,你得預先去猜測未來要應付什麼問題,而在細節都還不清楚時就先定義出上層類別。

我們開始來試看看,我們定義的夠不夠抽像吧! 如果助教看你這麼快就把生命遊戲的作業交出來,覺的很沒面子,想把題目變難一點,加上有病毒感染的情況。於是原題目的四條規則追加一條,變成這樣:

  1. 孤單死亡:如果細胞的鄰居小於一個,則該細胞在下一次狀態將死亡。
  2. 擁擠死亡:如果細胞的鄰居在四個以上,則該細胞在下一次狀態將死亡。
  3. 穩定:如果細胞的鄰居為二個或三個,則下一次狀態為穩定存活。
  4. 復活:如果某位置原無細胞存活,而該位置的鄰居為三個,則該位置將復活一細胞。
  5. 感染:正常的細胞有 ( 1 + 受感染的鄰居數量 x5 )% 的機率受到病毒感染。已感染的細胞在 3 次狀態改變後會痊癒。受感染的狀況下,有 10% 的機率會死亡。

我們的程式該怎麼配合它改變? (對,機車的 USER 就都是這樣臨時修改規格...) 先來看看執行的結果,畫面上已經分的出來活著的 Cell 跟受感染的 Cell ... 除了看到 Cell 活著與死亡的變化之外,也看的到病毒擴散的狀況是怎麼樣。執行的畫面如下:

image

圖例: ◎受感染的細胞,●活著的正常細胞,○死亡的細胞

接著,來看看改版後的程式碼:

改版: 會受到病毒感染的 Cell 程式碼[copy code]
        public bool IsInfected        {            get { return this.InfectedCount > 0; }        }        private int InfectedCount = 0;        public override string DisplayText        {            get            {                if (this.IsAlive == true) return "●";                else if (this.IsInfected == true) return "◎";                else return "○";            }        }        protected override IEnumerable<TimeSpan> WholeLife()        {            yield return TimeSpan.FromMilliseconds(_rnd.Next(800, 1200));            for (int index = 0; index < int.MaxValue; index++)            {                int livesCount = 0;                int infectsCount = 0;                foreach (Cell item in this.FindNeighbors())                {                    if (item.IsAlive == true) livesCount++;                    if (item.IsInfected == true) infectsCount++;                }                bool? value = _table[this.IsAlive ? 1 : 0, livesCount];                if (value.HasValue == true)                {                    this.IsAlive = value.Value;                }                if (this.IsInfected == true)                {                    this.InfectedCount--;                    if (this.InProbability(10) == true) this.IsAlive = false;                }                else                {                    if (this.InProbability(1 + infectsCount * 5) == true) this.InfectedCount = 3;                }                yield return TimeSpan.FromMilliseconds(_rnd.Next(800, 1200));            }            this.Dispose();            yield break;        }
   1:  public bool IsInfected
   2:  {
   3:      get { return this.InfectedCount > 0; }
   4:  }
   5:  private int InfectedCount = 0;
   6:  public override string DisplayText
   7:  {
   8:      get
   9:      {
  10:          if (this.IsAlive == true) return "●";
  11:          else if (this.IsInfected == true) return "◎";
  12:          else return "○";
  13:      }
  14:  }
  15:  protected override IEnumerable<TimeSpan> WholeLife()
  16:  {
  17:      yield return TimeSpan.FromMilliseconds(_rnd.Next(800, 1200));
  18:      for (int index = 0; index < int.MaxValue; index++)
  19:      {
  20:          int livesCount = 0;
  21:          int infectsCount = 0;
  22:          foreach (Cell item in this.FindNeighbors())
  23:          {
  24:              if (item.IsAlive == true) livesCount++;
  25:              if (item.IsInfected == true) infectsCount++;
  26:          }
  27:          bool? value = _table[this.IsAlive ? 1 : 0, livesCount];
  28:          if (value.HasValue == true)
  29:          {
  30:              this.IsAlive = value.Value;
  31:          }
  32:          if (this.IsInfected == true)
  33:          {
  34:              this.InfectedCount--;
  35:              if (this.InProbability(10) == true) this.IsAlive = false;
  36:          }
  37:          else
  38:          {
  39:              if (this.InProbability(1 + infectsCount * 5) == true) this.InfectedCount = 3;
  40:          }
  41:          yield return TimeSpan.FromMilliseconds(_rnd.Next(800, 1200));
  42:      }
  43:      this.Dispose();
  44:      yield break;
  45:  }

細節我就不多介紹了。這裡的重點是經過抽像化的動作後,把 Life / Cell 之間的邏輯做明確的劃分。World 的類別程式碼完全沒有出現任何有關 Cell 的 Code, 只有出現 Life 而已。除了在主程式 GameHost 有這麼一段,明確的把 Cell 建立起來,把它放進 World:

建立世界的程式碼[copy code]
        static void Main(string[] args)        {            int worldSizeX = 30;            int worldSizeY = 30;            World realworld = new World(worldSizeX, worldSizeY);            Random _rnd = new Random();            for (int x = 0; x < worldSizeX; x++)            {                for (int y = 0; y < worldSizeY; y++)                {                    Cell item = new Cell();                    realworld.PutOn(item, x, y);                }            }            // ...
   1:  static void Main(string[] args)
   2:  {
   3:      int worldSizeX = 30;
   4:      int worldSizeY = 30;
   5:      World realworld = new World(worldSizeX, worldSizeY);
   6:      Random _rnd = new Random();
   7:      for (int x = 0; x < worldSizeX; x++)
   8:      {
   9:          for (int y = 0; y < worldSizeY; y++)
  10:          {
  11:              Cell item = new Cell();
  12:              realworld.PutOn(item, x, y);
  13:          }
  14:      }
  15:      // ...

這樣的作法,其實已經引含了 "動態聯結" 的特性了。在開發主程式的階段 (指 World / Life 這兩個主要的 class), 都還沒有 Cell 的相關細節,而事後執行的程式碼卻可以依照 Cell 裡的邏輯來執行。這代表了我們不需要改主程式的設計,就能不斷的加入新的規責,甚至是新的生物進來一起運作。

如何? 物件技術的 "抽像化" 能力,的確很有效的解決了這樣的變化需求。下一篇會沿用一樣的架構,但是執行的範例會完全不一樣 (這次不用細胞了,直接用草原上的生態: 草、羊、虎) 的生命及規則,來套進這個框架,看看它能怎麼模擬出一個新的生態系統。

這樣的架構可以應付未來未知的變化,只要你的抽像化概念不變的前題下都沒問題。這種保留彈性,卻又不用在 design time 去多做不必要的實作,才是物件技術強大的地方。我舉個反例,很多剛入行的軟體工程師,你給他一個需求,他會想太多... 一個簡單的輸入 1 + 1 要顯示 2 的結果,他會這麼想:

USER 需不需要列印啊? 我先把這需求放進去好了,然後加個 config 預設關掉它,以免以後需要我還得大改程式...

只能算 1 + 1? 如果以後 USER 要算 3 * 5 怎麼辦? 好吧,我把 + 用一個 mode 來代表好了,以後 USER 需要括充為支援 +-*/ 就不用大改程式了...

...

碰到這些狀況,我只能誇獎這位年青有為的程式設計師一句話:

"你很認真... 辛苦了..."

不過我心裡會苦笑... 只不過要你寫個 1 + 1 = 2,搞這麼一大包? 多作考慮,預留未來可能需要的功能,不是件壞事。不過既然是未知的需求,你又如何保證你能夠正確的 "預知" ,然後進一步 "預留" ? 何況這些多做的需求,未來真正會用上的有多少? 用不到的話,只是開發成本的浪費,及讓你的架構複雜性提高,維護的困難增加而已。物件技術真的解決的了這種問題嗎? 下一篇的目標,我們會定在不修改 World / Life 的設計為前題,把生命遊戲的模擬內容換成草原的生態模擬。敬請期待續集 :D

 

 

 

 



9/24/2009 2:42:00 AM

[設計案例] 生命遊戲 #5, 中場休息

543 | CS | Microsoft.NET | 技術隨筆 | 物件導向 Facebook Share

在繼續下去之前,先來講一下,我希望讓這個 "生命遊戲" 程式,發展到什麼程度吧。其實前面四篇都還只是基礎入門,跟準備動作而已,接下來才開始會有些有趣的。

我希望這系列文章寫完後,這個程式要能扮演一個真正可運作的 Matrix … 沒錯,就是像電影駭客任務裡的母體一樣,這個程式會變成 Matrix 的主要架構,而各式各樣的 "生物" 可以在這個虛擬世界裡生活。為了讓它真的跑的動,所以前幾篇提到的效能問題,執行緒問題,就不能不考慮。為了讓這個虛擬世界能更擬真一點,它至少要是個依時間驅動的模式,而不是像 "生命遊戲" 最早定義的回合制,因此這個問題也要在基本架構裡解決掉。

這些 "生物" 那裡來? 當然是大家來開發 :D 最終目標是要把這 Matrix 建起來,讓各位的生物可以放進來互相較勁一番... 因此先替這些程式 (生物) 抽像化,定義好它跟世界,及跟其它生物之間互動的規格 (就是下篇 "抽像化 / 多型" 要說的) 就是必要的工作之一了。替生命定義好抽像化介面之後,就可以開始衍生出各種不同的生命型態,一起加入這個虛擬世界,因此繼承、多型的技術就派上用場了。

生命是會演化的,當世界上真的演化出一種新的生命型態時,整個世界可以 "安裝" 好新的生命型態,然後全部存檔,重新啟動嗎? 當然不行... 因此如何 "動態" 的加入新的生命型態,如何不停止 GameHost 的前提下,由新的 Assembly 載入 Class (再下篇要說明的 "動態載入"),也是必需克服的技術之一。

這幾個階段及目標,就是我這一系列文章想要做到的。聽起來好像很有趣,可是卻又沒什麼實際的用途... Orz, 沒辦法,我就是喜歡寫這類要動點腦筋的程式,即使畫面一點都不炫也沒關係... 平常工作就不大有機會寫這種程式了,加上現在又只剩一張嘴...。

如果順利的發展,我倒是有個打算,這個 GameHost 成形之後,我打算定些基本的規則,比如土地上會有一定的機率及規則,長出草 (食物) 來。而這世界有各種不同的生物 (EX: 羊),需要靠這世界上的資源維持生命。到時大家可以把自己創造的 "羊" 一起放到這個世界內,看看執行了一陣子之後,誰設計的 "品種" 比較好,最後可以一代一代的繁衍下來...。

想的很美好,不過我不像 darkthread 可以替最後優勝的造物者提供獎品.. Orz.. 未來的設計藍圖就先規劃到這裡。在繼續下去之前,我把程式重新整理了一下,有興趣的人可以下載回去。這份程式碼跟 #4 的功能結構是一樣的,只不過整個架構都作過重整,變數等命名也調整過了,是為了往後說明相關物件技術時,不會被這些從 #1 ~ #4 改的支離破碎的程式碼干擾...

嗯,講了一堆廢話,結論就是: 敬請期待續集 :D  哈哈...

下載重整過的程式碼:



9/19/2009 3:58:22 PM

[設計案例] 生命遊戲 #4, 有效率的使用執行緒

Microsoft.NET | 543 | C# | Threading | 我的作品 | 技術隨筆 | 物件導向 Facebook Share

原本這篇不講執行緒,要直接跳到 OOP 多型的應用... 不過看一看 #3 自己寫的程式,實在有點看不下去... 30x30 的大小,程式跑起來就看到 903 條執行緒在那邊跑... 而看一下 CPU usage, 只有 5% 不到... 這實在不是很好看的實作範例,如果這是線上遊戲的 SERVER 程式,裡面的每個人,每個怪物等等都用一條專用的執行緒在控制他的行為的話,我看這遊戲不用太多人玩,SERVER 就掛掉了吧! 因此要繼續更貼近實際的生命模擬遊戲前,我們先來解決效能的問題,所以多安插了這篇進來 :D

前一篇 (#3) 的主題是把生命的進行,從被動的在固定時間被喚醒 (callback) 的作法,改成主動的在指定時間執行 (execute)。 想也知道,現實世界的生物都是 "主動" 的,後面的作法比較符合 OOP 的 "模擬世界,加以處理" 的精神。但是,一個小程式就吃掉 900 條執行緒,是有點過頭了。不知道還有沒有人記得,我騙到獎品的這個程式... 很另類的用 yield return 來解決類似問題的作法... 藉著 compiler 很雞婆的把單一流程翻成數段可以切開執行的邏輯...,正好拿來利用一下,替我們把一連串連續的邏輯切段,以便利用多執行緒來處理。我的想法是這樣,原程式是用個迴圈,作完該作的事,就休息 (sleep) 一段時間。而新的寫法,我打算用 yield return new TimeSpan(…) 來取代 Thread.Sleep(…)。每個 Cell內部的程式結構修改不大,不過對於 GameHost 就是個挑戰了... 來看看修改前及修改後的程式碼:

用 yield return TimeSpan 來取代 Thread.Sleep( ) 的作法[copy code]
   1:  // 修改前
   2:  // 使用 Thread.Sleep( ) 來控制時間
   3:  public void WholeLife(object state)
   4:  {
   5:      int generation = (int)state;
   6:      for (int index = 0; index < generation; index++)
   7:      {
   8:          this.OnNextStateChange();
   9:          Thread.Sleep(_rnd.Next(950, 1050));
  10:      }
  11:  }
  12:  //
  13:  //
  14:  //
  15:  // 修改後
  16:  // 使用 yield return new TimeSpan( ) 來控制時間
  17:  public IEnumerable<TimeSpan> WholeLife(object state)
  18:  {
  19:      int generation = (int)state;
  20:      for (int index = 0; index < generation; index++)
  21:      {
  22:          this.OnNextStateChange();
  23:          yield return TimeSpan.FromMilliseconds(_rnd.Next(950, 1050));
  24:      }
  25:      yield break;
  26:  }

 

別想的太美,只改這樣,程式是不會動的... 修改過之後,麻煩的地方會在 GameHost. 因為整個 GameHost 的邏輯都反過來了。原本是 GameHost 只要放著那九百條執行緒自生自滅,它只要不斷的刷新畫面就好了。現在它則得用 foreach(…) 去詢問:

"大爺,這次您要休息多久?"

接到 yield return 傳回的 TimeSpan 物件 (代表它要休息多久後,繼續下一個動作) 後,經過這段時間,GameHost 就要再去叫醒 cell, 然後再詢問一次:

"大爺,這次您要休息多久?"

關鍵就在於 GameHost 如何能透過少量的 thread 來伺後這些大爺,而不是像 #3 的程式一樣,每個大爺都用一條專屬的 thread… 要共用執行緒,就要先想辦法把工作切碎,這是基本法則。如果你希望你的生命遊戲程式不只是作業的話,那麼效能跟即時回應的問題是必需要考慮的。在動手改寫 GameHost 程式之前,先來分析一下改寫的目標有那些:

目標是要達到像 #2 範例一樣的效果,但是要用更有效率的方式。

目標很清楚,再來就看看有什麼手段可以用了。第一個是過量的執行緒,應該要想辦法改用執行緒集區。因為 #2 用了高達 900 條執行緒,不過整體 CPU USAGE 不到 5%,大部份的執行緒都在閒置狀態。如果能想辦法把這些運算丟到執行緒集區,由集區動態管理會有效率的多。

第二,就是把原本的 Thread.Sleep(ts) 改成 yield return ts 後,原本每個 thread 自己睡覺的機制,就要改成 cell 各自回報 game host 它想要睡多久,然後由 game host 統一在時間到時叫醒它。由於一次有多個 cell 同時在運作,因此我們需要一個簡單的排程器,作法像這樣:

  1. 建立一個時間表,依照時間順序,把每個 cell 預計要被叫醒的時間標上去。
  2. 時間到了之後,就去呼叫該 cell 的 OnNextStateChangeEx(),同時取得該 cell 下次要喚醒的時間,再標到時間表上
  3. GameHost就不斷的替每個 cell 重複 (1) (2) 的動作..
  4. 同時另外用一條獨立的執行緒,作畫面更新的動作。

嗯,要處理的方式越來越清楚了。剩下的是 "時間表" 要用什麼型式來表現? 我的選擇是,我希望它是個 ToDo List, 會幫我排好時間,我只要把工作標上時間,丟進 ToDo List, 然後 ToDo List 只要能忠實的回報給我還有沒有排定的工作? 如果有,下一個要處理的工作是那一個? 什麼時後處理?

它的用法只有丟工作進去,跟拿工作出來,因此我設計它的公開介面長這個樣子:

CellToDoList 的類別設計[copy code]
   1:  public class CellToDoList
   2:  {
   3:      public void AddCell(Cell cell) {...}
   4:      public Cell GetNextCell() {...}
   5:      public Cell CheckNextCell() {...}
   6:      public int Count {get;}
   7:  }

 

裡面的實作,我就不多說了。我是把它當成 QUEUE 在設計,唯一的差別是,放進 QUEUE 的東西會先經過排序,因此不見得是 "First In First Out" 這種典型的貯列,而是會以 Cell 上標示的時間為準,依序 Out …。實作起來很簡單,用現成的 SortedList 當內部的儲存方式,加上基本的 lock 機制來確保它是 thread safe 的就夠了。

好,這些雞絲都準備好之後,就可以來打造我們的新版 GameHost 了。來看看 Code:

改用 ThreadPool / CellToDoList 的新版 GameHost:[copy code]
   1:  static CellToDoList _cq;
   2:  static void _YieldReturnGameHost(string[] args)
   3:  {
   4:      int worldSizeX = 30;
   5:      int worldSizeY = 30;
   6:      World realworld = new World(worldSizeX, worldSizeY);
   7:      _cq = new CellToDoList();
   8:      // init threads for each cell
   9:      for (int positionX = 0; positionX < worldSizeX; positionX++)
  10:      {
  11:          for (int positionY = 0; positionY < worldSizeY; positionY++)
  12:          {
  13:              Cell cell = realworld.GetCell(positionX, positionY);
  14:              cell.OnNextStateChangeEx();
  15:              _cq.AddCell(cell);
  16:          }
  17:      }
  18:      // 啟動定期更新畫面的執行緒
  19:      Thread t = new Thread(RefreshScreen);
  20:      t.Start(realworld);
  21:      while (_cq.Count > 0)
  22:      {
  23:          Cell item = _cq.GetNextCell();
  24:          if (item.NextWakeUpTime > DateTime.Now)
  25:          {
  26:              // 時間還沒到,發呆一下等到時間到為止
  27:              Thread.Sleep(item.NextWakeUpTime - DateTime.Now);
  28:          }
  29:          ThreadPool.QueueUserWorkItem(RunCellNextStateChange, item);
  30:      }
  31:  }
  32:  private static void RunCellNextStateChange(object state)
  33:  {
  34:      Cell item = state as Cell;
  35:      TimeSpan? ts = item.OnNextStateChangeEx();
  36:      if (ts != null) _cq.AddCell(item);
  37:  }
  38:  private static void RefreshScreen(object state)
  39:  {
  40:      while (true)
  41:      {
  42:          Thread.Sleep(500);
  43:          (state as World).ShowMaps("");
  44:      }
  45:  }

 

GameHost 的工作很明確,一開始 (line 18 ~ 20) 就把更新畫面的動作完全交給另一個執行緒,之後就專心處理 ToDoList 內的工作了。

接著後面的 while loop (line 21 ~ 30) 則是很單純的從 ToDoList 裡取出下一個要要動作的 Cell, 如果時間還沒到就 Sleep 等一下它。執行完後會再詢問下一次是什麼時後,同時再把他加到 ToDoList 內等待下一次輪到他時繼續。

這次的程式我沒有設定停止的條件,因此你會看到程式會不斷的執行下去。程式執行起來,結果跟 #3 沒什麼不同,畫面上的每個細胞會照著題目的規則生長或死亡,不同的是 #3 的 Game Host 需要用到 903 條執行緒,而這版的 Game Host 只要 9 條執行緒...

image

 

其實,以這樣的範例題,我大可以不用顧慮到效能的問題,不過就是示範程式怎麼寫嘛。不過,我的目標如果只是訂在怎麼寫這練習題,大可以 GOOGLE 一下就有一堆作業解答了 :D。我的目標是要展示一下,該如何開發這樣的 GameHost ? 這樣的程式,是大部份的遊戲的基礎,尤其是像線上遊戲或是 facebook 這類互動遊戲的基礎。有了像樣的 Game Host 之後,接下來就把目標放在如何建立多樣的生物,一起放在這世界裡面生活了。接下來就會大量運用到 OOP 的特點 (對,就是上一篇預告的...) 繼承及多型。

有沒有人覺的,這種程式越寫越像 Matrix (就是駭客任務裡的 "母體") 了? 裡面活著的東西其實都在我的掌控之下... =_= 哈哈... 未完待續,請期待續集 :D。

--
範例程式:



9/15/2009 2:26:31 AM

[設計案例] 生命遊戲#3, 時序的控制

Microsoft.NET | C# | Threading | 作業系統 | 技術隨筆 | 物件導向 Facebook Share

原本的範例,其實有些盲點,不知各位有沒看到? 一樣的起始狀態,一樣的遊戲規則,你不一定會得到一樣的結果。為什麼? 因為這會跟你程式 SCAN 的順序有關。怎麼說? 因為到目前為只,整個遊戲就好像下棋一樣,是 "回合制",我下完了換你... 一路一直輪下去。

這時先下後下就會影響結果了。現實世界的生命不是這樣的啊... 不知有沒有人玩過早期的太空戰士 (Final Fantasy) 系列遊戲? 當年 FF 有個很重要的突破,就是把 RPG 從傳統的 "回合制" 改成即時戰鬥... 每個人都有個倒數的碼錶,數到 0 你就可以發動下一次的攻擊... 這樣才接近現實世界啊。套用到我們的生命遊戲,這次我們想作的改變,就是把程式改成這種模式。

因此來調整一下規則,每個細胞每隔 1000ms 後會進到下一個狀態。不過生命總是沒有完全一樣的,因此每個細胞進到下一個狀態的時間差,都會有 10% 的誤差 (也就是 950ms ~ 1050ms 之間的時間都有可能)。其它規責則維持不變,來看看程式該怎麼改寫。

這種 "即時制",是比較合乎現實的情況的,如果未來你想發展到像 facebook 上的那些小遊戲,或是其它線上遊戲一樣的話, "回合制" 是決對行不通的... 這時,我們可以想像,每個細胞都有自己的執行緒,每換過一次狀態後就 Sleep() 一段時間,醒來再換到下一次狀態... 一直到指定的世代 (generation) 到達為止。

來看一下改版過的程式。我們先不動原本的 Cell, 只追加一個 method: WholeLife( ), 呼叫後就會一直更新這個細胞的狀態,直到它結束為止 (不是死掉喔,是 generation 到達)。而整個世界的所有細胞,都是獨立的個體,都有個專屬的執行緒在運作...。這時 Game Host 就得換個方式來讓這些細胞過日子 (執行),同時 Game Host 好像有個人造衛星一樣,不斷的在上空拍照來更新畫面,而完全不影響這些細胞的生命進行。

來看一下改寫過的 Cell 追加的 method:

Cell 追加的 method[copy code]
   1:  public void WholeLife(object state)
   2:  {
   3:      int generation = (int)state;
   4:      for (int index = 0; index < generation; index++)
   5:      {
   6:          this.OnNextStateChange();
   7:          Thread.Sleep(_rnd.Next(950, 1050));
   8:      }
   9:  }

 

改變不大,只是多個簡單的迴圈,跟 sleep 來控制時間而已。再來看看 Game Host 要怎麼改:

多執行緒版本的 Game Host[copy code]
   1:  static void Main(string[] args)
   2:  {
   3:      int worldSizeX = 30;
   4:      int worldSizeY = 30;
   5:      int maxGenerationCount = 100;
   6:      World realworld = new World(worldSizeX, worldSizeY);
   7:      // init threads for each cell
   8:      List<Thread> threads = new List<Thread>();
   9:      for (int positionX = 0; positionX < worldSizeX; positionX++)
  10:      {
  11:          for (int positionY = 0; positionY < worldSizeY; positionY++)
  12:          {
  13:              Cell cell = realworld.GetCell(positionX, positionY);
  14:              Thread t = new Thread(cell.WholeLife);
  15:              threads.Add(t);
  16:              t.Start(maxGenerationCount);
  17:          }
  18:      }
  19:      // reflesh maps
  20:      do
  21:      {
  22:          realworld.ShowMaps("");
  23:          Thread.Sleep(100);
  24:      } while (IsAllThreadStopped(threads) == false);
  25:      // wait all thread exit.
  26:      foreach (Thread t in threads) t.Join();
  27:  }
  28:  private static bool IsAllThreadStopped(List<Thread> threads)
  29:  {
  30:      foreach (Thread t in threads)
  31:      {
  32:          if (t.ThreadState != ThreadState.Stopped) return false;
  33:      }
  34:      return true;
  35:  }

 

其實這卅幾行 code, 大都花在控制執行緒上面,有興趣的讀者可以翻翻我之前寫的那系列文章,我就不多作說明了。調整之後,這個世界變的更不可測了,一樣的起始環境,連上帝 (在這模擬世界裡,我就是上帝 XD) 都無法預測下一秒會發生什麼事...

image

 

感覺就好像看電視一樣。畫面不斷的在閃動,而畫面裡的細胞會不規責的跳動,不像上一版程式一樣,每刷一次就變一次那樣的枯燥無聊。如果畫面呈現的地方再多用點心思,就可以弄的像卡通一樣,每個細胞都各自用自己的步調在活著...

到這裡,如何? 應該沒有人把作業寫到這個樣子了吧 XD (就說別抄我的程式去交作業了)。不適當的利用執行緒,也做的到類似的結果。不過,你花費的代價會很大,因為你的程式得自己來做 context switch (這些是 OS + thread scheduler 會幫你解決掉的,只要你曉得要用 thread)。

接下來下一篇,我們再繼續調整這世界的遊戲規則,加入更多元素進去,看看程式會變怎樣? 多執行緒解決時間的問題了,再來我們要用繼承及多型,讓不同的生命可以在同一個世界下共同生活...  ((待續))

 



9/14/2009 1:32:02 AM

[設計案例] 生命遊戲#2, OOP版的範例程式

Microsoft.NET | C# | 我的作品 | 技術隨筆 | 物件導向 Facebook Share

還好,第一版的程式沒有難產。這版的目的很簡單,就是把題目實作出來,同時我會盡量套用物件導向的理念去設計程式的結構,而不是只把結果算出來而已。其實我一直覺的,這類生命模擬的程式,是非常適合用OOPL來實作的範例,大概OOPL所有強調的特性 (封裝、繼承、多型、動態聯結... 等等) 都用的到,算是完美的應用範例題吧!

不過很奇怪的,我特地 GOOGLE 了一下,不知 OOPL 高手都不屑寫這種範例還是怎樣,找到的範例程式,不管用什麼語言 (C/C++/Java/C#都有) 寫的,清一色都很沒有物件導向的 fu ... 好吧,只好自己來寫一個。

第一步,一定是先看看你的程式,分析出需要那些類別/物件,及它們之間的關係。比較正規的作法就是 UML 的 UseCase 了。不過這範例其實不大,我就直接跳到 Class Diagram 了 (因為VS2008剛好有現成的...)... 主要的類別有兩個: World (世界) 及 Cell (細胞)。

World 就是給 Cell 生活的空間,我們只訂義一個有限大小的二維空間,就一個 M x N 的棋盤這樣。而 Cell 則是一個細胞,描述單一一個細胞本身,在各種不同的條件下會有什麼反應。先貼一下 class diagram:

 

image  
圖1. class diagram (World & Cell)

老實說,這張圖還蠻乏善可陳的,World對外公開的介面,大概包含了幾個主要功能,就是取得指定座標的 Cell (GetCell), 及把目前的整個 World 狀態印出來 (ShowMaps) 的 method 而已。而 Cell 的公開介面,不外乎是它目前是活著還是死的,還有它的建構式,及呼叫後會把狀態轉移到下一次狀態的 method。

其它都是 World / Cell 互相溝通用,或是 Init 用的 Method / Prop, 就不多作介紹。先來看看主程式,扮演上帝的你,如何讓這堆單細胞生物,在你的世界裡活起來:

Game Of Life 主程式[copy code]
   1:  static void Main(string[] args)
   2:  {
   3:      int worldSizeX = 30;
   4:      int worldSizeY = 30;
   5:      int maxGenerationCount = 100;
   6:      World realworld = new World(worldSizeX, worldSizeY);
   7:      for (int generation = 1; generation <= maxGenerationCount; generation++)
   8:      {
   9:          realworld.ShowMaps(string.Format("Generation: {0}", generation));
  10:          Thread.Sleep(1000);
  11:          for (int positionX = 0; positionX < worldSizeX; positionX++)
  12:          {
  13:              for (int positionY = 0; positionY < worldSizeY; positionY++)
  14:              {
  15:                  // do day pass
  16:                  Cell cell = realworld.GetCell(positionX, positionY) as Cell;
  17:                  cell.OnNextStateChange();
  18:              }
  19:          }
  20:      }
  21:  }

 

主程式我還沒把不相干的動作刪掉,也才廿一行... line 1 ~ 5 只是初始值,line 6 建立整個世界,之後就每跑完一個世代 (generation) 就休息一秒鍾,繼續下一次進化。這樣隨著時間的過去,畫面上會一直更新整個世界的狀態... 直到只定的次數到了為止。

 

class World 的部份就沒什麼特別的,就只是把一個二維陣列包裝一下而已。直接貼 Code 就混過去吧 XD,一樣沒有刪掉程式碼,原 CODE 照貼:

class World 的程式碼[copy code]
   1:  public class World
   2:  {
   3:      private int SizeX = 0;
   4:      private int SizeY = 0;
   5:      private Cell[,] _map;
   6:      public World(int maxPosX, int maxPosY)
   7:      {
   8:          this._map = new Cell[maxPosX, maxPosY];
   9:          this.SizeX = maxPosX;
  10:          this.SizeY = maxPosY;
  11:          for (int posX = 0; posX < maxPosX; posX++)
  12:          {
  13:              for (int posY = 0; posY < maxPosY; posY++)
  14:              {
  15:                  this._map[posX, posY] = new Cell(this, posX, posY);
  16:              }
  17:          }
  18:      }
  19:      internal void PutOn(Cell item, int posX, int posY)
  20:      {
  21:          if (this._map[posX, posY] == null)
  22:          {
  23:              this._map[posX, posY] = item;
  24:              item.PosX = posX;
  25:              item.PosY = posY;
  26:          }
  27:          else
  28:          {
  29:              throw new ArgumentException();
  30:          }
  31:      }
  32:      public Cell GetCell(int posX, int posY)
  33:      {
  34:          if (posX >= this.SizeX) return null;
  35:          if (posY >= this.SizeY) return null;
  36:          if (posX < 0) return null;
  37:          if (posY < 0) return null;
  38:          return this._map[posX, posY];
  39:      }
  40:      public void ShowMaps(string title)
  41:      {
  42:          Console.Title = title;
  43:          Console.SetWindowSize(this.SizeX * 2, this.SizeY);
  44:          Console.SetCursorPosition(0, 0);
  45:          Console.Clear();
  46:          for (int y = 0; y < this.SizeY; y++)
  47:          {
  48:              for (int x = 0; x < this.SizeX; x++)
  49:              {
  50:                  Cell item = this.GetCell(x, y);
  51:                  Console.SetCursorPosition(x * 2, y);
  52:                  Console.Write(item.IsAlive? "●":"○");
  53:              }
  54:          }
  55:      }
  56:  }

 

接下來是封裝每個細胞本身跟環境互動的影響,把上一篇講的規則對應成程式碼的樣子。先來看看 CODE:

class Cell 的程式碼[copy code]
   1:  public class Cell //: Life
   2:  {
   3:      protected World CurrentWorld { get; private set; }
   4:      internal int PosX = 0;
   5:      internal int PosY = 0;
   6:      private const double InitAliveProbability = 0.2D;
   7:      private static Random _rnd = new Random();
   8:      public Cell(World world, int posX, int posY) //: base(world, posX, posY)
   9:      {
  10:          this.CurrentWorld = world;
  11:          // setup world
  12:          this.PosX = posY;
  13:          this.PosY = posY;
  14:          this.CurrentWorld.PutOn(this, posX, posY);
  15:          this.IsAlive = (_rnd.NextDouble() < InitAliveProbability);
  16:      }
  17:      public bool IsAlive { get; private set; }
  18:      protected IEnumerable<Cell> FindNeighbors()
  19:      {
  20:          foreach (Cell item in new Cell[] {
  21:              this.CurrentWorld.GetCell(this.PosX -1, this.PosY-1),
  22:              this.CurrentWorld.GetCell(this.PosX, this.PosY-1),
  23:              this.CurrentWorld.GetCell(this.PosX+1, this.PosY-1),
  24:              this.CurrentWorld.GetCell(this.PosX-1, this.PosY),
  25:              this.CurrentWorld.GetCell(this.PosX+1, this.PosY),
  26:              this.CurrentWorld.GetCell(this.PosX-1, this.PosY+1),
  27:              this.CurrentWorld.GetCell(this.PosX, this.PosY+1),
  28:              this.CurrentWorld.GetCell(this.PosX+1, this.PosY+1)})
  29:          {
  30:              if (item != null) yield return item;
  31:          }
  32:          yield break;
  33:      }
  34:      public void OnNextStateChange()
  35:      {
  36:          int livesCount = 0;
  37:          foreach (Cell item in this.FindNeighbors())
  38:          {
  39:              if (item.IsAlive == true) livesCount++;
  40:          }
  41:          if (this.IsAlive == true && livesCount <1)
  42:          {
  43:              //孤單死亡:如果細胞的鄰居小於一個,則該細胞在下一次狀態將死亡。
  44:              this.IsAlive = false;
  45:          }
  46:          else if (this.IsAlive == true && livesCount >= 4)
  47:          {
  48:              //擁擠死亡:如果細胞的鄰居在四個以上,則該細胞在下一次狀態將死亡。
  49:              this.IsAlive = false;
  50:          }
  51:          else if (this.IsAlive == true && (livesCount == 2 || livesCount == 3))
  52:          {
  53:              //穩定:如果細胞的鄰居為二個或三個,則下一次狀態為穩定存活。
  54:              //this.IsAlive = true;
  55:          }
  56:          else if (this.IsAlive == false && livesCount == 3)
  57:          {
  58:              //復活:如果某位置原無細胞存活,而該位置的鄰居為三個,則該位置將復活一細胞。
  59:              this.IsAlive = true;
  60:          }
  61:          else
  62:          {
  63:              // ToDo: 未定義的狀態? assert
  64:          }
  65:      }
  66:  }

這裡開始應用到 OOPL 第一個特性: 封裝。從程式碼可以看到,主要的邏輯都被包在裡面了,就 Game Of Life 裡提到的四條規則。

程式這樣寫起來,比那些作業的標準答案看起來舒服多了吧? 雖然行數多了一些,不過看起來比較有 OO 的樣子了。當然只是看起來爽是沒用的,這樣的架構,到目前為只除了邏輯清楚一點之外,還看不到其它很明顯的好處。不過當這個規責稍微複雜一點,OOPL的優點就會被突顯出來了。

下回,把題目做點變化,再來看看程式該如何調整…   ((待續))

--
附件: 範例程式碼



9/12/2009 4:09:30 AM

[設計案例] 生命遊戲#1, 前言

Microsoft.NET | C# | Threading | 技術隨筆 | 物件導向 Facebook Share

[前言]

好久沒寫點自己覺的有內容的東西了... 最近 code 寫的少,實在沒有什麼了不起的新技術可以分享,而 thread 那種 "古典" 計算機科學的東西也寫的差不多了.. 就懶了起來。

雖然沒新技術好寫,不過老狗玩的把戲還是能榨出點渣的... 很多人都熟新技術,可以寫出很炫的程式,不過也常看到程式的結構真的是亂搞一通的... 所以我打算寫些 [設計案例] 的文章,舉一些我實作過的案例,說明什麼樣的問題可以用什麼方式或技術來解決。其實我想寫的就是像 design patterns 那類的東西,只不過我程度還差的遠,只能稱作 "案例" ... Orz

----------------------------------------------------------------------------------

最近 facebook 上有一些小遊戲,不知道在紅什麼... 突然間大家都在玩,就都是些模擬遊戲,像是開心農場、My FishBowl … 之類的,你要在裡面種東西或養魚,條件充足就會長大,收成等等... 然後透過 Facebook API 可以跟別人互動的遊戲。看到這類的 GAME,不禁想起過去在唸書時,幾個經典的作業題目,其中一個 [生命遊戲] (Game of Life) 就是這種 GAME 的始祖...

在 Wiki 找的到這段介紹:

http://zh.wikipedia.org/zh-hk/%E7%94%9F%E5%91%BD%E6%B8%B8%E6%88%8F

生命遊戲(Game of Life),又稱生命棋,是英國數學家約翰·何頓·康威(John Horton Conway)在1970年發明的細胞自動機(cellular automaton,也翻譯成「格狀自動機」)。

它最初於1970年10月在《科學美國人》(Scientific American)雜誌中馬丁·葛登能(Martin Gardner)的「數學遊戲」專欄出現。

1970… 我還沒出生... Orz, 不過, 這麼一個古老經典的問題,找的到一大堆範例程式,或是作業解答。清一色是用 C 這類配的上它的年紀的程式語言寫的,就算有 JAVA 版,大概也是換湯不換藥... 這四十年程式語言及軟體技術的進步,寫這種程式總該有點改變吧?

這篇我想寫的,就是這樣的問題,配合現在的 .NET / C#,能怎麼寫它? 這年代的軟體開發技術,對這種古典的程式能發揮什麼效益?

(警告: 剛好要交作業的人,可千萬別用我的方法交出去啊... 你的助教看不懂可能會給你零分...)

先找個範例來看看... 為了不讓過多的畫面處理程式碼,干擾到主程式的架構,我特地找了兩個 console based 的範例:

Java 版:
http://tw.myblog.yahoo.com/dust512/article?mid=25&prev=28&next=-1

多語言版 (C, Java, Python, Scala):
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/LifeGame.htm

這... 這就是典型的 "Java 版 C 程式碼" 的範例... 用 Java 來寫只寫這樣,有點用牛刀的感覺... 新的開發環境強調這幾項:

  1. 物件導向 (封裝,多型,動態連結... etc)
  2. 多執行緒
  3. 其它語言特色 (這次會講到的是 yield return)

這些技術怎麼套進這程式? 先來看看這遊戲有幾個障礙要克服吧。遊戲的規則簡單明瞭,借轉貼上面第二個範例的說明:

生命遊戲(game of life)為1970年由英國數學家J. H. Conway所提出,某一細胞的鄰居包括上、下、左、右、左上、左下、右上與右下相鄰之細胞,遊戲規則如下:

  1. 孤單死亡:如果細胞的鄰居小於一個,則該細胞在下一次狀態將死亡。
  2. 擁擠死亡:如果細胞的鄰居在四個以上,則該細胞在下一次狀態將死亡。
  3. 穩定:如果細胞的鄰居為二個或三個,則下一次狀態為穩定存活。
  4. 復活:如果某位置原無細胞存活,而該位置的鄰居為三個,則該位置將復活一細胞。

以前我最討厭寫這種程式了,這種程式寫起來就跟 Regexp 一樣,是 "write only” 的 code… 怎麼說? 程式寫好後,可能自己都看不懂了,因為邏輯被切的亂七八糟... GAME 裡可能同時有好幾個細胞,每個都有獨立的規則,不過程式卻是一個主迴圈,每次執行每個細胞的一小段邏輯... 程式的流程就這樣被切碎了... 我打算用C#的 yield return, 解決這邏輯破碎的問題。

第二個障礙,就是這類程式,某種程度都是隨著時間的進行而跑的,比如上面的條件都是 "下一次狀態" … 把每次狀態改變定義一個時間 (比如一秒),這就是個 realtime 的模擬程式了。如果有的細胞是一秒改變一次狀態,有的是兩秒,有的是五秒... 那就傷腦筋了... 你的程式會被切的更破碎... 這些每種細胞特殊的部份,我打算用 OOP 的多型來解決。

最後,這種很明顯是 "並行" 的問題,照道理來說,用多執行緒是最適合的了。不過隨便也有成千上萬個 "細胞" 在成長,每個都來一個 thread 養它,再高級的 server 都撐不住吧? 這邊會來探討一下,怎麼用執行緒相關的技巧,來解決這問題。

 

--------------------------------------------------------------------------------------

寫到這裡,突然覺的這題目好大... Orz, 搞不好這幾篇要撐幾個月才寫的完... 至少有個題材好寫,等到我生出第一個 sample code, 就會有下一篇了... 如果有同好也想試試看的,也歡迎分享看看你的 code… 只不過我沒像 darkthread 有本錢提供獎品... 哈哈 :D



3/3/2009 3:48:15 AM

EF#3. Entity & Inheritance

Microsoft.NET | C# | Entity Framework | ORM | SQL | 技術隨筆 | 物件導向 Facebook Share

繼承 (inheritance) 是物件技術的核心,就是這個特性提供了 OOP 絕大部份的特色。這東西被拿掉的話,OOP就沒這麼迷人了。繼然談到了 ORM,就不能不來看看 R(關聯式資料庫) 怎麼被對應到 O(物件),同時還能處理好繼承關係。

RDBMS 連基本的物件 (Object Base) 都不支援了,更別說物件導向 (Object Oriented) 了。因此要搞懂 ORM 及繼承的關係,就得先瞭解基本的 OO 是怎麼實作 "繼承" 這個動作。這些知識是古早以前學 C++ 時唸到的,現在的 CLR 不知道有沒有新的作法? 不過應該大同小異吧! C++ 主要是靠 virtual table 來實作繼承關係,當子類別繼承父類別時,父類別定義的 data member 跟 method 就全都遺傳到子類別身上了,這動作就是靠 virtual table 作到的。細節我就不多說了,有興趣的讀者們請先上網找找相關資訊看一看。

ORM 的運氣好多了,只要處理資料的部份。因此前一段提到的 virtual table 如果要拿來應用也會簡單的多。virtual table 可以很直覺的想像成是 DBMS 裡 table schema 的定義,而一個物件 (instance) 的 virtual table 資料,正好就對應到該 table (DBMS) 的一筆資料。這正好是 ORM 基本的動作。大部份 OO 的書都會說,繼承就是 " Is A " 的關係。在資料上則是子類別擁有父類別所有的欄位定義。這很容易對應到資料庫的正規化,該如何切割資料表的規責。你可以切開靠 PK / FK 再併回來,或是直接反正規化讓它重複定義在多個 TABLE... 事實上,兩大 ORM (EF & NH) 都歸納出三種作法,後面來探討一下彼此的差異...

再來看看繼承關係,假設父類別 class A 對應到 table A, 那麼衍生出的子類別 class B 對應的 table B, 則應該要包含所有 table A 定義的欄位才對。從這點出發,就帶出了第一種作法: 就是把 table A 所有的欄位都建一份到 table B (註: table per concrete type)。

不過這樣看起來有點蠢,DBMS 熟悉的人也許會採另一種作法: 沒錯... table B 只要留個 foreign Key, 指向 table A 的 primary Key,需要時再 join 起來就好了,這是第二種作法 (註: table per type)。

唸過 DBMS 的人都還記得 "正規化" (normalization) 跟 "反正規化" 吧? 切割過頭也是很麻煩的,因此有第三種作法逆其道而行,就是建一個 table 給所有的子子孫孫類別共用。因此 table 需要的欄位,就是所有的子類別的所有欄位集大成,通通都建進來... 不用的話就空在那裡,這是第三種作法 (註: table per hierarchy)。

這三種作法,在 Entity Framework (以下簡稱 EF) 或是 NHibernate (以下簡稱 NH) 都有對應的作法,只不過名字不大一樣... 這篇 ADO.NET team blog 借紹的還不錯,可以參考看看。這三種方式,在 EF 裡的說法分別是 (括號裡是 NH 的說法,參考這篇: Inheritance Mapping):

  • Table per Hierarchy (NH: Table per class hierarchy)
  • Table per Type (NH: Table per subclass)
  • Table per Concrete Type (NH: Table per concrete class)

事時上,處理方式大同小異,不外乎用三種不同的對應方式,來處理物件繼承關係。這些不同類別的物件彼此有繼承關係,對應到 TABLE 的方法不同,各有各的優缺點。其實 ADO.NET team blog 講的都很清楚,我就不再多說,簡單列張比較表:

  適用於 不適用於
Table Per Hierarchy
  1. 最簡單的實作方式
  2. 所有同系類別的實體 (instance) 數量不會很多時
  3. 需要用單一 QUERY 查出所有的子類別物件時
  4. 繼承階層較簡單的情況
  5. 類別的欄位要調整很容易
  1. instance數量太多,會嚴重影響效能
  2. 無法在table schema上做太多嚴格的檢查
Table Per Type
  1. 繼承關係清楚的對應到 TABLE
  2. 需要用單一QUERY查出所有子類別的物件
  3. 不同於 TPH,可以針對每種類別,設定嚴僅的 table constraint
  4. 每個類別要變動或調整都很容易
  1. 繼承階層較多時,要取得單一 instance data 需要透過多層 join
  2. table 數量會隨著類別的數量快速增長
Table Per Concrete Type
  1. 綜合 TPH / TPT 的優點 (也綜合了兩者的缺點)
  2. 可以針對每種類別設定 table constraint
  3. ORM mapping 很簡單
  1. 要用單一QUERY查出所有子類別的物件並不容易 (需要把所有的 TABLE JOIN 起來)
  2. 父類別的欄位調整很麻煩,所有的 TABLE 都需要配合調整

 

[未完待續] to be continue…



1/23/2009 12:09:53 AM

EF#2. Entity & Encapsulation

Microsoft.NET | C# | Entity Framework | ORM | SQL | 物件導向 Facebook Share

前一篇講了一堆大道理,這篇就來看一些實作吧。各種 ORM 的技術都有共同的目的,就是能把物件的狀態存到關聯式資料庫,而這樣的對應機制則是各家 ORM 競爭的重點,勝負的關鍵不外乎是那一套比較簡單? 那一套包裝出的 Entity 物件能夠更貼近一般的物件?

會有這樣的 "對應" 機制需求,原因只有一個,物件技術發展的很快,已經能解決大多數軟體開發的需求了,不過資料庫就沒這麼幸運,現在的 DBMS 撇開一些技術規格不談,本質上還是跟廿年前差不多,就是關聯式資料庫而已,本質上就是一堆 table + relationship, 配合 SQL 語法來處理資料。發展至今,物件技術跟資料庫技術能處理的問題,已經是兩個完全不同世界的問題了,三層式的架構在這段出現斷層...。

解決方式大概有兩條路,一種就是想辦法把這兩個世界串起來,就是 ORM framework 想做的事。另一個就是改造 RDBMS,讓 RDBMS 進化成也具有物件導向特性的資料庫。不過以眼前的五年十年來看,ORM 還是大有可為。ORM 只要能把 "對應" 這件事做到完美的地步,其實在某個層面上就已經做到 OODB 的願景了,只差在這些物件是活在 APP 這端,不是活在資料庫那端...。

扯遠了,接下來我會試著從物件技術的三大核心 (封裝、繼承、多型),及資料庫最需要的查尋機制 (QUERY) 來看看 Entity Framework 各能提供什麼支援,才能客觀的評論 Entity Framework 值不值得你投資在它身上。

在繼續看下去之前,請先俱備基本的 Entity Framework 運用的能力。在 MSDN 名家專欄裡 MVP(朱明中) 寫的這幾篇我覺的很不錯,可以參考看看。我就是看這幾篇入門的 :D。幾年前在比賽上碰過他幾次,我還蠻配服他的,可以靠自學而有今天的成就。以下是他寫的幾篇 ADO.NET / Entity Framework 的系列文章:

  1. 讀寫 ADO.NET Entity Framework (2007 年 9 月)
  2. 由 LINQ 存取 ADO.NET 物件 (2007 年 9 月)
  3. 整合 ADO.NET Entity Framework 到應用程式中 (2007 年 9 月)
  4. 首次接觸 ADO.NET Entity Framework (2007 年 9 月)
  5. ADO.NET Entity Framework 概觀 (2007 年 9 月)

 

在開始之前,我們先來看看一個最簡單的 Entity Framework 的範例,然後來看看封裝性能夠對你的程式帶來什麼影響? 先來看看只用到了 ORM 卻沒發揮封裝性的例子:

image

這是存放會員資料的表格,對應的 TABLE 很簡單,SQL 如下:

[copy code]
   1:  CREATE TABLE [dbo].[Users](
   2:    [ID] [nvarchar](50) NOT NULL,
   3:    [PasswordHash] [image] NOT NULL,
   4:    [PasswordHint] [nvarchar](100) NOT NULL,
   5:    [SSN] [nchar](10) NOT NULL,
   6:    [Gender] [int] NOT NULL,
   7:   CONSTRAINT [PK_Users] PRIMARY KEY CLUSTERED
   8:  ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]

 

大部份的人在 EDMX Designer 裡把資料表拉進來後,就開始用這個 Entity Class 了吧? 密碼的部份為了安全及實作上的考量,DB只存放 HASH,而 HASH 的運算則透過 .NET 程式來計算,不透過 SQL 的函數。作法決定後,你可能會寫出這樣的程式碼:

建立帳號的程式碼[copy code]
   1:  // 準備 object context
   2:  using (Membership ctx = new Membership())
   3:  {
   4:      // create user account:
   5:      User newUser = new User();
   6:      newUser.ID = "andrew";
   7:      newUser.PasswordHint = "12345";
   8:      newUser.PasswordHash = HashAlgorithm.Create("MD5").ComputeHash(Encoding.Unicode.GetBytes("12345"));
   9:      newUser.SSN = "A123456789";
  10:      newUser.Gender = 1;
  11:      ctx.AddToUserSet(newUser);
  12:      ctx.SaveChanges();
  13:  }

 

檢查密碼的程式碼[copy code]
   1:  // 準備 object context
   2:  using (Membership ctx = new Membership())
   3:  {
   4:      string passwordText = "12345";
   5:      User curUser = ctx.GetObjectByKey(new EntityKey("Membership.UserSet", "ID", "andrew")) as User;
   6:      bool isPasswordCorrect = true;
   7:      {
   8:          byte[] passwordTextHash = HashAlgorithm.Create("MD5").ComputeHash(Encoding.Unicode.GetBytes(passwordText));
   9:          if (passwordTextHash.Length != curUser.PasswordHash.Length)
  10:          {
  11:              isPasswordCorrect = false;
  12:          }
  13:          else
  14:          {
  15:              for (int pos = 0; pos < curUser.PasswordHash.Length; pos++)
  16:              {
  17:                  if (passwordTextHash[pos] != curUser.PasswordHash[pos])
  18:                  {
  19:                      isPasswordCorrect = false;
  20:                      break;
  21:                  }
  22:              }
  23:          }
  24:      }
  25:      Console.WriteLine("Password ({0}) check: {1}", passwordText, isPasswordCorrect ? "PASS" : "FAIL");
  26:  }

 

這樣的 User 類別設計有什麼問題? 我列幾個我認為設計上不妥的地方:

  1. 直接提供 PasswordHash 曝露過多不必要的實作細節
  2. 在台灣,身份證字號 (SSN) 跟性別 (Gender) 是相依的欄位 ( functional dependency )

以物件導向的角度來看,User 真正要提供的是接受 "驗證密碼" 的要求,至於你的實作是提供明碼或是用 Hash, 都是實作的細節。提供原始未加密的密碼,或是提供處理過的 HASH,在需求上都是不必要個功能。物件的介面定義要盡量以能滿足需求的最小介面為原則,其它的都不要公開,才滿足 "封裝性" 的要求。因此良好的設計應該把這些細節封裝起來,只在公開的介面表達你要提供的功能。

另外依照台灣的身份證字號規則, SNN 跟 Gender 是連動的。目前 User 的設計是把兩者的關係丟給前端寫網頁的人來維護,一不注意就會發生不一致的情況。DB 對於這種問題的解決方式,不外乎寫 trigger 或是其它 constraint 的方式來阻擋不正確的資料被寫入 DB,不過看了前面提到的規則,要單純用 SQL 的功能完整實作出來,還不大容易。

另一種作法,只儲存 SSN,Gender 欄位則以 VIEW 的方式提供,這樣就不會有不一致的問題。不過這方法的缺點在於,當邏輯太複雜的時後,常常會超出 SQL 能處理的範圍,效能也許會是個問題,或是 constraint 不能完全跟程式端一致。

就我看來,這類看似應該在 data layer 實作的複雜邏輯,又難以在 SQL DB 上面解決的問題,才是 Entity Framework 的強項。現在來看看 Entity Framework 能怎麼解決這些資料封裝的需求:

首先,把不需要公開的細節改成 Private 隱藏起來,包括 PasswordHash 的 Getter / Setter, Gender 更名為 GenderCode, 同時把 Getter / Setter 也改為 Private ...

接下來就要把這些封裝起來的細節,提供另一組較合適的公開資訊的方式。這時 .EDMX designer 替我們產出的 code 就能搭配 partial class 擴充功能了。來看看我們在 partial class 裡寫了什麼?

User.cs 的內容 (partial class)[copy code]
   1:  public partial class User
   2:  {
   3:      public string Password
   4:      {
   5:          set
   6:          {
   7:              this.PasswordHash = this.ComputePasswordHash(value);
   8:          }
   9:      }
  10:      public bool ComparePassword(string passwordText)
  11:      {
  12:          byte[] hash = this.ComputePasswordHash(passwordText);
  13:          // compare hash
  14:          if (this.PasswordHash == null) return false;
  15:          if (hash.Length != this.PasswordHash.Length) return false;
  16:          for (int pos = 0; pos < hash.Length; pos++)
  17:          {
  18:              if (hash[pos] != this.PasswordHash[pos]) return false;
  19:          }
  20:          return true;
  21:      }
  22:      public GenderCodeEnum Gender
  23:      {
  24:          get
  25:          {
  26:              return (GenderCodeEnum)this.GenderCode;
  27:          }
  28:      }
  29:      partial void OnSSNChanging(string value)
  30:      {
  31:          // ToDo: check ssn rules.
  32:          // sync gender code
  33:          this.GenderCode = int.Parse(value.Substring(1, 1));
  34:      }
  35:      private byte[] ComputePasswordHash(string password)
  36:      {
  37:          if (string.IsNullOrEmpty(password) == true) return null;
  38:          return HashAlgorithm.Create("MD5").ComputeHash(Encoding.Unicode.GetBytes(password));
  39:      }
  40:  }
  41:  public enum GenderCodeEnum : int
  42:  {
  43:      FEMALE = 0,
  44:      MALE = 1
  45:  }

 

被隱藏起來的 PasswordHash, 公開的介面就用 Password 的 Setter 跟 ComparePassword( ) method 取代,明確的用程式碼告訴所有要用它的 programmer:

"密碼只准你寫,不准你讀 (read only)... 只告訴你密碼對不對, 不會讓你把真正的密碼拿出去"

另一個部份,就是身份證字號跟性別的問題,則改用另一個方式解決。SSN 這個屬性維持不變,在它被更動時就一起更動 GenderCode 這個欄位。GenderCode 完全不對外公開,公開的只有把 int 轉成 GenderCodeEnum 的屬性: Gender。同時為了保護資料的正確性,只開放 Getter, 不開放 Setter。

 

同樣的程式,在我們調整過 Entity 的封裝之後,再來重寫一次看看:

建立新的使用者帳號[copy code]
   1:  // 準備 object context
   2:  using (Membership ctx = new Membership())
   3:  {
   4:      User newUser = new User();
   5:      newUser.ID = "andrew";
   6:      newUser.PasswordHint = "My Password: 12345";
   7:      newUser.Password = "12345";
   8:      newUser.SSN = "A123456789";
   9:      ctx.AddToUserSet(newUser);
  10:      ctx.SaveChanges();
  11:  }

 

 

檢查密碼是否正確[copy code]
   1:  // 準備 object context
   2:  using (Membership ctx = new Membership())
   3:  {
   4:      EntityKey key = new EntityKey("Membership.UserSet", "ID", "andrew");
   5:      User user = ctx.GetObjectByKey(key) as User;
   6:      // 要比對的密碼
   7:      string passwordText = "123456";
   8:      bool isPasswordCorrect = user.ComparePassword(passwordText);
   9:      Console.WriteLine("Password ({0}) check: {1}", passwordText, isPasswordCorrect ? "PASS" : "FAIL");
  10:  }

 

修改過的程式簡潔多了。不過比少打幾行程式碼更重要的是,它的邏輯更清楚,更不容易出錯。如果沒有妥善的處理封裝性的問題,可以想像寫出來的程式一定亂七八糟。要嘛不正確的資料都會被寫進 DB,不然就是 DB 有作適當的防範,但是程式沒有作好,最後就是到處都出現 SqlException ...

這裡只是簡單示範一下 Entity Framework 如何替資料提供封裝的特性,後續的文章會繼續示範 Entity Framework 如何能把 DBMS 的資料,進一步的應用到物件技術的繼承及多型等特性。敬請期待下集 :D



1/21/2009 8:35:27 PM

EF#1. 要學好 Entity Framework? 請先學好 OOP 跟 C# ...

Microsoft.NET | C# | Entity Framework | ORM | 技術隨筆 | 物件導向 Facebook Share

這次為了能順利的學好 Entity Framework,花了不少工夫在研究它的作法。不過有一大半不是在 Entity Framework 本身,而是在 C# 的一些特別的語法跟 LINQ 身上...。也因為這樣,我深切的體認到一個 ORM 技術能不能成功,其實都是在 Hosting 這個 Framework 的環境夠不夠成熟...。

不過在摸索的過程中,找到的資訊都是片斷的,每一篇都是講實作,範例程式,操作步驟... 等等,而當時我最需要的反而是幫助我決定,Entity Framework 到底值不值得我押在上面投資五年開發計劃使用的 ORM 技術? 它跟 NHibernate (考慮中的另一項 ORM framework) 的優缺點為何? 未來發展的優缺點又是什麼? 架構上的差異在那? 另外 Linq to SQL 呢? 這些較偏架構性跟本質的討論及比較資訊,反而少之又少...。

雖然最後還是研究了些心得出來,不過實在是不想寫那些到處都看的到的實作,就來寫點不一樣的吧。第一篇會先寫寫 ORM 的背景知識,還有 Entity Framework 跟 C# 的語法是如何魚幫水,水幫魚,如何解決了過去 ORM 用起來都不大對勁的問題...。

 

繼續長篇大論前,先老王賣瓜一下。雖然我碰過的 ORM framework 不多,不過相關的理論跟技術則碰了不少。撇開大學就在研究的 OOP 不談,研究所的指導教授就從 SmallTalk 開使教... 兩年的專題研究都是 OODB (物件導向資料庫),相關論文也看了一堆。出來工作後又有幸用了幾年的 TAMINO (一套 native xml database), 之後又花了很多時間,在 SQL 2000 上面建立起一套 Object <-> XML <-> Database,類似 ORM 的 Framework ...

不過這麼一路下來,都沒有覺的簡單又可行的方案。除了上面講的是我親自參與過的之外, M$ 其實也發表過幾個類似的技術,像是 Typed DataSet 就是個較接近的產物。 Typed DataSet 其實有點接近現在的 Entity Framework 了。DataSet 就等同於 Entity Container / ObjectContext, DataTable 大致就等同於 EntitySet, 而 DataRow 則等同於 Entity, Relation 則大致等同於 Entity Framework 的 Navigation Property.... 不過用起來還是到處都看的到 DataSet 的影子,感覺血統還不夠純正...

不過現在的 Entity Framework 不一樣了,感覺就已經往實用的領域邁進了一大步! 並不是說 Entity Framework 做的很好 (以成熟度來說, NHibernate 比目前的 Entity Framework 好的多), 而是跟 Entity Framework 搭配的技術都成熟了。一套 ORM 要成功,必要的條件很多啊... 實作上的角度看來,我覺的重要的有這幾項:

  1. 要有優良的 Object / Relationship Mapping 機制、作法、工具等等
  2. Framework 本身的擴充及自訂的能力要夠
  3. 要有效的解決以物件角度思考的查詢 (QUERY) 問題
  4. "物件" 要看起來像 "物件",不是 "資料"
  5. 處理資料庫典型的問題,效能跟便利性不能跟直接操作 DB 差太多
  6. 你的牌子夠不夠響亮... (這是心理因素而已... 哈哈)

這些是深切的體認。不然的話 ORM 的東西跟本不難啊,以功能來說,Typed DataSet 其實就解決一大半實際的問題了。先來看看物件導向幾個關鍵的核心技術是啥?

  1. 封裝 ( Encapsulation ),抽像化型別 (ADT, Abstract Data Type),資料 (Data) 跟行為 (Behavior) 能夠綁在一起
  2. 繼承 ( Inheritance )
  3. 多型 ( Polymorphism )

以這樣 "物件" 的關點來看,M$ 在 Entity Framework 之前的資料庫技術其實都不合格。先來看看資料庫存取技術,如果能搭配這些物件技術,能有什麼樣的改進?

[封裝]
這就沒啥好講的了。物件技術有很好的封裝機制,public / protected / private 等等 scope modifier 就能提供很棒的封裝機制。不過資料庫很難做的好,資料庫的那套頂多叫作安全機制 (security) 或是授權機制 (authorization), 不是封裝 (encapsulation) ... 真正的封裝不是看你是那個帳號決定能不能讀資料? 而是你是那個 SCOPE 的程式,能不能存取封裝起來的內部資訊。DBMS 對於資料的控制能力很有限,不外呼 Key, Constraint, Relationship / Foreign Key 等等。像加解密,正規運算式 (regular expression) 等等,對 DBMS 來說就太複雜了。更複雜的封裝機制單靠 DB 就很不實際... 無奈在沒有 ORM 的前題下,這些問題則是直接曝露在你的程式碼每個地方...。換句話說,如果 ORM 能提供良好的封裝機制,ORM 就能取代掉目前的 Data Access Layer ,成為 APP 存取 DBMS 的主要 API 。

順便吐個苦水,也因為 DBMS 對於資料的控制能力有限,維護的 APP 總是碰到這種問題,就是錯誤的資料總是有辦法鑽進資料庫裡面。不為什麼,只因為 DBMS 本身擋不下來,而 Data Access Layer 又不夠爭氣到足以扛下這重責大任,最後只能靠 APP 自身的開發人員,靠紀律跟自律,還有良心來作好這層把關的動作... -_- 如果有套像樣的 ORM 能夠卡在這個位置,光是資料內容的把關,就是一大進步了。

 

[繼承]
繼承跟資料庫有什麼關係? 其實 ORM 如果能有效的把繼承的功能跟資料庫整合起來,也是很嚇人的。舉例來說,部落格支援文章,相片等等不同的內容,但是它們都要有一致的抽像行為,如新的內容要能夠訂閱 (rss subscription),要能夠有標簽 (tagging) 等等共通的功能,在物件技術我們會很直覺的用繼承來做到。定義 BlogContent 類別,把這些邏輯擺上去。之後再分別衍生出 ArticleContent / PhotoContent 等類別,把差異的實作補上去就完成了。不過同樣的概念別想直接套用在資料庫上,你的腦袋得負責這兩者之間的對應。

懂的這麼多的工程師很難找啊... 去那裡找這種人來寫 APP ? 其實搞懂這些也不難,C++ / C# 在解決這類問題,只是很簡單的利用到 virtual table 就搞定了。換到 DBMS,就把 virtual table 的資料結構套到 database schema 就可以。不過說來簡單,能夠搞懂這些,還能精確的實作出來的人不多... 真的作出來還會被嫌:

"它ㄨ的,誰設計的 table schema ? 亂切一通害我 T-SQL query 這麼難寫..."

嗯,沒事,藉機吐吐苦水。主要要表達的就只有一個,繼承關係要對應到資料庫上面,也是挺麻煩的一件事。Entity Framework / NHibernate 就都提供了三種對應的方法。這三種切割對應的方式,要選那一種? 這又是門學問... Orz, 以後再說。

 

[多型]
這個就更玄了。多型是建立在繼承的基礎上,不管你是什麼類別的 instance, 多型的機制可以在父類別的角度,對所有各種衍生類別的物件,一視同仁的操作。而在這統一的前題下,每種類別的物件又可以一國兩制的各自為政... (咳,這不是政治版...)。這樣的抽像程度就是資料庫遠遠所不及的。延序前面講的部落格內容的例子,你能想像這個 store procedure 該怎麼寫嗎?

"要寫一個 sp_update_blogcontent 的 store procedure, 如果 ID 指向的是 blog, 則要執行更新 HTML 的 code,如果是 photo, 則要更新存放圖檔的 BLOB 欄位..."

天那,在 DB 這個層次,寫這種 CODE 只能用很醜的 IF  ELSE 一層一層堆起來...,跟物件技術比起來,程式碼的描述及抽像化能力實在差太遠,在這層次能解決的問題複雜度很有限...。你如果是個聰明人,最好還是別在 DBMS 搞這些物件技術,會死人的...。比較好的作法是移到 APP 那層去作比較實際。

不錯,ORM 存在的原因又多了一個...。

 

所以,再回頭來看看,ORM真的要發揮它的效益的話,絕對不是只有用 "物件" 來代替 "資料" 而已 (還是老話一句,這樣的話用 Typed DataSet 就夠了)。至少對應出來的 "物件",還能有效的應用到這些物件導向的特性,同時 ORM framework 還能替你維持這些跟資料庫的對應關係,這樣 ORM 技術才能真正發揮它的效益,那些被講到爛的三層式架構才不會在 DBMS 這層就破功了。

來看看比較具體的部份。這些物件技術的特點,C# 早在 2000 年,JAVA 早在 199X 年就有了,沒什麼了不起。不過當年的 ORM 實在難用的很。當時的 OOPL 就是缺了些東西,ORM 的程式寫起來限制一堆... 對應到資料庫的物件,用起來就是跟一般的物件差很多,這也不能用,那也不能用。

現在的 C# 就不一樣了,進化到足以解決這些語言的限制。來看看:

  1. reflection, attribute:
    這個讓物件 (Entity) 可以寫的更簡潔,reflection + attribute 可以解決很多過去得繞一大圈才做的到的事。如 class 對應到那個 table, property 對應到那個 column 等等。
  2. partial class:
    ORM 免不了有些 code generator 的搭配。有 partial class 可以讓程式搭配 code generator 更容易一點。
  3. extension methods:
    現有的物件技術很難讓你在現有的 class 上去作擴充,而 extension methods 可以。
  4. Linq
    這可是一大進步。過去 ORM 的目的就是想把 DB 的細節藏起來,無奈碰到 QUERY 的話什麼都藏不住,往往淪落到要嘛都直接用 SQL, 不然就是只剩幾種基本的 API 可以用,無法完全取代直接用 SQL 的查詢。不過 Linq 出現之後這情況就改觀了,雖然像報表那樣複雜大型的 QUERY 還是得直接下 SQL,不過一般 AP 內的查詢都可以直接用 Linq 搞定了

其它當然還有別的,不過我自己覺的這幾點是關鍵,至少可以讓現在的 Entity Framework 在使用 Entity 時,不會再跟一般的物件有什麼不同。大部份你可以應用在一般物件的技巧,也都能套用在 Entity 身上。第一篇碎碎唸的部份就先寫到這裡。後面會示範一下幾種打造你專屬的 Entity 用到的技巧。想看後面的讀者們請耐心等待 :D



12/7/2008 2:04:10 PM

原來 .NET 早就內建 XmlNodeWriter 了...

Microsoft.NET | C# | XML | 小技巧 | 我的作品 | 技術隨筆 | 物件導向 Facebook Share

最近事情一堆,上班忙上班的事,下班還在忙著研究 Enterprise Library, Entity Framework, 還有一堆五四三的,文章寫的就少了... 先跟有訂閱我 BLOG 的朋友們說聲道歉...。 不過在寫新專案的過程中,意外的發現這東西,一定要提一下...

 

不知道有多少人用過 XmlNodeWriter ? 我用這東西用很久了,當年 Microsoft 推出 .NET Framework 時,強調有很強的 XML 處理能力,其中 XmlReader / XmlWriter 就是以效能為考量,讓你避開處理大型 XML 資料效能很糟糕的 XmlDocument, 也不用去碰很難寫的 SAX 的替代方案...

無奈 M$ 內建的 XmlWriter 少的可憐,只能寫到檔案或是 TextWriter ... 看看權威的 MSDN 告訴我們有那些 XmlWriter 可以用?

image

老實說除了 XmlTextWriter 之外,另外兩個很少用的到。XmlWriter 在輸出 XML 時很好用 (如果你只作輸出的話),複雜的 XML 輸出用 XmlWriter 比用 XmlDocument 簡單多了,不過最常碰到的情況是我還是想用 XmlDocument 來操作 XML,不過其中一部份的 NODE 想用 XmlWriter 來更新內容...

古早有位好心的 MVP 寫了 XmlNodeWriter, 就可以讓我這樣用:

XmlNodeWriter Sample Code:[copy code]
   1:  XmlDocument xdoc = new XmlDocument();
   2:  xdoc.LoadXml("<root><node1><data/><data/><data/></node1><node2/></root>");
   3:  XmlNodeWriter xnw = new XmlNodeWriter(xdoc.DocumentElement, true);
   4:  xnw.WriteStartElement("newNode");
   5:  xnw.WriteAttributeString("newatt", "123");
   6:  xnw.WriteCData("1234567890");
   7:  xnw.WriteEndElement();
   8:  xnw.Close();
   9:  xdoc.Save(Console.Out);

 

第一個參數是 XmlNode, 第二個參數是要不要清掉原來 Node 下的內容。很棒,我可以直接拿 XmlNode 當作 XmlWriter 輸出的對象,透過 Writer 寫出去的東西就直接反映在 XmlNode 身上了,省掉輸出成 Text 然後再 PARSING 回 XML NODE 這種蠢事...

 

前面只是緬懷 XmlNodeWriter 到底有多好用,現在找不到有多難過而已... 接下來才是正題...

 

不過現在想再去找 XmlNodeWriter 官方網站已經找不到了 @_@,原本這 lib 是 hosting 在 gotdotnet.com 這網站上,不過 M$ 已經把它關了,改成 codeplex.com / MSDN Code Gallery 取代,只好求助 GOOGLE 大神,無意間又發現這 M$ XmlTeam 的 BLOGCOMMENTS 有這麼一段:

 

# re: XML Features in the February CTP of Visual Studio “Orcas”
Friday, February 02, 2007 8:27 PM by Stuart Ballard


Is there going to be an XmlNodeWriter in Orcas? It's a fairly glaring hole, especially if you've ever wanted to apply an XSL transformation to an in-memory XmlDocument and get the result as another in-memory XmlDocument. You can pass the input to the transform via XmlNodeReader, but to get it back out again you just have to feed your XmlWriter to a StringBuilder and then parse it...

Fortunately my use case wasn't performance-critical, but it's still ugly...

 

# re: XML Features in the February CTP of Visual Studio “Orcas”
Saturday, February 03, 2007 3:22 AM by Oleg Tkachenko


Stuart, XmlNodeWriter in .NET 2.0 is hiding in

xmlNode.createNavigator().AppendChild() method. It can be used to populate XmlNode via XmlWriter API and so you can

XmlDocument doc = new XmlDocument();

using (XmlWriter writer = doc.CreateNavigator().AppendChild()) {

   xslt.Transform(input, (XsltArgumentList)null, writer);

}

Mike, am I right that  Orcas January CTP includes none of these coolness?

 

真是太機車了,這麼好用的東西藏在這種地方? @_@,枉我從 .NET 1.0 beta 就開始用 C# 處理 XML,連 XSLT Extension 都寫過一堆, Trace Code 也追到 XSLT 內抓過一堆問題... 竟然連這東西都沒發現? 可惡...

於是手又癢了,拿來試用看看,發現只要動手寫幾行 Code, 我就能把 XmlNodeWriter 變回來了,像這樣:

 

我的 XmlNodeWriter 實作[copy code]
   1:  public class XmlNodeWriter : XmlWriter
   2:  {
   3:      private XmlWriter _inner_writer = null;
   4:      public XmlNodeWriter(XmlNode node, bool clean)
   5:      {
   6:          if (clean == true)
   7:          {
   8:              node.RemoveAll();
   9:          }
  10:          this._inner_writer = node.CreateNavigator().AppendChild();
  11:      }
  12:      #region 無聊的 "延長線" 程式碼...
  13:      // 略! 共一百多行,補上廿幾個 abstract method / property, 把它接到 _inner_writer 上
  14:      #endregion
  15:  }

 

這樣果真可以 WORK 了 :D  不過要真正變出一個新的 XmlNodeWriter 代價還不低,繼承 XmlWriter 的後果是有廿幾個 abstract method / property 得補上實作... 全都是很無聊的 code, 就是拿 _inner_writer 的直接套上去而已... 像這樣:

"延長線" 型的程式碼[copy code]
   1:  public override void Close()
   2:  {
   3:      this._inner_writer.Close();
   4:  }
   5:  public override void Flush()
   6:  {
   7:      this._inner_writer.Flush();
   8:  }
   9:  public override string LookupPrefix(string ns)
  10:  {
  11:      return this._inner_writer.LookupPrefix(ns);
  12:  }

 

這堆 Code 我就不貼了,總之可以 WORK :D

 

image

 

不過對 CODE 有點潔癖的我,越看越不是味道,就動起 Factory 的腦筋了。繼續改造一下... 原本 .NET 2.0 內建的 XmlWriter 就已經提供 Factory 的用法了,像這樣:

XmlWriter my_writer = XmlWriter.Create( ... );

不過沒辦法不改 .NET FX 原始碼的情況下 "加掛" 我自己的 Create(...) 實作,原本腦筋是動到 C# 3.0 開始支援的 Extension Method, 不過它只支援 instance method, 不支援 static method ... 只好改成這樣:

 

XmlWriterFactory 實作[copy code]
   1:  public abstract class XmlWriterFactory : XmlWriter
   2:  {
   3:      public static XmlWriter Create(XmlNode node)
   4:      {
   5:          return Create(node, false, null);
   6:      }
   7:      public static XmlWriter Create(XmlNode node, bool clearnContent)
   8:      {
   9:          return Create(node, clearnContent, null);
  10:      }
  11:      public static XmlWriter Create(XmlNode node, bool cleanContent, XmlWriterSettings settings)
  12:      {
  13:          if (node == null) throw new ArgumentNullException("node");
  14:          if (cleanContent == true)
  15:          {
  16:              node.RemoveAll();
  17:          }
  18:          XmlWriter xw = node.CreateNavigator().AppendChild();
  19:          if (settings != null)
  20:          {
  21:              xw = XmlWriter.Create(xw, settings);
  22:          }
  23:          return xw;
  24:      }
  25:  }

 

沒事還繼承原本的 XmlWriter 只有一個目的,就是要延用它原來的 10 種 Create method 啊... 貼張圖為証,繼承之後我就有 13 種不同的 Create method 可以用... 不用再兩頭跑 (只是不能加在原本的 XmlWriter 上真是殘念, C# 什麼時後會支援 static method extension ?):

image

 

 

當然,原程式只要改掉如何拿到 XmlWriter 那行而已,其它都照舊就可以執行了 :D

 

有需要的就拿去用吧,CODE 才十幾行,還包成 DLL 實在太麻煩了,需要的直接貼到你自己的 CODE 裡就好! 要散怖都隨便,沒有什麼授權問題,唯一的要求就是讓我知道我的 CODE 你有在用就好 :D,想讚助我的也很簡單,BLOG 上該多點幾下的東西,沒事就點一點... 哈哈



11/18/2008 1:23:00 AM

Policy Injection Application Block 小發現...

Microsoft.NET | 543 | AOP | Application Block | C# | MSDN | 小技巧 | 技術隨筆 | 物件導向 Facebook Share

因為工作的關係,最近正在研究 Enterprise Library 裡整合的 Patterns & Practices 介紹的各式 Application Block... 撇開其它的發現,有個東西一定要提一下,就是 Policy Injection ...

介紹文章我就不多說了,一樣網路一大堆,有興趣的可以看 MSDN 官方的說明。比較特別的是它的用法。當年剛開始研究 .NET 內建的 Role Based Security Control,才在讚嘆它的 code 寫起來真漂亮,只要加個 attribute, 就可以在 runtime 自動檢查呼叫時的身份是否滿足 attribute 的宣告,如下:

CAS範例程式: [copy code]
[PrincipalPermissionAttribute(SecurityAction.Demand, Role="Supervisor")]public void Foo() {    // ... }
   1:  [PrincipalPermissionAttribute(SecurityAction.Demand, Role="Supervisor")]
   2:  public void Foo() {
   3:      // ... 
   4:  }

 

不管你的 code 在那裡,只要呼叫這個 Foo method, 當時的身份 ( principal ) 如果不屬於 "Supervisor" 這個角色的話,就會引發 Security Exception... 當初看到這真是太棒了,我可以用宣告的方式來作安全控制,不需要在主程式裡加一堆囉哩叭唆的 code 來查權限...

不過當我開始研究如何 "自定" 這個行為,除了加上自己的安全機制之外,想更進一步的加上 Log 或是其它的檢查... 我才發現跟本辦不到。因為... 這行為是直接在 CLR 裡支援的啊,我可以加上一堆自定的 Attribute 掛上去,但是呼叫時完全不會觸發我的 code ...

之後研究過 AOP,發現 AOP 正是解決我這類問題的 Solution, 無奈那些 solution 都不大實際,就沒深入研究了。之後找到篇 MSDN 的文章,裡面提到 .NET Remoting 時,遠方會產生 Proxy, 同時 Client / Server 之間的溝通會介著中間傳輸層傳遞 IMessage 介面封裝的 message, 到另一端才會由 Proxy 解讀,然後用 Reflection 還原呼叫的動作... 利用 Proxy 在還原呼叫動作時,你就有機會插入你要的邏輯 (IMessageSink),做到跟上面例子類似的功能。

 

還是很不實際啊啊啊啊,我沒事也不會去用 .NET Remoting 啊,用不到的話這招對我也沒啥用 (大錯特錯!! 當年的我真是太過自信了 :~~~~) ... 這事就一直擱著了,直到...

最近在研究 Policy Injection Application Block 時,讓我看到了似曾相識的 code:

 

Policy Injection Sample Code #1[copy code]
[AuthorizationCallHandler("operation-name")]public void Deposit(decimal depositAmount){  balance += depositAmount;}
   1:  [AuthorizationCallHandler("operation-name")]
   2:  public void Deposit(decimal depositAmount)
   3:  {
   4:    balance += depositAmount;
   5:  }

 

 

這段 CODE 跟前面 CAS 的範例作用差不多,一樣是在 method 被呼叫前作一次權限的檢查。不同的是 AuthorizationCallHandlerAttribute 是自定的 (由 Security Application Block 提供的),它的作用比 ROLE 更進一階,是直接檢查授權的。之間的差別就如同 windows 大家都知道把 USER 加入 Administrators 角色的話,"預設" 就可以做大部份的事,但是你要在某個有 ACL 的物件 (如 NTFS 的檔案) 拒絕 Administrators 的存取也是可行的。前面 CAS 的例子就只是判定你是不是某角色的人,而這例子則是判定某個授權的定義允不允許你執行。

扯遠了,重點不在安全,重點是自定的 Code / Attribute 也可以這樣用啊! 由於我多年心裡的疑惑,挖出這段作法比研究 Policy Injection 更積極一點 (老闆對不起...) 哈哈,沒想到答案就在前文...

 

 

它ㄨ的!! 原來只是在 Local 使用 .NET Remoting ...

 

 

說穿了不值錢,你用的物件標上 Attribute 後,要透過它的建立方式 ( Create or Wrap ) 取得加料過的物件,再呼叫它就會有你預期的效果了。這加料過的物件,就是 System.Runtime.Remoting.Proxies.RealProxy 下的某類別啊啊啊啊... 意思是我拿這加料過的物件,就會透過 .NET Remoting 的方式去呼叫到我真正的物件,而 Policy Injection Application Block 正好就替我把我要作的動作給補上去...。

雖然心裡有被擺了一道的感覺,不過它的 code 包裝的真漂亮啊... 除了 Create 的方式由原本的 new .ctor( ) 改成它的 Create( ... ) 之外,其它就通通一樣了。更猛的是它還提供了幾個真的很實用的 CallHandler (就是呼叫時會加料的動作啦):

  • Authorization Handler
  • Caching Handler
  • Exception Handling Handler
  • Logging Handler
  • Performance Counter Handler
  • Validation Handler
  • Custom Pipeline Handlers

大部份的 Handlers 都望文生義,像是 Logging 就是呼叫時替你加一段 LOG,而 Performance Counter 則是呼叫時就替你戳一下 windows 內建的 performance counter, 讓你可以透過 performance monitor 看相關統計 (如你的 method 被呼叫過幾次... ),更神奇的是 Caching, 如果你的 method 跑的很慢,加上去之後甚至是 cache 裡已經有了上次的結果,這次呼叫就直接 return 了... (你還記得你寫過多少次資料不在 cache 內就 insert 進去的 code 嗎?) @_@

 

如果你看這篇期望看到啥 Enterprise Library / Policy Injection Application Block 的深入介紹的話,很抱歉... 我還沒那本事,哈哈... 再過陣子研究出心得,可能會寫幾篇吧...。 這類文章如果你不介意看英文的,官方的說明還有 QuickStart 的範例就夠你看了,可以參考看看,我就不獻醜了...。 這篇純粹是為了這 AB 解除了我多年來的遺憾,特地留下篇記念用的... :D



11/3/2008 2:34:00 AM

該如何學好 "寫程式" #5. 善用 TRACE / ASSERT

[精選文章] | 543 | C# | Microsoft.NET | 我的作品 | 技術隨筆 | 物件導向 Facebook Share

哈哈,這篇拖的夠久了 :P

上篇扯太多,寫到一半寫不完就留到這篇了。寫出可靠的程式,這是軟體工程師的基本要求。上篇提到了 TRACE / ASSERT 的應用,來複習一下:

TRACE: 原本是 C 的除錯用巨集,目的是用適合的方式輸出除錯用的訊息,用來跟一般的訊息輸出有所區別。因為用的是不同的方式輸出,可以很容易的統一關掉。隨著工具的進步,輸出的方式也越來越適合除錯,比如輸出到開發工具的除錯視窗,或是輸出成記錄檔等等。

ASSERT: 也是除錯用巨集,它接受一個 bool 參數,輸入值為 TRUE 時一切正常,就像沒呼叫一樣,輸入 FALSE 則會中斷程式,或是輸出顯目的警告訊息。目的在於確保程式的每個步驟情況都如預料般的順利。

這兩個東西從 C 的巨集,衍生出各種語言及環境都有各自的版本。它的目的很簡單,就是 [Writing Solid Code] 裡提到的:

用同一套程式碼,同時維護兩個版本 (RELEASE / DEBUG),讓錯誤自動跑出來

 

雖然這本書提到了不少技巧,正確的應用 TRACE / ASSERT 是最基本的。但是那些細節並不是主要的重點。重點是你在寫 CODE 時有時時刻刻記得要盡量減少 BUG 嗎? 你有正確的擬出對策嗎? 來看看上回最後一段範例程式:

 

加上 ASSERT 的算分程式碼[copy code]
        public static int ComputeQuestionScore(XmlElement quiz_question, XmlElement paper_question)        {            int totalScore = 0;            int itemCount = quiz_question.SelectNodes("item").Count;            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)            {                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;        }
   1:  public static int ComputeQuestionScore(XmlElement quiz_question, XmlElement paper_question)
   2:  {
   3:      int totalScore = 0;
   4:      int itemCount = quiz_question.SelectNodes("item").Count;
   5:      Trace.Assert(quiz_question != null);
   6:      Trace.Assert(paper_question != null);
   7:      Trace.Assert(paper_question.SelectNodes("item").Count == quiz_question.SelectNodes("item").Count);
   8:      //
   9:      //  如果都沒作答, 此題放棄
  10:      //
  11:      if (paper_question.SelectNodes("item[@checked='true']").Count == 0)
  12:      {
  13:          return 0;
  14:      }
  15:      //
  16:      //  題目的配分
  17:      //
  18:      int quiz_score = int.Parse(quiz_question.GetAttribute("score"));
  19:      //
  20:      //  答對一個選項的分數
  21:      //
  22:      int item_score = quiz_score / itemCount;
  23:      for (int itemPos = 0; itemPos < itemCount; itemPos++)
  24:      {
  25:          XmlElement quiz_item = quiz_question.SelectNodes("item")[itemPos] as XmlElement;
  26:          XmlElement paper_item = paper_question.SelectNodes("item")[itemPos] as XmlElement;
  27:          //
  28:          //  算成積
  29:          //
  30:          if (quiz_item.GetAttribute("correct") == paper_item.GetAttribute("checked"))
  31:          {
  32:              totalScore += item_score;
  33:          }
  34:          else
  35:          {
  36:              totalScore -= item_score;
  37:          }
  38:      }
  39:      Trace.Assert(totalScore >= (0 - quiz_score));
  40:      Trace.Assert(totalScore <= quiz_score);
  41:      return totalScore;
  42:  }

 

各位仔細看一下加上 ASSERT 的地方。大家寫程式,通常都是腦袋裡想著 "我要處理什麼問題" ,很少人會去想錯誤處理的部份。沒錯,這部份的確是吃力不討好,以此例來說,光是傳進來的參數就有可能狀況百出了。正常的流程都寫不完了,誰還有力氣去把這些錯誤都擋下來?

不過最容易出錯的地方也在這裡。我常在跟其它工程師說,正確的資料 (參數) 傳進來,本來就應該有正確的答案傳出去。難的是錯誤的資料傳進來,你還得回應 "正確" 的錯誤訊息回去,這才真的是個挑戰。這時 ASSERT 的效果就出來了。你可以把 ASSERT 想像成 "宣告" 的子句。以 line 5 ~ 7 行為例:

確保傳入參數是正確的[copy code]
            Trace.Assert(quiz_question != null);            Trace.Assert(paper_question != null);            Trace.Assert(paper_question.SelectNodes("item").Count == quiz_question.SelectNodes("item").Count);
   1:  Trace.Assert(quiz_question != null);
   2:  Trace.Assert(paper_question != null);
   3:  Trace.Assert(paper_question.SelectNodes("item").Count == quiz_question.SelectNodes("item").Count);

 

這三行看在我眼裡,意思就是:

"這兩個參數不能是 NULL,而且兩個 XML ELEMENT 都要有一樣數量的子節點 (Element),否則就不惜代價警告我"

同樣的,在程式的中間,還有傳回值之前,也都可以用同樣的方式來替你的程式 "把關"。再來看看算完成績後,要把值傳回去之前的 CODE:

確保傳回值的範圍正確的程式碼[copy code]
            Trace.Assert(totalScore >= (0 - quiz_score));            Trace.Assert(totalScore <= quiz_score);                        return totalScore;
   1:  Trace.Assert(totalScore >= (0 - quiz_score));
   2:  Trace.Assert(totalScore <= quiz_score);
   3:  return totalScore;

 

這兩行的意思就是:

"不管成績怎麼算,每張答案卷最後的總分一定介於 0 ~ 滿分之間。一樣,有例外的話就不惜代價警告我"

 

聽起來蠻狠的,不惜代價...,不過使用 ASSERT 的話就真的是這樣。通常碰到 ASSERT 後,程式不是進 DEBUGGER 就是直接關掉了。不過請大家注意一下,並不是到處加上 ASSERT 你的程式就沒問題了。要搞清楚加上它的目的是什麼。它要抓的是你程式的 BUG,不是執行期的錯誤 (比如 USER 輸入錯誤的值,或是必填的資料沒填等等)。執行期的錯誤,你還是得乖乖的寫程式,不能用 ASSERT 替代。

舉例來說,如果最後算出來的分數是負的,則會觸動 return 前的 ASSERT。有些有點經驗又有點兩光的 PROGRAMMER 可能會自己顯示一些錯誤訊息。但是這跟本不干 USER 的事啊! 會出現這種情況,錯的一定是 "程式" 本身,也就是你看到 ASSERT 警告後就該來改程式抓 BUG 了。加上 ASSERT 的目的就是在你的程式到處布下眼線,任何一個地方偵測到不對勁,馬上通知你來處理。

當你有心把程式寫好時,你才會覺的這樣作是必要的,而不是累贅。你眼線布的越多,BUG就越難藏在你的程式裡。相對的,如果傳進來的參數就不對了,那應該怎麼辦?

這時就要小心分清楚你要抓的是 BUG 還是做錯誤處理了。如果參數是 USER 直接輸入的,那收到 NULL 或是錯誤的值本來就有可能 (吃芝蔴那有不掉燒餅的...),你需要的是老老實實寫好錯誤處理的流程。但是如果你的 API 早已嚴格定義不接受 NULL,卻還是有白目的工程師硬把 NULL 傳給你的 API,那這時就是 BUG 了,應該用 ASSERT 抓出來,然後找到冤大頭叫他改程式。

不過這樣的 CODE 可不能交到 USER 手上。想像一下如果你正在用 WORD 打文件,結果碰到一個小 BUG,ASSERT 就跳出警告訊息要中止程式,你連存檔都來不及,大概會抓狂吧。這時就是一份程式碼兩種版本的作法發威的地方了。交給 USER 的程式,就應該是切到 RELEASE MODE (或是關掉 ASSERT / TRACE) 編譯的版本。這時所有的 TRACE / ASSERT 好像完全消失一樣,程式就如同一般情況運作。

當 USER 回報一些很難抓到的 BUG 時,這時就可以打開 ASSERT 或是改用 DEBUG BUILD 的版本,再讓 USER 去重現 BUG,這時如果你都有老老實實加上 ASSERT 的話,BINGO,問題在那就一目了然。看看是那一道 ASSERT 指令被觸發,就知道是什麼問題了。抓 BUG 最麻煩的就是找出錯在那裡,而善用 ASSERT 就可以讓 BUG 自己跳出來告訴你出了什麼問題,只要你養成好習慣。

 

再舉一個應用例。看到 Steve Maguire 先生舉這個例子,真是想拍手叫好。他舉了他們在開發 EXCEL 時的例子。EXCEL就是要替試算表作一堆運算,當年還在 DOS 時代,CPU怎樣都不夠快,RAM怎樣都不夠多,程式設計師無不絞盡腦汁,要榨出所有的運算能力,最佳化做到無所不用其極的地步。不過這種東西是錯不得的啊,少算了一塊錢還得了? 碰到這種問題你該怎麼辦?

通常,我們都會先有個安全的版本,算的不快,但是因為邏輯簡單,比較不容易出錯。這種版本寫出來後才開始想盡辦法,去改善程式讓速度加快。馬先生 (ㄜ... 是馬奎爾先生... ) 就充份應用了 ASSERT,隨時都要把 BUG 逼出來的精神,真的把 "驗算" 的方法應用上來。它的作法很簡單,同一張試算表,用兩份不同的程式碼各計算一次,最後再來比對一下結果 (驗算)。只要兩者得到的答案不一樣,那就是出問題了! 當然也有可能是安全的版本寫錯了,不過你至少多了個機會抓到問題,因為不一樣的話,一定 "至少" 有一邊是錯的!

 

沒有這樣的前題的話,各位看到可能都會在心裡想:

"有沒有搞錯,程式都寫不完了,還要寫兩種演算法來驗算?? 老闆又不會多給我一點薪水..."

沒錯,這的確是成本較高的方法,每套系統應該都有關鑑的地方,只要有絕對不能失誤的地方,就值得用這種作法。速度的問題怎麼辦? 很簡單。你只要在 DEBUG MODE 才啟用這 "驗算" 的機制,測試人員輸入各種數值做黑箱測試,如果每次測試的過程中發現驗算錯誤,則 "黑箱" 測試就能幫助你抓到只有 "白箱" 測試才有可能抓到的 BUG !

 

我寫的這個範例程式 (算成績) 其實也準備了兩個版本。上一篇貼的是基本的作法,結果比較可靠。而為了效率我也寫了另一份程式碼,用的是位元運算,希望藉著位元運算,一次就把多選題的答案給算出來。開發的過程中就用了 ASSERT + 驗算的技巧,它不會加快我寫程式的速度,但是它可以加速我找到 BUG 跟解決 BUG 的時間!

 

有沒有覺的這跟單元測試其實很像? 沒錯。單元測試就是一樣的觀念演變出來的作法,所以你用的單元測試 FRAMEWORK 也延用一樣的 ASSERT 使用慣例。你會發現其實之間的觀念都是相通的,只不過單元測試更進一步的把它系統化了,由原本四處藏在程式碼中的 ASSERT,抽出來成為一個一個獨立的 TEST CASE,由原本被動的執行時期檢查,演變為主動執行所有測試的 UNIT TEST。我覺的 Kent 在 XP (extreme programming) 裡舉了一個例子來說明單元測試,比喻的很貼切,我覺的也一樣能拿來比喻 ASSERT:

 

"車子裝了煞車,是要讓車子能開的更快!"

 

聽起來好像很蠢? 煞車明明是讓車子停下來的... 其實不然。想像一下如果你的車子沒煞車,你敢開多快? 了不起就是撞到不會怎麼樣的速度,或是油門放開就停下來的程度而以。有了煞車讓你有信心,碰到危險時你隨時能把車子停下來,你才敢把車子開上高速公路...

 

很有道理的比喻,ASSERT 跟 UNIT TEST 大部份人都覺的是 "煞車",是拖慢你速度用的,但是也因為有這些 "煞車",你才能放心的衝更快。當你有充份運用 ASSERT 的話,你就能很放心的寫程式,沒有後顧之憂。其實類似的關念,Steve Maguire 的書還有提到很多,只不過它的範例都是用 C 寫的 (還不是 C++ ...),看起來會吃力一點。範例程式可能對現今大部份的人都用不到,但是裡面的觀念跟作法還是很有參考價值的,手上還有這本書的人不妨拿起來翻一翻。

 

講到這裡,花了兩篇才講完第一個部份,主要的重點就是用 TRACE / ASSERT 來說明,要讓你的程式夠穩定,第一個要改進的就是你寫程式的想法,觀念及態度。各位不妨以這兩篇的例子,自己回想看看,你做到那幾項:

  1. 你寫程式有考慮到這些問題嗎?
  2. 如果你寫程式有用這些方法,有多少你曾解過的棘手 BUG 會變的迎刃而解的?
  3. 加上 ASSERT 之後,你是否對你程式更有信心了?
  4. 你是否更認同單元測試的必要了?

 

想法跟觀念有了改變,才有可能開發出優良的軟體。你開始認同這樣的想法了嗎? 恭喜你,你已經跨出第一步了。不過光是 BUG FREE 還不足以成為優秀的軟體工程師,這只是必要條件之一而以。除了把程式寫的 "可靠" 之外,接下來的挑戰是如何把程式寫的 "漂亮" ? 下回要開始來探討如何構思你程式碼的結構。什麼樣的結構,什麼樣的方式去分析你的問題,才寫的出架構漂亮的程式? 別急,請期待續篇 :D

 

 

--

註: 範例程式很多 CODE 被我跳過去了,有興趣的人可以抓回去研究看看... 請點 [這裡] 下載。



10/18/2008 11:53:00 AM

生產者 vs 消費者 - BlockQueue 實作

543 | C# | Threading | 作業系統 | 我的作品 | 技術隨筆 | 物件導向 | Microsoft.NET | [精選文章] Facebook Share

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



10/1/2008 10:43:22 PM

得獎了 :D~~~

Microsoft.NET | 543 | C# | Threading | 小技巧 | 安德魯的當年勇 | 我的作品 | 技術隨筆 | 物件導向 Facebook Share

 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



9/18/2008 3:25:17 AM

[C#: yield return] #1. How It Work ?

Microsoft.NET | Threading | 小技巧 | 技術隨筆 | 物件導向 | C# Facebook Share

C# 常常拿來跟 Java 比較,在 .NET 1.1 時常常是不相上下,而 .NET 又因為較年輕 & 頂著 M$ 的名號,往往被當成玩具一樣,不過 M$ 的確是在 .NET 及 C# 下了很多功夫,作了很多 Sun 不願意在 Java 身上作的事,這次要探討的 yield returnIEnumerable<T> 這搭配的 Interface 就是一例...。

Java 在過去的版本,往往為了跨平台,把修改 VM 規格視為大忌,連帶的連語法修改都一樣,即使不影響編譯出來的 bytecode 相容性也是一樣不肯改。而 .NET 就為了語法簡潔,編譯器往往是讓步的一方,因此 C# 有相當多的 Syntax Sugar,讓你寫起 CODE 爽一點...。你只要寫簡單的 CODE,編譯器會幫你轉成較煩雜的 CODE,有點像是文言文或是成語那樣的味道。古代文人常常用簡單的四個字,就有一大票引申的意義跑出來...,寫作文時只要套上成語,就代表了成語背後的故事,寓意。

"yield return" 算是最甜的甜頭了,因為編譯器替你翻出來的 code 整整一大串。先來看個簡單的例子,如果我想實作 IEnumerator<T> Interface, 照順序輸出 1 ~ 100 的數字,正統的 C# code 看起來要像這樣:

用 IEnumerator 依序傳回 1 ~ 100 的數字[copy code]

   1:  public class EnumSample1 : IEnumerator<int>
   2:  {
   3:      private int _start = 1;
   4:      private int _end = 100;
   5:      private int _current = 0;
   6:      public EnumSample1(int start, int end)
   7:      {
   8:          this._start = start;
   9:          this._end = end;
  10:          this.Reset();
  11:      }
  12:      public int Current
  13:      {
  14:          get { return this._current; }
  15:      }
  16:      public void Dispose()
  17:      {
  18:      }
  19:      object System.Collections.IEnumerator.Current
  20:      {
  21:          get { return this._current; }
  22:      }
  23:      public bool MoveNext()
  24:      {
  25:          this._current++;
  26:          return !(this._current > this._end);
  27:      }
  28:      public void Reset()
  29:      {
  30:          this._current = 0;
  31:      }
  32:  }

 

 

好不容易寫好 IEnumerator 之後,再來是拿來用,一筆一筆印出來:

取得 IEnumerator 物件後,依序取出裡面的數字[copy code]
   1:  EnumSample1 e = new EnumSample1(1, 100);
   2:  while (e.MoveNext())
   3:  {
   4:      Console.WriteLine("Current Number: {0}", e.Current);
   5:  }

 

不過如果只是要列出 1 ~ 100,大部份的人都不會想這樣寫吧? 直接用計概第一堂教你的 loop 不就好了? 程式碼如下:

送分題: 用 LOOP 印出 1 ~ 100 的數字[copy code]
   1:  for (int current = 1; current <= 100; current++)
   2:  {
   3:      Console.WriteLine("Current Number: {0}", current);
   4:  }

 

 

兩個範例都沒錯啊,那為什麼要用 IEnumerator ? 其實 IEnumerator 並不是 Microsoft 發明的,在四人幫寫的經典書籍 (Design Patterns) 裡就有這麼一個設計模式: Iterator,它的目的很明確:

"毋須知曉聚合物件的內部細節,即可依序存取內含的每一個元素。"

(摘自 物件導向設計模式 Design Patterns 中文版,葉秉哲 譯)

這裡指的 "聚合物件" 就是指 .NET 的 Collection, List, Array 等這類物件。意思是你不需要管 collection 裡每一個物件是怎麼擺的,用什麼結構處理的,用什麼邏輯或演算法處理的,我就只管照你安排好的順序一個一個拿出來就好。沒錯,這就是它主要的目的。換另一個說法,就是我們希望把物件巡訪的順序 (iteration) 跟依序拿到物件後要作什麼事 (process) 分開,那你就得參考 Iterator Pattern。不用? 那只好讓你的 iteration / process 混在一起吧。

差別在那? 我們再來看第二個例子。如果題目改一下,要列出 1 ~ 100 的數字,但如果不是 2 的倍數,也不是 3 的倍數,就跳過去。先來看看 Loop 的版本:

進階送分題,用LOOP印出 1~100 之中,2 或 3 的倍數[copy code]
   1:  for (int current = 1; current <= 100; current++)
   2:  {
   3:      bool match = false;
   4:      if (current % 2 == 0) match = true;
   5:      if (current % 3 == 0) match = true;
   6:      if (match == true)
   7:      {
   8:          Console.WriteLine("Current Number: {0}", current);
   9:      }
  10:  }

 

 

再來看看 IEnumerator 的版本:

用 IEnumerator 列出 1 ~ 100 中 2 或 3 的倍數[copy code]
   1:  public class EnumSample2 : IEnumerator<int>
   2:   {
   3:       private int _start = 1;
   4:       private int _end = 100;
   5:       private int _current = 0;
   6:       public EnumSample2(int start, int end)
   7:       {
   8:           this._start = start;
   9:           this._end = end;
  10:           this.Reset();
  11:       }
  12:       public int Current
  13:       {
  14:           get { return this._current; }
  15:       }
  16:       public void Dispose()
  17:       {
  18:       }
  19:       object System.Collections.IEnumerator.Current
  20:       {
  21:           get { return this._current; }
  22:       }
  23:       public bool MoveNext()
  24:       {
  25:           do {
  26:               this._current++;
  27:           } while(this._current %2 > 0 && this._current %3 > 0);
  28:           return !(this._current > this._end);
  29:       }
  30:       public void Reset()
  31:       {
  32:           this._current = 0;
  33:       }
  34:   }

 

 

而扣掉 IEnumerator 的部份,要把數字印出來的程式碼則完全沒有改變:

取出 IEnumerator 的每個數字,印到畫面上[copy code]
   1:  EnumSample2 e = new EnumSample2(1, 100);
   2:  while (e.MoveNext())
   3:  {
   4:      Console.WriteLine("Current Number: {0}", e.Current);
   5:  }

 

可以看的到,Loop 版本的確是把 iteration 跟 process 的 code 完全混在一起了,未來任何一方的邏輯要抽換都很麻煩,而 IEnumerator 則不會,分的很清楚,不過... 這 Code 會不會太 "髒" 了一點啊...? 試問一下,有誰會這麼勤勞,都用 IEnumerator 來寫 Code? 有的話請留個言,讓我崇拜一下...。

 

屁話講了一堆,最後就是要帶出來 "的確有魚與熊掌得兼的方法",怎麼作? 來看看用 C# 的 yield return 版本的程式碼:

傳回 IEnumerable 的 METHOD (不用再寫 CLASS,實作 IEnumerator 了)[copy code]
   1:  public static IEnumerable<int> YieldReturnSample3(int start, int end)
   2:  {
   3:      for (int current = 1; current <= 100; current++)
   4:      {
   5:          bool match = false;
   6:          if (current % 2 == 0) match = true;
   7:          if (current % 3 == 0) match = true;
   8:          if (match == true)
   9:          {
  10:              yield return current;
  11:          }
  12:      }
  13:  }

 

 

用 foreach 搭配 IEnumerable 印出每一筆數字[copy code]
   1:  foreach (int current in YieldReturnSample3(1, 100))
   2:  {
   3:      Console.WriteLine("Current Number: {0}", current);
   4:  }

 

 

 

真是太神奇了,安德魯。如何? 完美的結合兩者的優點,這種 code 實在是令人挑不出什麼缺點... 真是優雅... 不過念過系統程式的人一定都會吶悶... 這樣的程式執行方式,不就完全的違背了一般結構化程式典型的 function call / return 的鐵律了? 程式呼叫某個 function 就應該完全執行完才能 return 啊,怎麼能 "yield" return 後,跑完一圈又回到剛才執行到一半的 function 繼續跑,然後再 "yield" return ? 好像同實有兩段獨立的邏輯在運作... 還可以在兩者之間跳來跳去?

這就是 C# compiler 猛的地方了。搬出 reflector 來看看編譯出來的 code, 再被反組譯回來變成什麼樣子:

 

反組譯 YieldReturnSample3[copy code]
   1:  public static IEnumerable<int> YieldReturnSample3(int start, int end)
   2:  {
   3:      <YieldReturnSample3>d__0 d__ = new <YieldReturnSample3>d__0(-2);
   4:      d__.<>3__start = start;
   5:      d__.<>3__end = end;
   6:      return d__;
   7:  }
   8:   
   9:   

 

耶? 看到一個多出來的 class: <YieldReturnSample3>d__0 ... 再看看它的 class 長啥樣:

編譯器自動產生的 IEnumerator 衍生類別[copy code]
   1:  [CompilerGenerated]
   2:  private sealed class <YieldReturnSample3>d__0 : IEnumerable<int>, IEnumerable, IEnumerator<int>, IEnumerator, IDisposable
   3:  {
   4:      // Fields
   5:      private int <>1__state;
   6:      private int <>2__current;
   7:      public int <>3__end;
   8:      public int <>3__start;
   9:      private int <>l__initialThreadId;
  10:      public int <current>5__1;
  11:      public bool <match>5__2;
  12:      public int end;
  13:      public int start;
  14:   
  15:      // Methods
  16:      [DebuggerHidden]
  17:      public <YieldReturnSample3>d__0(int <>1__state)
  18:      {
  19:          this.<>1__state = <>1__state;
  20:          this.<>l__initialThreadId = Thread.CurrentThread.ManagedThreadId;
  21:      }
  22:   
  23:      private bool MoveNext()
  24:      {
  25:          switch (this.<>1__state)
  26:          {
  27:              case 0:
  28:                  this.<>1__state = -1;
  29:                  this.<current>5__1 = 1;
  30:                  while (this.<current>5__1 <= 100)
  31:                  {
  32:                      this.<match>5__2 = false;
  33:                      if ((this.<current>5__1 % 2) == 0)
  34:                      {
  35:                          this.<match>5__2 = true;
  36:                      }
  37:                      if ((this.<current>5__1 % 3) == 0)
  38:                      {
  39:                          this.<match>5__2 = true;
  40:                      }
  41:                      if (!this.<match>5__2)
  42:                      {
  43:                          goto Label_0098;
  44:                      }
  45:                      this.<>2__current = this.<current>5__1;
  46:                      this.<>1__state = 1;
  47:                      return true;
  48:                  Label_0090:
  49:                      this.<>1__state = -1;
  50:                  Label_0098:
  51:                      this.<current>5__1++;
  52:                  }
  53:                  break;
  54:   
  55:              case 1:
  56:                  goto Label_0090;
  57:          }
  58:          return false;
  59:      }
  60:   
  61:      [DebuggerHidden]
  62:      IEnumerator<int> IEnumerable<int>.GetEnumerator()
  63:      {
  64:          Program.<YieldReturnSample3>d__0 d__;
  65:          if ((Thread.CurrentThread.ManagedThreadId == this.<>l__initialThreadId) && (this.<>1__state == -2))
  66:          {
  67:              this.<>1__state = 0;
  68:              d__ = this;
  69:          }
  70:          else
  71:          {
  72:              d__ = new Program.<YieldReturnSample3>d__0(0);
  73:          }
  74:          d__.start = this.<>3__start;
  75:          d__.end = this.<>3__end;
  76:          return d__;
  77:      }
  78:   
  79:      [DebuggerHidden]
  80:      IEnumerator IEnumerable.GetEnumerator()
  81:      {
  82:          return this.System.Collections.Generic.IEnumerable<System.Int32>.GetEnumerator();
  83:      }
  84:   
  85:      [DebuggerHidden]
  86:      void IEnumerator.Reset()
  87:      {
  88:          throw new NotSupportedException();
  89:      }
  90:   
  91:      void IDisposable.Dispose()
  92:      {
  93:      }
  94:   
  95:      // Properties
  96:      int IEnumerator<int>.Current
  97:      {
  98:          [DebuggerHidden]
  99:          get
 100:          {
 101:              return this.<>2__current;
 102:          }
 103:      }
 104:   
 105:      object IEnumerator.Current
 106:      {
 107:          [DebuggerHidden]
 108:          get
 109:          {
 110:              return this.<>2__current;
 111:          }
 112:      }
 113:  }

 

耶? 不就完全跟之前手工寫的 IEnumerator 一樣嘛? 只不過這個 IEnumerator 是自動產生出來的,不是手寫的...。 畢竟是機器產生的 CODE,總是沒那麼精簡。想到了嗎? 沒錯,這就是 C# compiler 送給你的 syntax sugar ...,你可以腦袋裡想像著計概課入門時教你的 LOOP 那樣簡單的想法,compiler 就幫你換成 IEnumerator 的實作方式,讓你隨隨便便就可以跟別人宣稱:

 

"看! 我的程式有用到 Iterator 這個設計模式喔..."

 

聽起來好像很臭屁的樣子... 哈哈! 如果是在真的用的到 Iterator Patterns 的情況下,真的是可以很臭屁的拿出來炫耀一下。不過,我幹嘛突然講起 yield return ? 各位看的過程中有沒有聯想到前幾篇 POST 講的 Thread Sync 那兩篇文章 ( #1, #2 ) ? IEnumerator 跟 Thread Sync 又有什麼關係? 賣個關子,下篇繼續!



8/22/2008 10:44:53 PM

世紀末軟體革命復刻版

技術隨筆 | 物件導向 | 敗家 Facebook Share

http://www.books.com.tw/exep/prod/booksfile.php?item=0010334718

 

沒想到電腦書也流行復古... 真是令人懷念的一本書啊,電腦書通常都是半年到一年就過時了,堆了兩年以上的書很少還會拿出來翻... 不過這本 (原版,不是復刻版) 例外,足足有好幾年的時間我還是會沒事就拿起來翻一翻。每想到十來年後還會有書局再版... 一定要推一下。

這本書的觀念寫的實在不錯,我有很多OOP的觀念都是靠這本書建立起來的。常常有人問我學物件導向要看那本書,我都很想推這一本,不過早就絕版了那買的到... 前陣子才發現竟然有復刻版... :D

再版的這本書是把原本上下兩冊併在一起,不知道有沒有附當年作者自己寫的 GUI 範例程式? 老實說那個範例程式在當年是蠻猛的,一張磁片就放的下的程式 (還包含 source code),一個像 windows 3.1 的視窗環境,該有的功能一點都不少,你還可以用它的 API 開發在那個 GUI 環境下的應用程式...,不過那個東西實際的用途不大,現在搞不好也沒有環境能跑了,不過看到有人可以用 C++ 建立起像 Windows 3.1 那樣的環境,而且真的可以跑,還真是打從心底佩服...。

技術可能都退流行了,現在流行的東西書上都沒提到,不過觀念的部份還是很實用,想加強自己物件導向觀念的人不要錯過這本書... [Y]



8/15/2008 2:51:00 AM

Thread Sync #2. 實作篇 - 互相等待的兩個執行緒

Microsoft.NET | Threading | 小技巧 | 作業系統 | 技術隨筆 | 物件導向 Facebook Share

上篇有人跟我講太深奧了... Orz, 其實不會,只是還沒看到 Code 而以...。就先來幫黑暗魔人賽說明一下程式碼...。首先來看的是黑暗大魔王: GameHost..

 

GameHost 呼叫 Player 的片段[copy code]
    public void Start(Player p)    {        // 略...        int[] guess = p.StartGuess(_maxNum, _digits);        // 略...        Hint hint = compare(guess);        // 略...        while (hint.A != _digits)        {            // 略...            guess = p.GuessNext(hint);            // 略...            hint = compare(guess);        }        p.Stop();        // 略...    }
   1:  public void Start(Player p)
   2:  {
   3:      // 略...
   4:      int[] guess = p.StartGuess(_maxNum, _digits);
   5:      // 略...
   6:      Hint hint = compare(guess);
   7:      // 略...
   8:      while (hint.A != _digits)
   9:      {
  10:          // 略...
  11:          guess = p.GuessNext(hint);
  12:          // 略...
  13:          hint = compare(guess);
  14:      }
  15:      p.Stop();
  16:      // 略...
  17:  }

 

這段程式完全是老闆的角度在思考。抓到 PLAYER 後就叫它開始猜 StartGuess(),然後拼命的叫 PLAYER 再猜 GuessNext(), 直到猜中才可以休息 Stop()

很典型的多型 ( Polymorphism ) 應用,實際上會 RUN 什麼 CODE,就看繼承 PLAYER 的人是怎麼寫的...。這次我們再從弱勢勞工的角度來看看 PLAYER 該怎麼實作 (以 darkthread 附的 DummyPlayer 為例):

 

Player 實作的範例 ( DummyPlayer )[copy code]
public class DummyPlayer : Player{    private int[] _currAnswer = null;    private Random _rnd = new Random();    private void randomGuess()    {        List<int> lst = new List<int>();        for (int i = 0; i < _digits; i++)        {            int r = _rnd.Next(_maxNum);            while (lst.Contains(r))                r = _rnd.Next(_maxNum);            lst.Add(r);            _currAnswer[i] = r;        }    }    public override int[] StartGuess(int maxNum, int digits)    {        base.StartGuess(maxNum, digits);        _currAnswer = new int[digits];        randomGuess();        return _currAnswer;    }    public override int[] GuessNext(Hint lastHint)    {        randomGuess();        return _currAnswer;    }}
   1:  public class DummyPlayer : Player
   2:  {
   3:      private int[] _currAnswer = null;
   4:      private Random _rnd = new Random();
   5:   
   6:      private void randomGuess()
   7:      {
   8:          List<int> lst = new List<int>();
   9:          for (int i = 0; i < _digits; i++)
  10:          {
  11:              int r = _rnd.Next(_maxNum);
  12:              while (lst.Contains(r))
  13:                  r = _rnd.Next(_maxNum);
  14:              lst.Add(r);
  15:              _currAnswer[i] = r;
  16:          }
  17:      }
  18:   
  19:      public override int[] StartGuess(int maxNum, int digits)
  20:      {
  21:          base.StartGuess(maxNum, digits);
  22:          _currAnswer = new int[digits];
  23:          randomGuess();
  24:          return _currAnswer;
  25:      }
  26:      public override int[] GuessNext(Hint lastHint)
  27:      {
  28:          randomGuess();
  29:          return _currAnswer;
  30:      }
  31:  }

 

因為 CODE 不多,我就不刪了,全文照貼。另一個原因是我想讓各位看看拆成好幾段的 CODE 是不是還能夠一眼就還原成原來的邏輯?  如果只看這段 CODE 十秒鐘,沒有看註解或說明,誰能馬上回答這段 CODE 解題的邏輯是什麼?

 

別誤會,不是指這 CODE 不易讀,而是因為呼叫的方式邏輯被迫配合 GameHost 而被切散了,你得再重新把它拼湊起來。它的邏輯很簡單,甚至簡單到連問題的答案都被忽略掉了,不過就每次都隨機丟個數字回去,在 StartGuess( ) 及 GuessNext( ) 都是。

 

 

可憐的勞動階級要站起來啊~ 先幻想一下,如果勞工 (PLAYER) 才是老闆,那麼程式可以改成怎麼樣? 這也才是我們本篇的主角。先來看看成果再回頭來看怎麼實作。這次看的是修改後的版本: AsyncDummyPlayer.

 

換 PLAYER 的角度思考的邏輯: AsyncDummyPlayer[copy code]
    public class AsyncDummyPlayer : AsyncPlayer    {        private int[] _currAnswer = null;        private Random _rnd = new Random();        private void randomGuess()        {            List<int> lst = new List<int>();            for (int i = 0; i < _digits; i++)            {                int r = _rnd.Next(_maxNum);                while (lst.Contains(r))                    r = _rnd.Next(_maxNum);                lst.Add(r);                _currAnswer[i] = r;            }        }        protected override void Init(int maxNum, int digits)        {            _currAnswer = new int[digits];        }        protected override void Think()        {            while (true)            {                this.randomGuess();                Hint h = this.GameHost_AskQuestion(this._currAnswer);                if (h.A == this._digits) break;            }        }    }
   1:  public class AsyncDummyPlayer : AsyncPlayer
   2:  {
   3:      private int[] _currAnswer = null;
   4:      private Random _rnd = new Random();
   5:      private void randomGuess()
   6:      {
   7:          List<int> lst = new List<int>();
   8:          for (int i = 0; i < _digits; i++)
   9:          {
  10:              int r = _rnd.Next(_maxNum);
  11:              while (lst.Contains(r))
  12:                  r = _rnd.Next(_maxNum);
  13:              lst.Add(r);
  14:              _currAnswer[i] = r;
  15:          }
  16:      }
  17:      protected override void Init(int maxNum, int digits)
  18:      {
  19:          _currAnswer = new int[digits];
  20:      }
  21:      protected override void Think()
  22:      {
  23:          while (true)
  24:          {
  25:              this.randomGuess();
  26:              Hint h = this.GameHost_AskQuestion(this._currAnswer);
  27:              if (h.A == this._digits) break;
  28:          }
  29:      }
  30:  }

 

程式碼也沒比較少,都差不多。不過是那堆 CODE 換個地方擺而以。但是仔細看看,這個版本的邏輯清楚多了,PLAYER 一開始就是執行 Init( ) 的部份,而 GameHost 叫 Player 開始解題時, Player 就開始思考 (Think),而這個無腦的 Player 也很直接,就一直執行 while (true) { .... } 這個無窮迴圈,直到亂猜猜中為止。

如果 Player 在思考的時,不管在那裡它都可以適時的呼叫 GameHost_AskQuestion( .... ) 來跟 GameHost 問答案。什麼時後該猜數字? 該猜什麼數字? 這正是整個 Player 的核心,也就是 "怎麼猜" 這件事。以人的思考方式一定會分階段,比如一開始先把所有數字猜一輪,有個概念後再想想怎麼猜能更逼近答案,最後才是致命的一擊,找出正確答案送出去,贏得比賽。

這樣的作法,如果套在 DummyPlayer (原版本),每個階段都要塞在一個大的 switch case, 放在 GuessNext( ) 裡。而現在是那個階段? 只能靠 instance variable 了,先存著等到下次又被呼叫時再拿出來回想一下,上回作到那...。

而第二個版本,則完全沒這個問題,就把它當作一般程式思考就夠了,第一階段就是一個 LOOP,有它自己用的一些變數。第一階段處理完畢就離開 LOOP 繼續執行後面的 CODE... 直到最後離開 Think( ) 這個 method (認輸) 或是猜中答案光榮返鄉...。

 

 

兩者的差別看出來了嗎? DummyPlayer 像是被動的勞工,老闆說一動他就作一動。第一動作完就拿個筆計記下來,等著下次老闆再叫他,他就翻翻筆記看看之前做到那,這次繼續...。

而 AsyncDummyPlayer 這個主動的勞工呢? 老闆交待給他一件任務後,他就自己思考起該怎麼做了。中間都不需要老闆下令。反而是過程中勞工需要老闆的協助時,老闆再適時伸出援手就可以了,一切雜務都由這位主動優秀的勞工自己處理掉。

 

 

 

有沒有差這麼多? 這麼神奇? 是怎麼辦到的? 先來看看類別關系圖:

ThreadSync

 

上圖中,AsyncPlayer 就是改變這種型態的關鍵類別。AsyncPlayer 會用我們在上一篇講到的關念,化被動為主動,轉換這兩種呼叫模式。先來看看這個類別的程式碼到底變了什麼把戲,可以讓弱勢的勞工也有自主的權力?

 

 

 

 

AsyncPlayer 實作: 化被動為主動[copy code]
    public abstract class AsyncPlayer : Player    {        public override int[] StartGuess(int maxNum, int digits)        {            base.StartGuess(maxNum, digits);            Thread thinkThread = new Thread(this.ThinkCaller);            thinkThread.Start();                        this._host_return.WaitOne();            return this._temp_number;        }        public override int[] GuessNext(Hint lastHint)        {            this._temp_hint = lastHint;            this._host_call.Set();            this._host_return.WaitOne();            return this._temp_number;        }        public override void Stop()        {            base.Stop();            this._temp_hint = new Hint(this._digits, 0);            this._host_call.Set();            this._host_end.WaitOne();            this._host_complete = true;        }        private void ThinkCaller()        {            try            {                this.Init(this._maxNum, this._digits);                this.Think();            }            catch (Exception ex)            {                Console.WriteLine("Player Exception: {0}", ex);            }            finally            {                this._host_end.Set();            }        }        protected abstract void Init(int maxNum, int digits);        protected abstract void Think();        private AutoResetEvent _host_call = new AutoResetEvent(false);        private AutoResetEvent _host_return = new AutoResetEvent(false);        private AutoResetEvent _host_end = new AutoResetEvent(false);        private bool _host_complete = false;        private int[] _temp_number;        private Hint _temp_hint;        protected Hint GameHost_AskQuestion(int[] number)        {            if (this._host_complete == true) throw new InvalidOperationException("GameHost stopped!");            lock (this)            {                try                {                    this._temp_number = number;                    this._host_return.Set();                    this._host_call.WaitOne();                    return this._temp_hint;                }                finally {                    this._temp_number = null;                    this._temp_hint = new Hint(-1, -1);                }            }        }    }
   1:  public abstract class AsyncPlayer : Player
   2:  {
   3:      public override int[] StartGuess(int maxNum, int digits)
   4:      {
   5:          base.StartGuess(maxNum, digits);
   6:          Thread thinkThread = new Thread(this.ThinkCaller);
   7:          thinkThread.Start();
   8:          this._host_return.WaitOne();
   9:          return this._temp_number;
  10:      }
  11:      public override int[] GuessNext(Hint lastHint)
  12:      {
  13:          this._temp_hint = lastHint;
  14:          this._host_call.Set();
  15:          this._host_return.WaitOne();
  16:          return this._temp_number;
  17:      }
  18:      public override void Stop()
  19:      {
  20:          base.Stop();
  21:          this._temp_hint = new Hint(this._digits, 0);
  22:          this._host_call.Set();
  23:          this._host_end.WaitOne();
  24:          this._host_complete = true;
  25:      }
  26:      private void ThinkCaller()
  27:      {
  28:          try
  29:          {
  30:              this.Init(this._maxNum, this._digits);
  31:              this.Think();
  32:          }
  33:          catch (Exception ex)
  34:          {
  35:              Console.WriteLine("Player Exception: {0}", ex);
  36:          }
  37:          finally
  38:          {
  39:              this._host_end.Set();
  40:          }
  41:      }
  42:      protected abstract void Init(int maxNum, int digits);
  43:      protected abstract void Think();
  44:      private AutoResetEvent _host_call = new AutoResetEvent(false);
  45:      private AutoResetEvent _host_return = new AutoResetEvent(false);
  46:      private AutoResetEvent _host_end = new AutoResetEvent(false);
  47:      private bool _host_complete = false;
  48:      private int[] _temp_number;
  49:      private Hint _temp_hint;
  50:      protected Hint GameHost_AskQuestion(int[] number)
  51:      {
  52:          if (this._host_complete == true) throw new InvalidOperationException("GameHost stopped!");
  53:          lock (this)
  54:          {
  55:              try
  56:              {
  57:                  this._temp_number = number;
  58:                  this._host_return.Set();
  59:                  this._host_call.WaitOne();
  60:                  return this._temp_hint;
  61:              }
  62:              finally {
  63:                  this._temp_number = null;
  64:                  this._temp_hint = new Hint(-1, -1);
  65:              }
  66:          }
  67:      }
  68:  }

 

這段程式碼長了一點,內容也都刪不得,各位請耐心點看。上一篇我畫了張概念性的時序圖,這次我們再拿同一張圖,不過這次會標上程式碼:

 ThreadSync2

 

 

請注意一下各個箭頭的上下順序。由上往下代表時間的進行,如果應該在後面執行的 CODE 不巧先被呼叫了,則動作較快的那個 THREAD 會被迫暫停,等待另一邊的進度跟上。先來看看 StartGuess( ) 怎麼跟 Think( ) 互動:

StartGuess(...)[copy code]
        public override int[] StartGuess(int maxNum, int digits)        {            base.StartGuess(maxNum, digits);            Thread thinkThread = new Thread(this.ThinkCaller);            thinkThread.Start();                        this._host_return.WaitOne();            return this._temp_number;        }
   1:  public override int[] StartGuess(int maxNum, int digits)
   2:  {
   3:      base.StartGuess(maxNum, digits);
   4:      Thread thinkThread = new Thread(this.ThinkCaller);
   5:      thinkThread.Start();
   6:      this._host_return.WaitOne();
   7:      return this._temp_number;
   8:  }

 

GameHost 呼叫 Player.StartGuess( ) 有兩個目的,一個是給 Player 題目範圍,讓 Player 做好準備動作。另一個則是準備好之後 GameHost 要取得 Player 傳回的第一個問題。

程式碼很忠實的做了一樣的事,只不過 StartGuess( ) 建立了新的執行緒來負責。新的執行緒會執行 ThinkCaller( ),啟動之後 GameHost 這邊就什麼都不作,等待 _host_return 這個 WaitHandle 被叫醒,代表另一邊已經做好了,可以從共用變數 _temp_number 取得問題傳回去。

既然 GameHost 在等待某人通知它,我們就來看看是誰會通知他題目已經準備好了:

 

GameHost_AskQuestion(...)[copy code]
        protected Hint GameHost_AskQuestion(int[] number)        {            if (this._host_complete == true) throw new InvalidOperationException("GameHost stopped!");            lock (this)            {                try                {                    this._temp_number = number;                    this._host_return.Set();                    this._host_call.WaitOne();                    return this._temp_hint;                }                finally {                    this._temp_number = null;                    this._temp_hint = new Hint(-1, -1);                }            }        }
   1:  protected Hint GameHost_AskQuestion(int[] number)
   2:  {
   3:      if (this._host_complete == true) throw new InvalidOperationException("GameHost stopped!");
   4:      lock (this)
   5:      {
   6:          try
   7:          {
   8:              this._temp_number = number;
   9:              this._host_return.Set();
  10:              this._host_call.WaitOne();
  11:              return this._temp_hint;
  12:          }
  13:          finally {
  14:              this._temp_number = null;
  15:              this._temp_hint = new Hint(-1, -1);
  16:          }
  17:      }
  18:  }

 

就在 GameHost 正在等題目的時後,另一個執行緒正在進行 "思考" 的動作,直到有結論後會呼叫 GameHost_AskQuestion( ... ) 送出問題。這時這個問題會被放到 _temp_number, 而下一步就是 _host_return.Set( ), 通知另一個執行緒,正在等這個結果的人: "喂! 東西已經準備好了,可以來取貨了!!"

整個機制就這樣串起來了。GameHost 那邊怎麼把答案傳回來? 同樣的作法,反過來而以。GameHost 會藉著呼叫 Player.GuessNext(...) 把答案傳回來,而這時就觸動一樣的機制,讓另一邊 Player Thread 呼叫的 GameHost_AskQuestion( ... ) 醒過來,把答案拿走, RETURN 回去。

這樣一直重複下去,剩下最後一個同步的點,就是結束遊戲的地方。說穿了也是一樣的把戲,只是這次是藉著 GameHost 呼叫 Player.Stop( ),而另一邊 Player Thread 執行完 Think( ) 後,兩邊就一起結束遊戲了。

 

總算講完了。其實 thread 能解決的問題還真是五花八門。每次當我想出這些方法來簡化問題時,我就會覺的很有成就感。雖然寫出這個不會讓我贏得比賽,反而因為同步的關係,AsyncDummyPlayer 執行的速度還遠遠落後 DummyPlayer (我的機器跑起來,大概差了四~五倍 ...) 。不過我知道我簡單的頭腦,不先把問題簡化的話,我大概解決不了太複雜的問題...。也許是缺了這種能力,才讓我更有動力去想簡化問題的方式吧?

 

最後,為什麼每次講到 thread 的文章,都是 code 一點點,文章跟圖一大堆? 咳咳... 難道我也到了靠一張嘴混日子的地步了嘛? Orz... 本系列到此結束,以後還會有什麼主題? 想到再說啦~~ 今天各位記得去拜拜~~ 下回見!



8/14/2008 3:37:00 AM

Thread Sync #1. 概念篇 - 如何化被動為主動?

Microsoft.NET | Threading | 技術隨筆 | 物件導向 Facebook Share

別以為我轉行了... 這篇不是勵志文章,教你用主動積極的態度面對人生.... 而是討論執行緒同步機制及如何用來解決惱人的流程問題。會寫這篇的念頭來自黑暗程式魔人辦的猜數字程式設計大賽,在處理的過程中想到的解法...,不過這篇要講的不是猜數字,而是不相干的東西: Thread Sync (執行緒的同步機制)。

 

一般程式寫久了,會很習慣一路到底的思考方式,程式也完全照這樣的思路被設計出來。不過寫 GAME 這類的程式就不是這麼一回事了。就先舉十五年前我用 C 寫的俄羅斯方塊的遊戲當例子 (大驚! 十... 十五年?),腦袋裡想的流程八九不離十,一定是像這樣:

"隨機從上面掉一個方塊下來,時間到了就往下掉,USER有按方向鍵就左右移動或是旋轉,直到卡到底下或是其它方塊為止..."

很正確的想法,很可惜你的程式完全不能這樣寫,為什麼? 當你沒有使用多執行緒或是其它的技巧時,你的主程式流程一定得被限定在固定時間 refresh 畫面的無窮迴圈... 上面的邏輯怎麼辦? 會被迫拆成好幾塊,然後被主程式定期呼叫... 程式寫起來大概會像這樣:

TETRIS
   1:  public void ProcessBrick()
   2:  {
   3:      switch (status)
   4:      {
   5:          case 1:
   6:              //
   7:              //  按右鍵, 往右移一格
   8:              //
   9:              break;
  10:          case 2:
  11:              //
  12:              //  按左鍵, 往左移一格
  13:              //
  14:              break;
  15:          case 3:
  16:              //
  17:              //  按上鍵, 順時針旋轉 90 度
  18:              //
  19:              break;
  20:          case 4:
  21:              //
  22:              //  按下鍵, 往下移一格
  23:              //
  24:              break;
  25:          case 5:
  26:              //
  27:              //  .......
  28:              //
  29:              break;
  30:      }
  31:  }

 

原本好好的邏輯被切成好幾塊,然後再藉著狀態等資訊,每次的 LOOP 各挑這次要執行的那一小段,然後拼湊出原本的邏輯...。別哀怨,誰叫你寫的 CODE 不是老大? 老大是控制畫面的主程式,你既然是當小的就乖乖躲在旁邊被呼叫... 委屈一點是應該的...。

 

真是黑心啊... 誰叫老闆永遠是對的。這次黑心... 不,黑暗魔人出的題目正好又讓我聯想到一樣的狀況。黑暗魔人出的題目,是先實作了 GameHost 類別 (就是老大啦),及 Player 抽象型別 (小角色就是他),再藉著多型 (Polymorphism) 的方式,由 GameHost 不斷的呼叫 Player 提供的 GuessNum( ),來讓 Player 問問題,同時把上一次問題的答案傳給 Player ...

 

程式也不難寫,大家都玩過 1A1B 的遊戲吧? 腦袋裡一定是這樣想的:

 

"一開始先隨便猜幾個,把結果記下來....。"

"再來刪去法,比較可能的幾個數字再猜一猜...。"

"快猜到了,幾種組合列出來想一想怎麼辦好? 好! 就猜這個...。"

...

...

...

"BINGO! 猜中了!!!"

 

很高興的想好流程後,真的要開始寫就傻住了... 這堆流程跟邏輯,要我拆成一直會被重複呼叫的 "單一個" method, 每一回合會被呼叫一次...。意思是一連串複雜的處理過程,要依序切成完全一樣的片段 (就是指重複呼叫同一段程式碼) ? 更慘的是這次問的問題,下一次呼叫才拿的到答案!? MY GOD... 要想出怎麼猜到對方的數字已經夠頭痛了,還得來處理這些 "行政" 問題?

 

My God, 頭越想越痛,這樣下去來我大概只能寫出比 DummyPlayer (註: 參賽程式附的 Player 範例,隨機產生問題,無腦的一直問,直到猜中為止...) 高明一點點的程式而已了。曾 MSN 跟黑暗魔人討論過,看看能不能讓 GameHost 化主動為被動,改由 GameHost 提供 callback 讓 Player 呼叫的可能性? 不過後來想想不對,那有主持人在旁邊看等著被來賓訪問的道理? 何況如果以後是兩個 Player 對戰怎麼辦? 誰要來當 "小的" ?? 問題還是一樣沒解決...

 

過去大家對於 THREAD 的印象都是 "多工",需要用 thread 解決的問題大多是在改善執行效能上面,因為同時用兩個 thread 可以做兩件事,效率會比較好。其實 thread 也很適合解決這類的問題,因為執行緒讓我們有機會,不需切斷 GameHost / Player 的 "思路",讓兩邊都能用很直覺的思考方式寫程式。

 

大概畫一下時序圖對照一下,先看看原本的作法:

投影片2

 

 

 

 

再看一下改用兩個執行緒的作法:

投影片3

 

 

不管之中的技術障礙怎麼克服,至少這樣改起來,兩邊都能各自用更合理簡單的方式思考自己的問題,也更接近實際的情況 (莊家跟玩家不會共用一個腦子吧...)。也唯有把問題簡化之後,我們才有辦法想出更複雜的方式來解決問題,科技不就是這樣進步的嘛?

 

這次的例子裡,執行緒是用來簡化問題的,而不是拿來增進效率的。兩個人腦袋各自想著問題,總要溝通吧? thread 之間溝通的機制就很單純了,共用變數加上同步機制,來確定對方是否準備好我要的東西,或是對方是否已經準備好要接招了?

 

這次搬出來的是過去說明 thread pool 提到的 AutoResetEvent,現在又重現江湖了。方法很簡單,要拿資料的那一方,就去 Wait( ) 等資料準備好,另一方把資料放在共用變數之後就呼叫 Set( ),叫醒另一個還在 Wait( ) 的執行緒,可以起床拿東西閃人了...。

 

接下來當然就各忙各的,直到雙方又有交換資料的需求,同樣的方式就再來一次。只是隨著資料交換的方向不同 (比如問問題是把題目由 player --> host,而取得答案則是 host --> player),上述的動作雙方角色要互換才能順利進行。

 

Orz,本來想一篇打完的,不過打到快睡著,加上內容還剩不少... 就分兩集吧! 程式碼及實作各位就耐心點,下一篇會端出實際操作執行緒的範例。






精選文章

RUN! PC 文章及範例下載
2008/11. 生產線模式的多執行緒應用
2008/09. 用ThreadPool發揮CPU運算能力
2008/06. SEMAPHORE在ASP.NET的應用
2008/04. 以ASP.NET開發同步WEB應用程式

如何學好 "寫程式" 系列
#1. 該如何學好 "寫程式" ??
#2. 為什麼 programmer 該學資料結構 ??
#3. 進階應用 - 資料結構 + 問題分析
#4. 你的程式夠 "可靠" 嗎?

#5. 善用 TRACE / ASSERT

安德魯是誰?

Andrew Wu | Create Your Badge

我喜歡鑽研物件導向、軟體工程及作業系統等相關技術。我會在這裡發表我的研究心得,也當作我自己的學習筆記。


Recent comments

Comment RSS