當心LINQ搜尋的效能陷阱
13 | 53,027 |
對於長年與資料庫、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比較佔便宜。(如果不考量一開始將全部資料載入記憶體所耗費的時間成本)