LINQ ToDictionary初始容量

我經常使用LINQ擴展方法ToDictionary，但是我想知道性能。沒有任何參數來定義的字典，並用10萬項以上列表的能力，這可能成爲一個問題：LINQ ToDictionary初始容量

IList<int> list = new List<int> { 1, 2, ... , 1000000 }; 
IDictionary<int, string> dictionary = list.ToDictionary<int, string>(x => x, x => x.ToString("D7"));

是否實現實際上採取list.Count並把它傳遞到構造函數詞典？或者是字典的大小足夠快，所以我不必擔心它？

來源

2012-05-29 Franky

你有沒有試過計算它的長度？ – Ian

執行實際上是否接受list.Count並將它傳遞給字典的構造函數？

No.據ILSpy，實施基本上是這樣的：

Dictionary<TKey, TElement> dictionary = new Dictionary<TKey, TElement>(comparer); 
foreach (TSource current in source) 
{ 
    dictionary.Add(keySelector(current), elementSelector(current)); 
} 
return dictionary;

如果輪廓你的代碼，並確定ToDictionary操作是你的瓶頸，它的瑣碎，使基於上面的代碼你自己的功能。

來源

2012-05-29 14:51:20 akatakritos

感謝您的回答。在這種情況下，我會嘗試使用自定義擴展來創建字典。 – Franky

實現是否實際上接受list.Count並將其傳遞給字典的構造函數？

這是一個實現細節，它對你沒有任何影響。

或者是字典調整速度夠快，所以我真的不必擔心它？

嗯，我不知道。只有您知道這是否實際上是您應用程序的瓶頸，以及性能是否可以接受。如果您想知道它是否足夠快，請編寫代碼並記下時間。正如Eric Lippert所說的那樣，如果你想知道兩匹馬的速度有多快，你是否會讓他們彼此競爭，或者你會問隨機的陌生人哪個更快？

這就是說，我很難成像這是任何實際應用中的瓶頸。如果將項目添加到字典是應用程序中的瓶頸，那麼您做錯了什麼。

來源

2012-05-29 14:43:18 jason

通常情況是，對ToDictionary的調用不應該是一個瓶頸，但我必須導入數百萬個數據，並將這些數據保留在字典中以便隨後創建引用。按照Ian的建議，它會告訴我需要多長時間，但是我想知道是否重新實現ToDictionary可以加速我的應用程序，如果我指定了容量？ – Franky

這聽起來像你正在做一次性進口？這怎麼可能是一個瓶頸？但是，我的初始點仍然存在。或者它的速度足夠快（你的第一匹馬），或者它不是，你應該編寫你自己的字典版本（你的第二匹馬），看看這兩匹馬中的哪一匹足夠快達到你的目的。我懷疑你會從兩者之間看到很多性能差異。 – jason

@Franky - 我敢肯定字典類會在每次調整大小時加倍，所以您只需要調整log2（n），所以在1,000,000條記錄的情況下，只有大約20個調整大小。至於這方面的表現，我不確定，但正如akatakritos所提到的那樣，實現一個佔用大小的重載應該是微不足道的。 –

我不知道如何調整字典的大小，但使用dotPeek.exe檢查實現後，表明實現不佔用列表的長度。

什麼代碼基本上做的是：

創建一個新的字典
疊代序列和添加項目

如果你發現這是一個瓶頸，這將是微不足道的創建自己的擴展方法ToDictionaryWithCapacity工作的東西，可以有實際計算其長度，而無需迭代整個事情。

剛剛掃描了Dictionary實施。基本上，當它開始填滿時，內部列表的大小几乎翻倍至接近總理。所以這不應該發生得太頻繁。

來源

2012-05-29 14:45:16

我不認爲這會成爲TBH的瓶頸。如果你有真正的抱怨和問題，那麼你應該在當時考慮一下，看看你是否可以改進它，也許你可以做分頁，而不是一次轉換所有東西。

來源

2012-05-29 14:47:09

實現是否實際上接受list.Count並將其傳遞給字典的構造函數？

它沒有。這是因爲調用Count（）會枚舉源，然後將其添加到字典將再次枚舉源。枚舉源不是一個好主意，例如，這會在DataReader上失敗。

或者是字典調整速度夠快，所以我真的不必擔心它？

Dictionary.Resize方法用於展開字典。它分配一個新的字典並將現有的項目複製到新的字典中（使用Array.Copy）。質數步驟中字典大小增加。

這不是最快的方法，但速度不夠快，如果你不知道大小。

來源

2012-05-29 14:59:25

'Count'和'Count（）'是不一樣的。 – leppie

Leppie，你說得對。但ToDictionary（）是IEnumerable的擴展方法，因此Count不可用。 Count（）也是IEnumerable的擴展方法。 –

@CarstenSchütte有時，擴展方法針對知道其「Count」或已編制索引的集合進行了優化。示例：http://stackoverflow.com/a/18200099/543814。 – Timo

LINQ ToDictionary初始容量

回答

相關問題