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

    接續前文:

    1. 該如何學好 "寫程式" ??
    2. 該如何學好 "寫程式" #2. 為什麼 programmer 該學資料結構 ??
    這類文章還真不好寫,想了好幾天,才擠的出一篇文章。第一篇已經講了一堆教條了,第二篇也舉了簡單的例子,說明挑對資料結構的重要性,接下來這篇會把主題放在更複雜的例子上,到底那些地方該注重技術,而那些地方該把重點放在基礎的資料結構及演算法身上。 這次不囉唆半天了,先來回顧一下第一篇,我出的題目是這樣: 以台灣高速公路為題 (中山高、北二高、國道二號),你有辦法寫程式,讓使用者指定起點跟終點的交流道,然後替它找出建議的路線嗎? (把延路經過的交流到跟收費站列出來就好)。 舉這個題目,是怕前面的例子被嫌太簡單,一點都不能符合實際的情況。沒錯,絕大部份的情況都不會像上一篇的範例一樣,放一堆資料在記憶體裡 SEARCH 出來就了事那麼簡單。高速公路的問題核心一樣是在資料結構,不過這次多了必需自己實作的演算法。 跟我一樣五六年級的人,都聽過這句話吧,PASCAL 之父 (Niklaus Wirth) 講的這句名言: "程式 = 資料結構+演算法",沒錯,這個範例就需要用到這兩種能力才搞的定。依我的看法,解決這問題有三道關卡要闖:
    1. 你該用什麼樣的方式來儲存這樣的地圖資訊? 這裡會用到的知識,是資料結構裡的 GRAPH,典型的方法就是分成點跟線來記錄..
    2. 你該用什麼樣的演算法,找出你要的最佳路線? 最基本的是要找出所有可走的路線 (走迷宮),再找出其中最便宜的一條路。
    3. 你的程式的結構該如何設計? 這部份跟課本比較無關,講的是你對程式語言及可用的函式庫/工具的掌握,還有架構等等。
    這三道關卡,要依序破解,前一關的決定會影響到後面的解決方式。先從資料來說,連該怎麼記錄這些資料,就別想解題了。最基本的 GRAPH 需要點 (NODE) 及點跟點之間的連線 (LINK) 組成。很直覺的就可以定出這兩個類別:
    描述交流道/收費站的 class[copy code]
    public class Node
    {
        public string Name = null;
        public int TollFee = 0;
        public List<Link> Links = new List<Link>();
        public Node(string name, int tollFee)
        {
            this.Name = name;
            this.TollFee = tollFee;
        }
    }
     
    描述兩個點之間的路段 (Link) 的 class[copy code]
    public class Link
    {
        public double Distance = 0D;
        public Node FromNode = null;
        public Node ToNode = null;
        public RoadNameEnum Road;
        public Link(Node from, Node to, double distance, RoadNameEnum road)
        {
            this.FromNode = from;
            this.ToNode = to;
            this.Distance = distance;
            this.Road = road;
        }
        public enum RoadNameEnum
        {
            Highway1,
            Highway2,
            Highway3
        }
    }
     
    好像沒什麼特別的,每個點除了搭配 List<Link> 來記錄所有經過它的路段 (Node.Links) 之外,也標上了這個點的名字 (Node.Name),跟過路費 (Node.TollFee)。而每個路段則記錄了它兩個端點 (Link.FromNode, Link.ToNode) 之外,也額外記錄了路段的距離 (Node.Distance),及它是屬於那一條高速公路的資訊 (Link.Road)。 接下來就要載入資料了。我偷個懶,只記中山高跟北二高新竹以北的部份,還有機場國道。實在是沒力氣把全部的路段打完... 哈哈。資料來源是參考國道高速公路局的網頁。以下是 Map 類別的部份程式碼,及載入部份地圖資訊的程式碼:
    MAP[copy code]
    public class Map
    {
        private Dictionary<string, Node> _nodes = new Dictionary<string, Node>();
        public Map()
        {
            //
            //  construct / load map data
            //
            this.AddNode("基金", 0);
            this.AddNode("七堵收費站", 40);
            this.AddNode("汐止系統", 0);
            this.AddNode("樹林收費站", 40);
            // 略
            this.AddLink("基金", "七堵收費站", 4.9-0, Link.RoadNameEnum.Highway3);
            this.AddLink("七堵收費站", "汐止系統", 10.9-4.9, Link.RoadNameEnum.Highway3);
            // 略
        }
        private void AddNode(string name, int tollFee)
        {
            Node n = new Node(name, tollFee);
            this._nodes.Add(name, n);
        }
        private void AddLink(string n1, string n2, double distance, Link.RoadNameEnum road)
        {
            Node node1 = this._nodes[n1];
            Node node2 = this._nodes[n2];
            Link link = new Link(this._nodes[n1], this._nodes[n2], distance, road);
            node1.Links.Add(link);
            node2.Links.Add(link);
        }
        public Link FindLink(string name1, string name2)
        {
            foreach (Link way in this._nodes[name1].Links)
            {
                if (way.GetOtherNodeName(name1) == name2) return way;
            }
            return null;
        }
    }
     
    第一步準備動作完成了。接下來就是想辦法在 class Map 裡加上 FindBestWay( ) method, 來找出最佳路線。在這邊先定義一下什麼叫最佳路線。一般不外乎是找最短的路線,或是通過最少的收費站,我們來點實際的,以油價每公升 30 元為例,車子就假設一公升可以跑 15 公里好了,因此每跑一公里要花兩塊錢。最佳路逕就是花的油錢跟過路費最少的為準。
    沒唸過資料結構的朋友們,現在大概卡住了。該怎樣找出最佳的路逕? 電腦什麼不行,就是計算很快,這種最佳解的問題,通常都可以用暴力法解決。只要把所有的路線找出來,然後找出總花費最便宜的那個路線就好。雖然資料結構的書通常會舉其它更有效率的演算法,其中一個演算法的名字我不記得了,大致的步驟是由起點開始往外擴散,先算走一步可以走到那些點,再往外推,如果到同一點有兩條以上的路線,就保留便宜的那個... 直到推到終點為止。 不過這方法寫起來比較麻煩,我挑另一個簡單一點的 (相對的比較沒效率),就是搭配 STACK 走迷宮的方法,把所有路線試過一次,找出所有能從起點到終點的路線,再從其中挑出最經濟的。 為什麼我會挑這個? 只是因為它的邏輯比較簡單易懂,畢竟這個程式不是在比賽,要去拼最快的話就不用了.. 哈哈。資料結構在講到 TREE 一定會講到怎麼樣把 TREE 的每個節點都走一次的方法,就是要搭配 STACK,把走過的點都 PUSH 進去,當作麵包屑來用,等走到沒路了就 POP 退回上一步,改走第二個分岔,直到所有的點都走完為止。 接下來就要把 GRAPH 切掉幾條線,把它想像成長的不大整齊的 TREE,就從起點開始走下去。因為 GRAPH 不像 TREE,有可能會走回原點,因此我們在走的過程中需要跳過已經走過的點,免的最後都在兜圈子繞不出去。 這邊我搭配了遞迴 (RECURSIVE) 的方式來簡化問題。其實就邏輯來說,遞迴幾乎可以跟 STACK 劃上等號。因為遞迴的過程中也是有 STACK 在輔助 (就是 CALL STACK)。不過我偏愛 RECURSIVE,因為藉著 CALL STACK 加上 FUNCTION CALL 傳遞的參數,可以自動幫我處理不少 push / pop, 及替每個階段保存暫時的資料,程式看起來會簡單很多。
    找出最經濟路線的程式碼[copy code]
       1:  private double _cost = 0;
       2:  private string[] _best_path = null;
       3:  private Stack<string> _path = null;
       4:  private void Search(string startName, string endName, double current_cost)
       5:  {
       6:      this._path.Push(startName);
       7:      if (startName == endName)
       8:      {
       9:          if (this._cost == 0 || current_cost < this._cost)
      10:          {
      11:              this._cost = current_cost;
      12:              this._best_path = this._path.ToArray();
      13:          }
      14:          this._path.Pop();
      15:          return;
      16:      }
      17:      foreach (Link way in this._nodes[startName].Links)
      18:      {
      19:          string next = way.GetOtherNodeName(startName);
      20:          if (this._path.Contains(next) == false)
      21:          {
      22:              this.Search(
      23:                  next,
      24:                  endName,
      25:                  current_cost + this._nodes[next].TollFee + way.Distance * 3);
      26:          }
      27:      }
      28:      this._path.Pop();
      29:  }
      30:  public string[] FindBestPath(string startName, string endName, out double cost)
      31:  {
      32:      try
      33:      {
      34:          this._cost = 0;
      35:          this._path = new Stack<string>();
      36:          this.Search(startName, endName, 0);
      37:          cost = this._cost;
      38:          return this._best_path;
      39:      }
      40:      finally
      41:      {
      42:          this._cost = 0;
      43:          this._path = null;
      44:      }
      45:  }
    先來看看結果。主程式是要找出 "機場端" 跟 "基金" 交流道之間的最經濟路線,看看程式跑出來的結果:
    image 不相信的人就拿紙筆畫一畫算一算吧! 應該是沒算錯啦。這個例子我就不像上一個例子,放上千萬個節點來拼拼看速度到底多快了,因為我沒有現成的資料啊,這東西要產生假資料也麻煩的多,就略過這個步驟了。不過我們倒是可以回過頭來看看,目前這段程式有什麼可以改進的? 首先,在資料數量遽增的情況下,演算法的改善一定是第一要務。你會發現程式碼從五行變成三行,或是從 100ms 進步到 90ms, 這種程度的改善相較之下都是微不足道的,一來這種改善程度通常是固定的,因為演算法沒有變,整體來說可能只是從 100sec 進步到 90sec,我是客戶的話,還不如換顆快一點的 CPU 就好了...。但是演算法的改進,則是讓你迴圈的次數變少,或是比較的次數變少等等,改變幅度通常是以倍數來算,隨便就提升好幾倍的效能。這就不是升級 CPU 可以解決的問題...。還記得上個例子嗎? 從 List 換成 SortedList, 搜尋速度差了 6000 倍... 你要花多少錢才買的到運算速度快 6000 倍的電腦? 除了演算法之外,程式也是有其它地方可以改善的。看到第 20 行程式碼了嗎? 就是找出下一步是不是已經走過了的程式碼: if (this._path.Contains(next) == false) 其中 _path 是 Stack<string> 物件,養成好習慣,順手查查它的時間複雜度吧,在 MSDN 裡是這麼寫的: http://msdn.microsoft.com/en-us/library/xeaek790.aspx This method performs a linear search; therefore, this method is an O(n) operation, where n is Count. 看起來它的效果跟 List 一樣,搜尋都很慢,有幾筆就要比對幾次。還記得上一篇提過什麼方法? 如果排序過的資料,要花的時間是 O(log n), 如果是採用 HashTable 結構的,則只要 O(1)... 再把 MSDN 拿出來翻翻看,發現除了 Dictionary<TKey, TValue> 之外,還有另一個更適合的 HashSet (.NET 3.5 only): http://msdn.microsoft.com/en-us/library/bb359438.aspx The HashSet<(Of <(T>)>) class provides high performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order. The capacity of a HashSet<(Of <(T>)>) object is the number of elements that the object can hold. A HashSet<(Of <(T>)>) object's capacity automatically increases as elements are added to the object. 馬上看一下,新增一筆及找出某一筆需要的時間複雜度:   HashSet<T>.Add( T ): If Count is less than the capacity of the internal array, this method is an O(1) operation. If the HashSet<(Of <(T>)>) object must be resized, this method becomes an O(n) operation, where n is Count.   HashSet<T>.Contains( T ): This method is an O(1) operation.   看起來沒什麼好挑的了。把資料塞進去跟找出來的時間都是固定的,當地圖的節點夠多,你要找的目標夠遠,多花一倍的空間另外放一份 HashSet 絕對是值得的。也因為 HashSet 有這樣的特性,因此它特別適合拿來作集合的運算。比如兩堆資料要找出交集 (Intersection),聯集 (Union) 等等都很方便。既然都講了就順手查看看: HashSet<T>.IntersectWith(Hash<T>): If the collection represented by the other parameter is a HashSet<(Of <(T>)>) collection with the same equality comparer as the current HashSet<(Of <(T>)>) object, this method is an O(n) operation. Otherwise, this method is an O(n + m) operation, where n is Count and m is the number of elements in other.         --------------------------- 本系列文章 [該如何學好 "寫程式"] 第一部份就先到這裡。在這裡作個小結。既然第一部份我是在探討要成為一個好的 "programmer" 該具備的能力,我自然是把重點放在怎樣把你拿到的需求,忠實且正確的寫成 code 為主。這時邏輯及觀念,還有資料結構等等基礎的知識是我認為的重點。也許有些讀者很不以為然,我猜想的大概會有這幾個理由:
    • 我不會這些,程式還不一樣寫的好好的?
    • 都什麼年代了,現在講求的是程式架構!
    • 物件導向不是都講求封裝? 幹嘛還要去挖這些?
    • 現在資料都放資料庫了,還學這幹嘛?
    • ...
    其實這些論點也沒錯,不過上一篇可以看到,不懂得這些基礎的話,現成的物件給你挑也不見得知道要挑那一個,更慘的是連之間的差別都不曉得。還有,資料結構通常包含兩個層面,一個是怎麼 "描述" 你的資料? 另一個是怎麼去應用你的資料? 以這題為例,如果你都不曉得要把地圖拆成點跟線來記錄,你會知道 TABLE 該怎麼建嗎? 另外,很多資料庫上面效能的問題,也都跟資料結構有關。就跟上一篇該挑那一種 Collection 一樣,資料庫也可以把它當成一個更巨大,功能更多的 Collection 來看待,因此能不能有效的利用它,資料結構也是很重要的觀念之一。 再來講到架構的部份,我覺的這位網友在他的 blog (我不認得他本人,只是常看他文章) 發表的這兩篇文章很不錯: 1. 程式設計的兩個觀點 (1/2) 2. 程式設計的兩個觀點 (2/2) 他這兩篇講的就是兩個極端,一個講求效率跟演算法,另一個則是講求架構跟程式的美感。而這兩者通常不容易兼顧。以我來說我比較偏後者,效能的部份,我會捨棄一些小地方以換來程式碼的可擴充性,可讀性,架構等等。不過我不會放棄的是資料結構跟演算法的正確性,就如同前面寫的例子一樣,程式碼有沒有最佳化,差的是 xx % 的效能,但是演算法跟資料結構的差距,則是好幾倍。我一向認為不會跑就要學飛,遲早會跌下來的,所以才會寫這三篇針對 programmer 的文章。 接下來,就換到 software engineer 了。這個階段就不只是把程式碼 "寫對" 或是 "寫出來" 而以,而是要開始考慮怎樣才 "寫的好" 了。有興趣的讀者們請耐心等待續集 :D   -- 範例程式下載: Taiwan-Highway.zip

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

  2. 得獎了 :D~~~

     IMG_9142

     

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

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

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

     

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

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

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

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

  3. 該如何學好 "寫程式" #2. 為什麼 programmer 該學資料結構 ??

    自從貼了上一篇 該如何學好 “寫程式” 一文,原本以為這種老生常談的內容沒什麼人會看,沒想到還有人給我回應.. :D 原來這種文章還是有市場的。接下來這篇,是延續上一篇,來談談要成為合格的 programmer, 我認為應該要俱備的 “內功” 是什麼。上篇我提到,我認知的 programmer,就是要有實作 (CODING) 的能力。要有能力把技術規格 (像是輸入格式,操作介面等等) 具體的寫成可以執行的程式碼。當然是要寫的又快又好,穩定不當機又沒 BUG …。

    在這個階段 (programmer),會一些具體的工具或是技術是必要的,但是它絕對不是主角。如何去運用你的工具才是關鍵。我認為 “資料結構” 就是能正確運用你的工具 (程式語言及函式庫) 最重要的知識。我常看到很多會一堆 “先進” 的技術,卻寫出很可笑的 code … 。這種例子太多了,兩層迴圈擺錯順序,或是某些動作 不小心 擺到迴圈內,多花了好幾倍的時間在做冤枉事…。這種例子我通通把它規在基本功夫不好,或是常聽的邏輯觀念不佳。所以在上一篇我會提到,好的 programmer 至少能滿足我講的三個基本要求:

    1. 丟一付洗過的撲克牌給你 (不要多,黑桃1 ~ 13就好),你知道怎麼用 Bubble Sort / Quick Sort 的步驟把它排好嗎? 丟一個陣列,裡面隨便打幾個數字,你能寫程式把它由小到大排好印出來嗎?
    2. 假設記憶體夠大的話,你有辦法把一百萬筆通訊錄資料讀到記憶體內 (用什麼物件都隨你),然後還能用很快的速度找到你要的資料嗎? 不同的搜尋方式,你知道該用什麼樣的方式找才有效率嗎?
    3. 以台灣高速公路為題 (中山高、北二高、國道二號),你有辦法寫程式,讓使用者指定起點跟終點的交流道,然後替它找出建議的路線嗎? (把延路經過的交流到跟收費站列出來就好)

    第一個只要你知道排序的方法,剩下的就是你有沒有本事把腦袋的想法寫成 CODE 而以。這個要求大部份的人都能過關,我就不多作解釋了。來看看第二個要求,它考驗的是你該用什麼樣的方式 “SEARCH” ?

    我就以 C# 為例來說明這個問題該怎樣思考。以資訊系的 “資料結構” 這門課的角度來思考,你應該要找出個適合的資料結構 (Binary Tree, Heap, Linked List … etc) 來存放這堆資料。不過資料結構這麼多種,你都要自己做嗎? .NET framework 已經在 System.Collection.Generic 這命名空間內提供了一堆好用的 Collection 給你用了,你該怎麼挑選才好? 課堂上老師不會教你實作的東西,而公司的前輩也不會教你這種基礎的東西,那你該怎麼把這兩者應用在一起?

    就先從 (2) 的例子開始吧! 通訊錄最基本的要求,就是儲存的資料要能按照姓名/EMAIL/電話號碼排序。輸入名字後,要能很快的找到這個人完整的通訊錄。如果能像手機一樣,邊輸入名字就邊過濾名單,直到名字打完人就找到的話更好。在宣告了 class ContactData { … } 類別來處理一筆資料後,下一步你會怎麼做?

    ContactData 類別定義:

    public class ContactData
    {
        public string Name;
        public string EmailAddress;
        public string PhoneNumber;
        public void OutputData(TextWriter writer)
        {
            writer.WriteLine("Name:\t{0}", this.Name);
            writer.WriteLine("Email:\t{0}", this.EmailAddress);
            writer.WriteLine("Phone:\t{0}", this.PhoneNumber);
            writer.WriteLine();
        }
    }
    

    開始來看看,有基本功夫的 programmer 跟一般 “熟 C# 熟 .NET” 的 programmer 差在那裡吧! 程式很簡單,先產生一百萬筆假資料,然後去找 A123456 這個人的資料,接著再找出手機號碼為 0928-1234 開頭的所有人資料。事後會分別計算花掉的時間跟程式佔用的記憶體大小。

    1. 大概有 70% 的人,會選擇用 List<ContactData>,不為什麼,只因為他沒想到別的方法,或是直覺就覺的要這樣寫… 來看看這樣的 code:

    List<ContactData> 寫的範例程式

    private static void Sample1()
    {
        Stopwatch timer = new Stopwatch();
        timer.Reset();
        timer.Start();
        // 產生假資料庫
        List<ContactData> contacts = new List<ContactData>();
        {
            for (int index = 999999; index >= 0; index--)
            {
                ContactData cd = new ContactData();
                cd.Name = string.Format("A{0:D6}", index);
                cd.EmailAddress = string.Format("{0:D6}@chicken-house.net", index);
                cd.PhoneNumber = string.Format("0928-{0:D6}", index);
                contacts.Add(cd);
            }
        }
        Console.WriteLine("建資料花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds);
        timer.Reset();
        timer.Start();
        {
            // 搜尋 A123456 這個人的資料
            ContactData data = null;
            data = contacts.Find(delegate(ContactData x) { return x.Name == "A123456"; });
            Console.WriteLine("搜尋 A123456 花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds);
            //data.OutputData(Console.Out);
        }
        timer.Reset();
        timer.Start();
        {
            // 列出電話號碼為 0928-1234* 開頭的使用者
            foreach (ContactData match in contacts.FindAll(delegate(ContactData x) { return x.PhoneNumber.StartsWith("0928-1234"); }))
            {
                //match.OutputData(Console.Out);
            }
            Console.WriteLine("搜尋 0928-1234* 資料花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds);
        }
        Console.WriteLine("共使用記憶體: {0}MB", Environment.WorkingSet / 1000000);
    }
    
    

    憑良心說,寫的出這樣程式碼的人,已經算是高手了。因為這樣已經用到不少高級技巧,像是 delegate, anonums method, 還有知道 List<T>.Find( ) 怎麼用等等… 以下是他的執行結果:

    1. 更進階一點的人 (另外 25%),也許會額外加上 Dictionary 當作索引,來改善 search A123456 這筆資料的效率:

    加上 Dictionary 當作索引的 code:

    // 略
    // 產生假資料庫
    Dictionary<string, ContactData> name_index = new Dictionary<string, ContactData>();
    List<ContactData> contacts = new List<ContactData>();
    {
        for (int index = 999999; index >= 0; index--)
        {
            ContactData cd = new ContactData();
            cd.Name = string.Format("A{0:D6}", index);
            cd.EmailAddress = string.Format("{0:D6}@chicken-house.net", index);
            cd.PhoneNumber = string.Format("0928-{0:D6}", index);
            name_index.Add(cd.Name, cd);
            contacts.Add(cd);
        }
    }
    Console.WriteLine("建資料花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds);
    timer.Reset();
    timer.Start();
    {
        // 搜尋 A123456 這個人的資料
        ContactData data = name_index["A123456"];
        //data = contacts.Find(delegate(ContactData x) { return x.Name == "A123456"; });
        Console.WriteLine("搜尋 A123456 花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds);
        //data.OutputData(Console.Out);
    }
    // 略</pre>
    

    會寫到這樣,也算強者了。不但對 C# 夠熟,也有用 Collection 物件來當作索引的觀念。程式碼只有兩行不同,一個是多宣告了 Dictionary 物件 (第3行),另一個是搜尋的地方 (第21行)。來看看執行結果:

    果然有效,建資料從 5151ms 變成 5843ms, 記憶體從 288MB 變成 340MB,不過 search(A123456) 卻快的嚇人, 0ms… 破錶了!

    但是這樣的 CODE 老實說只能算是及格而以,因為它沒有挑對 Collection 來用。怎麼說? 我的理由有這幾個:

    1. List<T> 的搜尋效能不好
    2. 沒能滿足用多種排序方式的要求 (需要時要當場執行 List<T>.Sort( ))

    如果這是某個 Mail Client 內的 CODE,產品經理一定會問:

    “如果資料從一百萬筆,變成一億筆,程式的表現會是什麼情況?”

    有沒有基本功夫,這裡開始有差別了。唸過資料結構的都知道有個叫 “時間複雜度” (time complexity) 的東西,用 O(n) 表示。O(n) 代表花費的時間會跟資料比數成線性的成長。100倍的資料大概就要花上100倍的時間.. 如果是 O(n^2) 的演算法,則 100 倍的資料就會花上 10000 倍的時間。

    MSDN 專業的地方就在這裡。Microsoft 真的很細心的在每一個 Collection 物件的說明文件上,都會標上 time complexity。有唸書有保佑,瞄到那行字我的問題就都解決掉了。先來看看 List 的行為:

    **List.Add(T item):**

    If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

    [List.FindAll(Predicate match)](http://msdn.microsoft.com/en-us/library/fh1w7y8z.aspx)

    This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.

    再來看看 Dictionary<TKey, TValue> 的行為:

    Dictionary<TKey, TValue>.Add(TKey key, TValue value)

    If Count is less than the capacity, this method approaches an O(1) operation. If the capacity must be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

    Dictionary<TKey, TValue>.Item[TKey key] {get; set;}

    Getting or setting the value of this property approaches an O(1) operation.

    好,答案出來了。當資料變成一百倍時,List.Add 是 O(1), 所以每加一筆資料的時間不會越來越久 (safe). 但是搜尋時間是 O(n), 意思是現在找 A123456 要花 60ms, 未來有一億筆就要花 60x100=6000ms=6sec, 找 0928-1234* 則要花 240x100=24000ms=24sec… 以這樣的成長速度,記憶體還沒用完,你的程式就會慢到受不了了。有沒有其它的解決辦法?

    換成 Dictionary 就酷多了,搜尋時間是 O(1), 代表不管你有幾筆,搜尋的時間都差不多。為什麼? MSDN 說的很清楚…

    http://msdn.microsoft.com/en-us/library/xfhwa508.aspx

    The Dictionary<(Of <(TKey, TValue>)>) generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<(Of <(TKey, TValue>)>) class is implemented as a hash table.

    什麼是 HashTable? 又是一個好例子,唸過資料結構的都知道吧? 我就不多說了,請看 wiki:

    http://en.wikipedia.org/wiki/Hashtable

    一樣是看 MSDN 文件,有沒有唸過資料結構,到這裡就差這麼多了。體會到學校教的東西真的有用了嗎? 這個例子還沒完,再看下去。

    事實上,以上的實作方式都不合格。LIST 效能不好,Dictionary 拿來作索引有個致命的缺點:

    它的 KEY 不能重複!!!

    是的,對應到資料庫的話,它就好像是個 unique key 一樣。拿來當 NAME 的索引還沒問題,拿來當其它欄位的索引就糟糕了,別說效能問題,連用都不能用。

    另外,針對排序的問題也是無解,這是 HashTable 的特性,要照順序排,就要另請高明。

    事實上,以上的實作方式都不合格。List 搜尋的效能不算好,而 Dictionary 也只能處理 exact match 的狀況,同時也無法處理需要排序的問題。

    唸過書的再想想,這時該怎麼辦?

    標準解法是分別照這幾個欄位排序,然後用 Binary Search. 這才是正解。因為排序好的資料就像一般資料庫的 index, 可以讓你很容易的 order by, 同時又能讓你很快的找到你要的資料,甚至是列出某一段範圍的資料都沒問題。

    不過寫成程式要怎麼作? MSDN 就在手上嘛,System.Collection.Generic 就把它當購物網站,逛一逛… 看有沒有其它合用的。

    不錯,又找到兩個: SortedListSortedDictionary,還是一樣,那一個比較合適? MSDN 都寫的很清楚,足夠你判斷了,前題是資料結構教的幾個基本觀念 (像是前面講的 Hash Table, Time Complexity 等) 人家寫出來你要看的懂,看的懂就知道該挑那一個。

    至於挑選的過程我就不多說了。我最後決定用 SortedList, 列一下這個 Collection 的特性:

    SortedList.Add( )

    This method is an O(n) operation for unsorted data, where n is Count. It is an O(log n) operation if the new element is added at the end of the list. If insertion causes a resize, the operation is O(n).

    新增一筆需要的時間是 O(n), 唯一特例是加在最後面,而且沒引發 resize 的動作,就是 O(log n)。至於排序? 通通是 O(1),因為在 Add() 把資料加進來時就排好序了,所以 Add() 花的 O(log n) 就是在排序。要照順序印資料或找資料,完全不費吹灰之力,拿來印就是了。不過比較可惜的是,SortedList 並沒有提供 BinarySearch,因此要找 “0928-1234*” 這樣的資料要辛苦點,自己用 BinarySearch 的邏輯,簡單寫一下吧。如果前面的關卡都過了,這應該不難吧?

    改用 SortedList 最大的缺點就是載入資料時會比較慢,不過其它在程式的處理上,還有效能都更貼近這個題目的需求。來看看程式碼,這次我用了兩個 SortedList,分別代表替 name 及 phone number 作排序:

    改用 SortedList<> 的範例:

    private static void Sample3()
    {
        Stopwatch timer = new Stopwatch();
        timer.Reset();
        timer.Start();
        // 產生假資料庫
        SortedList<string, ContactData> name_index = new SortedList<string, ContactData>();
        SortedList<string, ContactData> phone_index = new SortedList<string, ContactData>();
        {
            for (int index = 0; index < 1000000; index++)
            {
                ContactData cd = new ContactData();
                cd.Name = string.Format("A{0:D6}", index);
                cd.EmailAddress = string.Format("{0:D6}@chicken-house.net", index);
                cd.PhoneNumber = string.Format("0928-{0:D6}", index);
                name_index.Add(cd.Name, cd);
                phone_index.Add(cd.PhoneNumber, cd);
            }
        }
        Console.WriteLine("建資料花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds);
        timer.Reset();
        timer.Start();
        {
            // 搜尋 A123456 這個人的資料
            ContactData data = name_index["A123456"];
            Console.WriteLine("搜尋 A123456 花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds);
            //data.OutputData(Console.Out);
        }
        timer.Reset();
        timer.Start();
        {
            // 列出電話號碼為 0928-1234* 開頭的使用者
            for (int pos = BinarySearch<string, ContactData>(phone_index, "0928-1234");
                pos < BinarySearch<string, ContactData>(phone_index, "0928-1235");
                pos++)
            {
                //phone_index.Values[pos].OutputData(Console.Out);
            }
            Console.WriteLine("搜尋 0928-1234* 資料花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds);
        }
        Console.WriteLine("共使用記憶體: {0}MB", Environment.WorkingSet / 1000000);
    }
    private static int BinarySearch<TKey, TValue>(SortedList<TKey, TValue> index, TKey key)
    {
        return BinarySearch<TKey, TValue>(index, key, 0, index.Count - 1);
    }
    private static int BinarySearch<TKey, TValue>(SortedList<TKey, TValue> index, TKey key, int start, int end)
    {
        if (start == end) return end;
        int pos = (start + end) / 2;
        int compareResult = index.Comparer.Compare(key, index.Keys[pos]);
        if (compareResult == 0)
        {
            return pos;
        }
        else if (compareResult > 0)
        {
            return BinarySearch<TKey, TValue>(index, key, pos + 1, end);
        }
        else
        {
            return BinarySearch<TKey, TValue>(index, key, start, pos - 1);
        }
    }
    

    執行結果:

    至於前面產品經理問的問題,各位就試著自己到 MSDN 找看看答案吧! 比較過之後,你就會瞭解為什麼我會挑選 SortedList .. 我只挑 SEARCH 時間來看,List 的搜尋是 O(n), 而 SortedList 的搜尋是排序過的資料作 BinarySearch, 找找書就知道是 O(log n), 分別來比較一下:

    當 N 等於 1000000 時:

    List: 3131861 ticks SortedList: 39294 ticks (快 80 倍)

    推算一下,N 放大為 100 倍 (100000000) 時:

    List: 3131861 x 100000000 / 1000000 = 313186100 ticks

    SortedList: 39294 x log 100000000 / log 1000000 = 52392ticks (快 5978 倍)

    看到了嗎? 換個 Collection 物件,對於 Search 這個動作,一百萬筆資料時差了 80 倍,當資料成長一百倍 (100000000 筆) 時,搜尋速度差異爆增為近 6000 倍! 這就是資料結構或是演算法的差異,這樣的差異已經大到其它地方最佳化怎麼作都補不回來的地步,唯一一個關鍵就是要用對演算法!

    終於打完這篇了。沒想到前一篇寫一堆老生常談的話,這次又變成一堆 sample code 了。不過我的目的就是讓各位瞭解,基礎一定要顧好啊,不然寫程式是一定會碰到瓶頸的。這次從很簡單的需求,帶到資料結構的觀念,再帶到 MSDN 裡面特別標記的資訊…。看完後應該不會再有人說學校教的東西沒用了吧?

    有網友問過我有沒有推薦什麼書? 很抱歉,我也只看過課本而以 … 哈哈,這些純粹是出來工作後,無意間還想到要去翻翻課本得來的經驗。其實這種例子很多,過去我常貼的 multi-thread 的文章也是很多這樣的例子,只不過課本從資料結構換成作業系統了,這個主題才寫到 1-2, 後面還有, 有什麼看法或心得就請留在回應給我吧! 如果能支持一下旁邊的讚助商的話也算是種鼓厲啦.. 敬請期待下一篇..

    調查一下,有人看這篇之前就知道 SortedList 嗎? 留個話給我吧,我很好奇這種東西有多少人會去用… :D

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

  4. MSDN Magazine 十月號竟然下架了...

    image

    上個禮拜才看完 2008 / 10 的 MSDN Magazine,才想說這期 MSDN 的內容,有一半以上的主題是討論多核心處理器效能問題 (平行處理,多核的 CACHE 機制對程式的影響... etc),不過剛才才想貼篇心得,上網一看竟然又縮回去只剩九月號? @_@

    難道我是夢到我看過十月號的嘛? 哈哈... GOOGLE 找一下還真的給我找到庫存網頁 :D 當然要貼來紀念一下。不知道重新上架後內容會不會多幾篇文章?

     

    這期的主題還真的都押在多核處理器的效能問題上。光是平行處理 ( TPL, PLINQ ) 的方法就好幾篇:

    • Design Considerations For Parallel Programming
    • Improved Support For Parallelism In The Next Version Of Visual Studio
    • Build Concurrent Apps From Simple F# Expressions

     

    另外在探討多核心效能問題的也有幾篇:

    • new Thread(ReadEditorsNote).Start(); yourAttention.WaitOne() //這標題還蠻有意思的...
    • .NET Matters: False Sharing
    • Exploring High-Performance Algorithms

     

    不過看完只記得部份重點而以,本來想多寫點心得,不過原文網址都連不到了... 再等幾天吧 :D

    2008/09/28 .NET MSDN 多執行緒 技術隨筆

  5. Google 讓人越來越笨?

    無意間在網站上看到這則新聞:

     

    GOOGLE 讓人變笨?網路便利後遺症
    http://n.yam.com/bcc/life/200806/20080626204869.html

     

    文內有這麼一段話:

    但是大家都忽視了這種便捷要付出的代價。「網路似乎粉碎了人們專注與沉思的能力,到如今,腦袋只盼著以網路提供資訊的方式來獲取資訊」。

    影響所及,傳統媒體也跟著零碎化,長篇大論的東西不再有人要看,一篇文章超過四個段落,讀者就想落跑,電視節目加入滾動字幕和不斷跳出的小廣告,報刊則儘量縮短文章長度,改以一小塊一小塊的摘要取代,在版面上堆砌各種易於瀏覽的零碎資訊。

    這篇文章還沒找到真正源頭的那篇文章,不過這篇一定要推一下,真的是講到我心坎裡了。我要講的不是這篇文章,而是現在 INTERNET 環境下,GOOGLE 實在是太方便了,讓很多事開始可以 "速成" 起來。技術的進步不是壞事,不過在什麼都要 "速成" 的文化下,到底還有多少人願意去深入的研究某一件事物呢?

     

    以我的老本行 "軟體開發" 為例,很多人半路出家,學了一些工具或是簡單的網頁程式設計,就可以出家了。天資好一點的,碰到問題還曉得到 GOOGLE 去查查有無合適的 SOLUTION,找到了就東拼西湊湊出個 "可以動" 的 SOLUTION。聽起來沒什麼不好啦,不過這樣一來,沒有幾個人還會願意再深入瞭解為什麼要這樣做等等議題了。我面試過的工程師也有幾十個了 (不知道破百了沒?),有幾個問題是我必問的,其中一個就是:

     

    "你碰到不知道怎麼解決的問題時,你會怎麼做?"

     

    我沒真的統計啦,不過印像中,問題答案的榜首是:

    1. GOOGLE 找看看
    2. 各大論譚去問問題 or 搜尋看看
    3. 問朋友
    4. 翻書
    5. ... (不外乎是對外求救之類的方法)

    我期望的答案一直沒有聽到,而聽到的都是透過 INTERNET + SEARCH ENGINE 這類的回答。當然這是沒錯啦,因為 GOOGLE 實在太方便了,不過我期望聽到的 "再進修" "想辦法去瞭解問題的原因" 等等答案都沒聽到。就算要找資料,連知道要去查第一手資料 (Microsoft 的東西,大部份 MSDN 都有提供第一手的資訊,不然就是某技術產品的官方網站) 的觀念都沒了,只因為英文看不懂? 或是鄉民寫的東西看的比較簡單? 咳咳...。

    而這件事的負面影響,就是人才越來越 M 型化了。INTERNET 只需要有 M 型頂端的人提供資訊,讓其它人來找資源就夠了。GOOGLE 越強,落在 M 型左邊人才的需求就越少。越來越多人依賴 GOOGLE找到零碎的資訊拼湊起來,而少了獨立思考解決問題的能力。我想人類的智能,重組的部份一定會越來越多,創造的部份一定會越來越少,會不會到最後創造的部份就會消失不見了? 難怪 INTEL 會如此預言,2050年後,機器的智慧會開始超越人類了。很有道理耶,因為搜尋 & 重組不就是電腦的專長嗎? 資料夠多運算速度夠快就能做的到。而電腦追不上的 "創造" 這種能力,人類卻漸漸的在喪失...

    也許實際情況不會這麼悲觀,但是我相信這一定是個趨勢。能怎樣對抗這樣的 "退化" ? 想辦法讓自己的能力落在 M 型的左邊吧。跟上一篇講的一樣,沒有速成的方式,先把內功練好吧! 與其花時間研究那些兩三年就會淘汰掉,看起來很炫的 "新技術",不如多花點時間學一學能讓你終身受用的基礎能力吧。

    2008/09/28 技術隨筆 有的沒的