對於長年與資料庫、SQL語法打交道的開發者來說,LINQ語法有無比的親切感! 當要在List<SomeClass>集合中找尋特定物件時,寫成
   form o in SomeList where o.Col1 == "A" && o.Col2 == "B" select o
是再自然也不過的事。乍看之下,反正List<SomeClass>已被存在記憶體,無須顧忌反覆查詢資料庫所產生的連線成本,而where條件比對又十分直覺易懂,感覺上是個不可多得的好做法。

但需留意一點: LINQ to Object的Where查詢不像實體資料庫可以靠Index加速或透過資料庫引撆演算法進行最佳化,當查詢對象的元素很多且重覆查詢頻率很高時,就應考慮使用Dictionary<string, SomeClass>等做法取代Where條件比對,避免效能問題。

今天剛好看到有段程式用LINQ搜尋實現對照表查詢,有違我所認知的效能法則,但過去有概念卻沒實測過,因此索性設計了一個實驗來驗證:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
 
namespace ConsoleApplication1
{
    class Program
    {
        static List<Boo> pool = new List<Boo>();
        static List<Boo> shuffled;
        static Dictionary<string, Boo> dict;
        static Dictionary<string, string> strDict;
 
        static void Main(string[] args)
        {
            int MAX_NO = 100;
            //使用相同亂數種子確保每次執行之測試資料相同
            Random rnd = new Random(9527); //交給你了,9527
            //建立大量物件集合
            for (int i = 0; i < MAX_NO; i++)
            {
                for (int j = 0; j < rnd.Next(500, 1000); j++)
                {
                    pool.Add(new Boo()
                    {
                        No = i,
                        SubNo = j,
                        Code = "C" + rnd.Next(1000).ToString("000")
                    });
                }
            }
            //打亂排序
            shuffled = pool.OrderBy(o => rnd.Next()).ToList();
            //建立Dictionary
            dict = pool.ToDictionary(
                o => string.Format("{0}\t{1}", o.No, o.SubNo),
                o => o);
            //建立字串Dictionary
            strDict = pool.ToDictionary(
                o => string.Format("{0}\t{1}", o.No, o.SubNo),
                o => o.Code);
            //產生TIMES個待查對象
            int TIMES = 500;
            List<Boo> toFill = new List<Boo>();
            for (int i = 0; i < TIMES; i++)
            {
                Boo sample = pool[rnd.Next(pool.Count)];
                toFill.Add(new Boo()
                {
                    No = sample.No, SubNo = sample.SubNo
                });
            }
            Console.WriteLine("Count={0:N0}", pool.Count);
            for (int i = 0; i < 3; i++)
            {
                Console.WriteLine("Round {0}", i);
                Stopwatch sw = new Stopwatch();
                sw.Start();
                for (int j = 0; j < TIMES; j++)
                {
                    var boo = toFill[j];
                    //分別用GetCode1到GetCode4測試
                    boo.Code = GetCode4(boo.No, boo.SubNo);
                }
                sw.Stop();
                Console.WriteLine(" Time={0:N0}ms", sw.ElapsedMilliseconds);
            }
            //挑選三個抽樣檢查執行結果是否一致
            Console.WriteLine("{0} {1} {2}", 
                toFill[1].Code, toFill[10].Code, toFill[50].Code);
            Console.Read();
        }
        static string GetCode1(int n, int sn)
        {
            return pool.Single(o => o.No == n && o.SubNo == sn).Code;
        }
        static string GetCode2(int n, int sn)
        {
            return shuffled.Single(o => o.No == n && o.SubNo == sn).Code;
        }
        static string GetCode3(int n, int sn)
        {
            return dict[string.Format("{0}\t{1}", n, sn)].Code;
        }
        static string GetCode4(int n, int sn)
        {
            return strDict[string.Format("{0}\t{1}", n, sn)];
        }
 
    }
 
    class Boo
    {
        public int No;
        public int SubNo;
        public string Code;
    }
}

我用亂數建立了5萬多個元素的List<Boo>,每個Boo有No, SubNo, Code三個屬性;另外有一個約500筆Boo的目標集合,每筆待處理的Boo已經有No及SubNo屬性,程式需一一查出其對照的Code碼為何填入。程式中用了四種查詢方法:

1.GetCode1() – List<Boo>.Single(o => o.No == n && o.SubNo == sn)
2.GetCode2() – 同GetCode1,但List<Boo>被洗牌打亂順序
3.GetCode3() -- 將List<Boo>轉成Dictionary<string, Boo>,以No + "\t" + SubNo當Key查詢
4.GetCode4() -- 同GetCode3,但直接轉成Dictionary<string, string>,建出Key對Code字串對照表

我使用固定亂數種子的做法,以確定每次產生的測試資料都相同。而測試時會顯示List<Boo>的資料個數,重複執行三回合每次的耗時(ms),以及抽樣檢查第1,10,50筆結果的Code值,以檢核查表結果一致‧

執行數據如下:

GetCode1() 原始Lis<Boo>.Single()尋找

Count=52,803
Round 0
Time=59,356ms
Round 1
Time=59,738ms
Round 2
Time=59,296ms
C183 C436 C560

GetCode2() List<Boo>打亂順序,用.Single()尋找

Count=52,803
Round 0
Time=62,327ms
Round 1
Time=62,177ms
Round 2
Time=62,219ms
C183 C436 C560

GetCode3() 使用Dictionary<string, Boo>

Count=52,803
Round 0
Time=3ms
Round 1
Time=2ms
Round 2
Time=1ms
C183 C436 C560

GetCode4() 使用Dictionary<string, sting>

Count=52,803
Round 0
Time=3ms
Round 1
Time=1ms
Round 2
Time=1ms
C183 C436 C560

由測試結果來看,二者效率表現天差地別: 使用LINQ Where查詢,平均一筆耗時>0.1秒,總共耗時一分多鐘;而Dictionary做法500次查詢加起來也不超過3ms!! 另外,將集合順序打亂會導致執行時間稍長,但並不明顯。另外,我也測了Count=5,000、500筆時,GetCode1的時間約為6,000ms、600ms,差不多維持等比例。原則上,我個人認為這是依循List[Linear, O(n)] vs Dictionary[Hashtable, O(1)?] Big-O關聯產生的結果(純屬門外漢的推估,如有錯歡迎指正),而當我們寫where … select ... 時,往往會落入我們正在對Table用Primary Key當條件做查詢,而且資料全在記憶體中應該很快的錯覺,然而實際上卻只能無效率地靠Table Scan在集合中逐筆查找比對,很難快得起來。

由上述實驗可獲得一項結論: "依賴LINQ的Where查詢在大量資料中反覆查詢,很容易形成效能瓶頸。面對類似需求,可透過ToDictionary()簡單轉換成Dictionary,即可獲得可觀的效能提升。"


Comments

# by KKBruce

//使用相口亂數種子確保每次執行之測試資料相同 //使用相同亂數種子確保每次執行之測試資料相同 細節中的細節。 沒有你,我們只會"盲目"使用這些技術。

# by cycer

雖然學校都有教資料結構與演算法 但很少人注意到 所以說, 基礎還是很重要的

# by 小黑

大師,果然是大師

# by 佑翔

謝謝你,9527

# by chicken

怪,留言沒出現,重打一次 ~_~ LINQ是定義架構,實際上搜尋的演算法是能夠自訂的,只差在你用的情況有沒有實作索引之類的機制而已... 自己弄的話,要搞懂的地方比較多,這裡有個現成的 library, 能夠支援 indexed linq to object ... http://i4o.codeplex.com/

# by Ken Kin

典型的 deferred execution 問題

# by Ken Kin

典型的 deferred execution 問題

# by God

Good

# by Lynn

感覺就是在記憶體與效能之間的選擇, 由於近幾年記憶體便宜又大容量,確實可以犧牲記憶體以提高效率。 我也很愛用Dictionary, 還沒有Dictionray的時候, 用的是hashtable, 或是很多index表,加強大量查詢的速度, 然而針對資料本身較大的時候,記憶體的使用就明顯可觀, 有時就必須考量Server 記憶體的運作, 這中間的平衡,需要花時間try

# by Song

你好,想請問如果查詢的條件有很多例如.Where(x=>x.Id==filter.Id && x.Available=filter.Available) .... 更多條件這樣串下去的話該如何搭配Dictionary? 謝謝

# by Jeffrey

to Song, 篩選條件要能事先預期列舉,才能透過Dictionary加速,如果你指的情境是條件極多、串接方式又很彈性,要用 Dictionary 加速也是可能的但實作複雜度會高很多(相當於要搞一套自訂演算法),除非加速很有必要性,接受較慢但高度彈性的 LINQ 成本較低。

# by Mecer

你好, 我還是個 LINQ 的門外漢, 單純想了解一下 如果資料庫中 Table A = 30 萬筆 , Table B = 50 萬筆 用了許多的 Index 與有效率的 SQL Script 之後查出二者關聯的查詢結果 = 1000 筆資料 那麼, 若改用 LINQ 的做法 , 把這二個 Table 都載入到記憶體之中, 再透過 LINQ + Dictionary的語法, 把這 1000 筆資料撈出來 請問 , 哪一種的作法將會比較快呢? 謝謝

# by Jeffrey

to Mecer, SQL Index的加速效果跟Dictionary差不多,所以差異會在資料存取上,如果測試時SQL Server的資料沒有完全進記憶體Cache,我認為對記憶體物件+Dictionary比較佔便宜。(如果不考量一開始將全部資料載入記憶體所耗費的時間成本)

Post a comment