當心LINQ搜尋的效能陷阱

對於長年與資料庫、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,即可獲得可觀的效能提升。"

歡迎推文分享:
Published 20 October 2011 12:55 AM by Jeffrey
Filed under: ,
Views: 29,038



Comments

# KKBruce said on 19 October, 2011 06:44 PM

//使用相口亂數種子確保每次執行之測試資料相同

//使用相同亂數種子確保每次執行之測試資料相同

細節中的細節。

沒有你,我們只會"盲目"使用這些技術。

# cycer said on 19 October, 2011 09:20 PM

雖然學校都有教資料結構與演算法

但很少人注意到

所以說, 基礎還是很重要的

# 小黑 said on 19 October, 2011 11:33 PM

大師,果然是大師

# 佑翔 said on 20 October, 2011 03:32 AM

謝謝你,9527

# chicken said on 22 October, 2011 06:02 AM

怪,留言沒出現,重打一次 ~_~

LINQ是定義架構,實際上搜尋的演算法是能夠自訂的,只差在你用的情況有沒有實作索引之類的機制而已...

自己弄的話,要搞懂的地方比較多,這裡有個現成的 library, 能夠支援 indexed linq to object ...

http://i4o.codeplex.com/

# Ken Kin said on 12 August, 2012 09:02 PM

典型的 deferred execution 問題

# Ken Kin said on 12 August, 2012 09:03 PM

典型的 deferred execution 問題

# God said on 22 September, 2012 12:37 AM

Good

# Lynn said on 12 November, 2016 02:50 AM

感覺就是在記憶體與效能之間的選擇,

由於近幾年記憶體便宜又大容量,確實可以犧牲記憶體以提高效率。

我也很愛用Dictionary,

還沒有Dictionray的時候, 用的是hashtable,

或是很多index表,加強大量查詢的速度,

然而針對資料本身較大的時候,記憶體的使用就明顯可觀,

有時就必須考量Server 記憶體的運作,

這中間的平衡,需要花時間try

# Song said on 27 May, 2017 11:46 PM

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

謝謝

# Jeffrey said on 28 May, 2017 04:10 AM

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

Leave a Comment

(required) 
(required) 
(optional)
(required) 
(提醒: 因快取機制,您的留言幾分鐘後才會顯示在網站,請耐心稍候)

5 + 3 =

Search

Go

<October 2011>
SunMonTueWedThuFriSat
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345
 
RSS
創用 CC 授權條款
【廣告】
twMVC
最新回應

Tags 分類檢視
關於作者

一個醉心技術又酷愛分享的Coding魔人,十年的IT職場生涯,寫過系統、管過專案, 也帶過團隊,最後還是無怨無悔地選擇了技術鑽研這條路,近年來則以做一個"有為的中年人"自許。

文章典藏
其他功能

This Blog


Syndication