[CODE] LINQ to Object - 替物件加上索引!

好久沒寫文章了，看了一下上一篇的日期… 嚇，再撐幾天就 10 個月了 =_=,  週末看了 darkthread 的這篇文章: 當心LINQ搜尋的效能陷阱，想說 LINQ to SQL, LINQ to Entity Framework, LINQ to … 都支援索引, 沒道理 LINQ to Object 不行啊, 一定只是沒人補上實作而已.. 動了這個念頭之後, 接下來的時間就都在研究這些…

回到主題，年紀夠大的網友，大概都還聽過 Embedded SQL 吧? 當年用 C/C++ 要存取資料庫，實在不是件簡單的事… 光是那堆 initial database connection 的動作就搞死人了，因此有些開發工具廠商，就搞出了 Embedded SQL 這種內嵌在程式語言內的 SQL .. 貼一段 CODE，看起來大概像這樣:

Embedded SQL sample code:

/* code to find student name given id */
/* ... */
for (;;) {
    printf("Give student id number : ");
    scanf("%d", "id);
    EXEC SQL WHENEVER NOT FOUND GOTO notfound;
    EXEC SQL SELECT studentname INTO :st_name
             FROM   student
             WHERE  studentid = :id;
    printf("Name of student is %s.\n", st_name);
    continue;
notfound:
    printf("No record exists for id %d!\n", id);
}
/* ... */

有沒有跟現在的 LINQ 很像? CODE 就不多解釋了，這類的工具，大都是遵循這樣的模式: 透過編譯器 (或是 code generator / preprocessor)，將 query language 的部份代換成一般的 data access code，最後編譯成一般的執行檔，執行起來就有你預期的效果…

看到 darkthread 探討 LINQ to Object 效能問題之後，第一個反應就是:

“該怎麼替 LINQ to Object 加上索引??”

LINQ 這堆指令，最終是會被翻譯成 extension method, 而這些 extension method 是可以自訂的，就先寫了一個小程式試看看..

    public class IndexedList : List<string>
    {
    }

    public static class IndexedListLinqExtensions
    {
        public static IEnumerable<string> Where(this IndexedList context, Expression<Func<string, bool>> expr)
        {
            Console.WriteLine("My code!!!");
            foreach (string value in context.Where(expr)) yield return value;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            IndexedList list1 = new IndexedList();
            // init list1 ...

            foreach (string value in (from x in list1 where x == "888365" select x)) {
                Console.WriteLine("find: {0}", value);
            }
        }
    }

程式很簡單，只是做個 POC，證明這段 CODE 會動而已。從 List<string> 衍生出一個新類別: IndexedList, 然後針對它定義了專屬的 Extension method: Where(...), 然後試著對 IndexedList 這集合物件，用 LINQ 查詢… 果然 LINQ 在執行 where x == “888365” 這語句時，會轉到我們自訂的 extension method !

接下來的工作就不是那麼簡單了，我自認很愛挖這些 framework 的設計，又自認 C# 語法掌握能力也不差，結果我也是花了一些時間才摸清楚它的來龍去脈… 事情沒這麼簡單，所以我做了極度的簡化…

首先，我只想做個 POC (Proof of concept), 證明可行就好, 完全沒打算把它做成可用的 library .. 因為在研究的過程中，早已找到有人在做這件事了 (i4o, index for objects)。為了讓 code 簡短到一眼就看的懂的程度，我的目標定在:

1. 查詢對相只針對 List<string> 處理，不做泛型及自訂索引欄位。
2. 查詢只針對 == 做處理。如下列 LINQ 語句的 where 部份: from x in list1 where x == "123456" select x
3. 條件只限於 x == "123456", 只提供 == 運算元，只提供常數的比對，常數只能放在右邊…

接下來就是索引的部份了，因為 where 只處理 == 這種運算，也不用排序了，採用 HashSet 就很夠用了，速度又快又好用，時間複雜度只有 O(1) .. 看起來很理想，於是剛才的 Sample Code 就可以改成這樣:

IndexedList : 加上索引的 List<string> 實作

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;

namespace IndexedLinqTest
{
    public class IndexedList : List<string>
    {
        public readonly HashSet<string> _index = new HashSet<string>();

        public void ReIndex()
        {
            foreach (string value in this)
            {
                this._index.Add(value);
            }
        }
    }

    public static class IndexedListLinqExtensions
    {
        public static IEnumerable<string> Where(this IndexedList context, Expression<Func<string, bool>> expr)
        {
            if (expr.CanReduce == false "" expr.Body.NodeType == ExpressionType.Equal)
            {
                BinaryExpression binExp = (BinaryExpression)expr.Body;
                string expectedValue = (binExp.Right as ConstantExpression).Value as string;
                if (context._index.Contains(expectedValue)) yield return expectedValue;
            }
            else
            {
                //return context.Where(expr);
                foreach (string value in context.Where(expr)) yield return value;
            }
        }
    }
}

程式碼稍等再說明，先來看看怎麼用! darkthread 的作法真不錯用，借兩招來試試… 程式大概執行這幾個步驟:

1. 準備 10000000 筆資料，用亂數打亂，建立 list1 (含索引, type: IndexedList) 及 list2 (不含索引, type: List<string>)
2. 呼叫 list1.ReIndex(), 替 list1 重建索引 (HashSet), 記錄建立索引花費的時間
3. 分別對list1, list2進行LINQ查詢，查出四筆指定的資料，計算查詢花費的時間

直接來看看程式碼吧:

測試 Indexed LINQ 的程式碼

class Program
{
    static void Main(string[] args)
    {
        Stopwatch timer = new Stopwatch();

        IndexedList list1 = new IndexedList();
        list1.AddRange(RndSeq(8072, 10000000));

        List<string> list2 = new List<string>();
        list2.AddRange(list1);

        timer.Restart();
        list1.ReIndex();
        Console.WriteLine("Build Index time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);


        Console.WriteLine("\n\n\nQuery Test (indexed):");
        timer.Restart();

        foreach (string value in (from x in list1 where x == "888365" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list1 where x == "663867" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list1 where x == "555600" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list1 where x == "888824" select x)) 
            Console.WriteLine("find: {0}", value);

        Console.WriteLine("Query time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);

        
        
        Console.WriteLine("\n\n\nQuery Test (non-indexed):");
        timer.Restart();

        foreach (string value in (from x in list2 where x == "888365" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list2 where x == "663867" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list2 where x == "555600" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list2 where x == "888824" select x)) 
            Console.WriteLine("find: {0}", value);

        Console.WriteLine("Query time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);
    }

    private static IEnumerable<string> SeqGenerator(int count)
    {
        for (int i = 0; i < count; i++) yield return i.ToString();
    }

    private static IEnumerable<string> RndSeq(int seed, int count)
    {
        Random rnd = new Random(seed);
        foreach (string value in (from x in SeqGenerator(count) orderby rnd.Next() select x)) yield return value;
    }
}

而程式執行的結果:

貼一下參考配備 (這是炫耀文…)，給大家體會一下速度…

CPU: INTEL i7 2600K, INTEL Z68 主機板 RAM: 8GB OS: Windows 7 (x64)

看起來藉著 HashSet 當索引，來加速 LINQ 查詢的目的已經達到了。不加索引需要 2147.83 ms, 而加上索引只需要 2.19ms … 兩者時間複雜度分別是 O(1) v.s. O(n), 要是資料的筆數再往上加，兩者的差距會更大…

回過頭來看看程式碼吧! 關鍵在 LINQ 的 Extension 上面:

支援索引的 LINQ extension: where( )

public static IEnumerable<string> Where(this IndexedList context, Expression<Func<string, bool>> expr)
{
    if (expr.CanReduce == false "" expr.Body.NodeType == ExpressionType.Equal)
    {
        BinaryExpression binExp = (BinaryExpression)expr.Body;
        string expectedValue = (binExp.Right as ConstantExpression).Value as string;
        if (context._index.Contains(expectedValue)) yield return expectedValue;
    }
    else
    {
        //return context.Where(expr);
        foreach (string value in context.Where(expr)) yield return value;
    }
}

line 1 的宣告，限制了只有對 IndexedList 型別的物件，下達 WHERE 語句的情況下，才會交由你的 extension method 執行。而 Microsoft 會把整個 where 語句，建構成 Expression 這型別的物件。

前面我下的一堆條件，像是只能用 == 運算元，只針對字串常數比對等等，就都寫在 line 3 的判段式了。基本上只要不符合這些條件，就會跳到 line 12, 索引等於完全無用武之地了。

要是符合使用索引的條件，則程式會進到 line 5 ~ line 7.  程式會透過 HashSet 去檢查要找的 data 是否存在於 List 內? 前面提過了，用 HashSet.Contains(...) 來檢查 (O(1))，效能遠比 List<string>.Contains(...) 的效能 (O(n) ) 好的多。

實驗的結果到此為止，很明顯了，索引的確發揮出效果了，不過老實說，這段 code 真的沒什麼實用的價值… 哈哈，與其這樣繞一大圈，用 LINQ 很帥氣的查資料，還不如直接用程式找 HashSet 就好… 這只是證明 it works, 不繼續完成它，主要的原因是已經有人做了，而且做的比我好 XD! 需要的人可以參考看看 i4o 這套 library. 想體會這東西怎麼用，可以先看看作者的 BLOG，這篇是使用範例:

http://staxmanade.blogspot.com/2008/12/i4o-indexspecification-for.html

要下載的話，它的 project hosted 在 codeplex: http://i4o.codeplex.com/

2011/10/25 C# 技術隨筆 物件導向

[CODE] 可以輸出到 TextBox 的 TextWriter: TextBoxWriter!

吃葡萄不吐葡萄皮... 對，這不是繞口令... 哈哈...。

先祝各位 2011 新年快樂!!  這幾個月忙翻了, 一方面系統要移轉到 windows azure, 另一方面要改善原本系統的排程 (原本是 console app + scheduler task service), 現在要用 windows service 來取代, 突然之間之前覺的工作上用不到的 multi-threading 技巧, 現在都派上用場了...

題外話先扯一下, 在 azure 因為架構上就已經把 web role (presentation layer) / worker role (business logic layer) / azure storage (data layer) 分的很清楚, 相對的每一層之間的 communication 時間就拉長了, 我們碰到的狀況就是 worker role 對 azure storage 有大量的 I/O 的話, 效能就很糟糕... 在這邊用了生產線的模式, 結果效能提升了十幾倍... 果然前輩說的沒錯: 架構對了，什麼事都變簡單了...

另一個案例則是把原本靠 windows task scheduler 執行的排程，改成用自行開發的 windwos service ... 不過開發成 service 實在是不大好除錯, 再加上多執行緒先天也是除錯不易... 因此開發階段都寫成windows form, 提供 START / STOP / PAUSE / CONTINUE 等控制的功能，簡化前段的開發作業。

azure / service 都用到了不少多執行緒的技巧, 改寫成 service 也用了老字號的 Cassini 解決另一部份的問題，這些都是值得介紹一下的部份，不過今天主題不在這，改天另起專欄再說。在改寫成 windows service 的過程中，需要把過去寫成 Console application 的 code 移到 service ，而過去這些程式都直接用 Console.Out 這個 TextWriter 輸出訊息到 DOS command prompt / log file, 移到 windows form 之後, 要輸出到 TextBox 就變的麻煩了點, 本來不想理它, 後來發現不好好處理這個問題還不行...

如果不講究 code 好不好看，其實改一下程式就可以了，把原本的 Console.Out.WriteLine( ) 改成 TextBox.AppendText( ) 就好，但是...

1. 原程式得改寫，不能直接用 TextWriter ... 另外, 很多現有的函式庫都接受 TextWriter, 不能靠 TextWriter 輸出的話程式會變很雜
2. 只有 create control 的 UI thread 可以呼叫 AppendText( ) ...
3. thread-safe 的問題: 輸出的訊息會交錯輸出, 無法閱讀
4. 長時間連續執行，TextBox 的訊息會太多, 得要有 recycle 的機制
5. 最好可以順便寫 LOG 檔...

老實說，除了 (1) 之外，其它點都是自己寫個專用的 OutputLog method 就可以解決。不過考量到程式未來真正執行時，是在 service 的環境, 在那邊是沒有 TextBox 這種 UI control 的, 最終還是要透過 TextWriter 輸出到 log file, 或是透過 socket 輸出... 何況用 TextWriter 輸出 log 也比較符合抽象化的原則, 不需要去碰到太多輸出方式的細節...

問題跟目的都搞清楚之後，接下來就是實作了。這次實作目標就是要想個辦法，用 TextWriter 的方式輸出 LOG 訊息，而這些訊息要自動呈現在 WebForm 的 TextBox control 上, 就好像在 DOS command prompt 裡執行 console application 一樣。先來想像一下 code 寫起來跟看起來是什麼樣子:

        private TextWriter output;
        public Form1()
        {
            InitializeComponent();
            this.output = TextWriter.Synchronized(new TextBoxWriter(this.textBox1));
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            for (int i = 0; i < 300; i++)
            {
                this.output.WriteLine("{0}. Hello!!!", i);
            }
        }

   1:  private TextWriter output;

   2:  public Form1()

   3:  {

   4:      InitializeComponent();

   5:      this.output = TextWriter.Synchronized(new TextBoxWriter(this.textBox1));

   6:  }

   7:  private void Form1_Load(object sender, EventArgs e)

   8:  {

   9:      for (int i = 0; i < 300; i++)

  10:      {

  11:          this.output.WriteLine("{0}. Hello!!!", i);

  12:      }

  13:  }

建立好 TextWriter 之後，後面只管用這 writer 輸出訊息，對應的 TextBox 自然就會像 terminal 般，不斷的跑出訊息出來...

基本要求達到了，這就是我要的功能。其實這東西上網 GOOGLE 一下, 類似的例子也有, 不過一來寫起來沒幾行, 二來功能跟我要的有點出入... 想想還是自己寫一個。先來看看這個 writer 是怎麼實作的?

TextWriter 要實作並不難，不過不熟悉的話，也是得花些時間才能搞定。主要是 TextWriter 的 Writer( ) 跟 WriterLine( ) 就共有 35 種不同的多載... HELP 沒有清楚的寫到這堆 method 之間的關係，一時也不知 override 那一個的效果是最好的...。一開始我是從最基本的 void TextWriter.Write(char value) 下手, 結果效能慘不忍睹... 輸出一行字就要一秒鐘, 好像回到了當年DOS時代加上倚天中文後, 按個DIR字是一行一行跑出來的光景... Orz, 後來花了點時間追蹤這卅幾個 method 的先後關係，才改了這個效能 OK 的版本:

   public class TextBoxWriter : TextWriter
    {
        private TextBox _textbox;
        public TextBoxWriter(TextBox textbox)
        {
            this._textbox = textbox;
        }

        public override void Write(char value)
        {
            this.Write(new char[] { value }, 0, 1);
        }

        public override void Write(char[] buffer, int index, int count)
        {
            if (this._textbox.InvokeRequired)
            {
                this._textbox.Invoke((Action<string>)this.AppendTextBox, new string(buffer, index, count));
            }
            else
            {
                this.AppendTextBox(new string(buffer, index, count));
            }
        }



        private void AppendTextBox(string text)
        {
            this._textbox.AppendText(text);
        }



        public override Encoding Encoding
        {
            get { return Encoding.UTF8; }
        }
    }

   1:  public class TextBoxWriter : TextWriter

   2:   {

   3:       private TextBox _textbox;

   4:       public TextBoxWriter(TextBox textbox)

   5:       {

   6:           this._textbox = textbox;

   7:       }

   8:       public override void Write(char value)

   9:       {

  10:           this.Write(new char[] { value }, 0, 1);

  11:       }

  12:       public override void Write(char[] buffer, int index, int count)

  13:       {

  14:           if (this._textbox.InvokeRequired)

  15:           {

  16:               this._textbox.Invoke((Action<string>)this.AppendTextBox, new string(buffer, index, count));

  17:           }

  18:           else

  19:           {

  20:               this.AppendTextBox(new string(buffer, index, count));

  21:           }

  22:       }

  23:       private void AppendTextBox(string text)

  24:       {

  25:           this._textbox.AppendText(text);

  26:       }

  27:       public override Encoding Encoding

  28:       {

  29:           get { return Encoding.UTF8; }

  30:       }

  31:   }

其中補充說明一下, 在 line 14 ~ 21 為何要大費周章的, 把要呼叫 AppendTextBox( ) 的動作, 放到 delegate, 再交由 TextBox 控制項自行 Invoke 呼叫 ? 這是源自 windows form 的一條規範, 要是你寫的程式有多執行緒的應用，一定要知道這鐵律:

UI thread 的限制: 只有 create control 的 thread 可以更動 control 的狀態。

如果不遵守這個規則，執行時就會被警告:

解法就參考 line 14 ~ 21 的部份就好，說明的話 darkthread 這篇講的很清楚, 我就不客氣直接引用了 :D

http://blog.darkthread.net/blogs/darkthreadtw/archive/2007/09/29/tips-about-ui-thread-limitation.aspx

不過，這樣只是達到基本需求而已，還有其它的問題... (3 ~ 5), 太久沒寫文章了，沒想到一篇寫不完... 請待下回分解 :D

2011/01/03 .NET ASP.NET C# 多執行緒 技術隨筆

Extension Methods 的應用: Save DataSet as Excel file...

好久沒寫東西了，趁著還記得 C# 怎麼寫的時後多補幾篇 =_= 要靠程式輸出Excel已經是個FAQ級的問題了，看過我之前文章的大概都知到，我很懶的寫那種FAQ級的東西，不是說寫了沒用，而是太多人寫，一定有寫的比我好的... 到最後連我自己忘了都會去查別人寫的，那我寫了還有啥用? 所以當然是有些特別的東西，才會想寫這篇...  我碰到的問題是，程式要處理的都是 DataSet 物件，不過 DataSet 物件是從 Excel 來的，處理完也要能回存回 Excel ..., 只不過為了先把 POC 作完，現在是以 DataSet 原生的 XML 格式代替。 其實以儲存的角度來看，XML很好用。不過要教會客戶編輯XML可是個大挑戰啊... 像 Excel 這樣有個表格還是比較容易上手一點。原本的程式長的像這樣:  

            DataSet ds = new DataSet();
            ds.ReadXml("data.xml");
            // do something
            ds.WriteXml("data.xml");