C# 哪个 .NET 集合更快：枚举 foreach Dictionary<>.Values 或 List<>？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15904625/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Which .NET collection is faster: enumerating foreach Dictionary<>.Values or List<>?
提问by Doug Domeny
Are one of these enumerations faster than the other or about the same? (example in C#)
这些枚举中的一个是否比另一个更快或大致相同？（在 C# 中的示例）
Case 1:
情况1：
Dictionary<string, object> valuesDict;
// valuesDict loaded with thousands of objects
foreach (object value in valuesDict.Values) { /* process */ }
Case 2:
案例2：
List<object> valuesList;
// valuesList loaded with thousands of objects
foreach (object value in valuesList) { /* process */ }
UPDATE:
更新：
Background:
背景：
The dictionary would be beneficial for keyed search elsewhere (as opposed to iterating through a list), but the benefit would be diminished if iterating through the dictionary is much slower than going through the list.
字典对于其他地方的键控搜索是有益的（与遍历列表相反），但是如果遍历字典比遍历列表慢得多，那么好处就会减少。
UPDATE: Taking the advice of many, I've done my own testing.
更新：根据许多人的建议，我已经完成了自己的测试。
First, these are the results. Following is the program.
首先，这些是结果。以下是程序。
Iterate whole collection Dict: 78 Keyd: 131 List: 76
迭代整个集合 Dict：78 Keyd：131 List：76
Keyed search collection Dict: 178 Keyd: 194 List: 142800
键控搜索集合 字典：178 键：194 列表：142800
using System;
using System.Linq;
namespace IterateCollections
{
public class Data
{
public string Id;
public string Text;
}
public class KeyedData : System.Collections.ObjectModel.KeyedCollection<string, Data>
{
protected override string GetKeyForItem(Data item)
{
return item.Id;
}
}
class Program
{
static void Main(string[] args)
{
var dict = new System.Collections.Generic.Dictionary<string, Data>();
var list = new System.Collections.Generic.List<Data>();
var keyd = new KeyedData();
for (int i = 0; i < 10000; i++)
{
string s = i.ToString();
var d = new Data { Id = s, Text = s };
dict.Add(d.Id, d);
list.Add(d);
keyd.Add(d);
}
var sw = new System.Diagnostics.Stopwatch();
sw.Start();
for (int r = 0; r < 1000; r++)
{
foreach (Data d in dict.Values)
{
if (null == d) throw new ApplicationException();
}
}
sw.Stop();
var dictTime = sw.ElapsedMilliseconds;
sw.Reset();
sw.Start();
for (int r = 0; r < 1000; r++)
{
foreach (Data d in keyd)
{
if (null == d) throw new ApplicationException();
}
}
sw.Stop();
var keydTime = sw.ElapsedMilliseconds;
sw.Reset();
sw.Start();
for (int r = 0; r < 1000; r++)
{
foreach (Data d in list)
{
if (null == d) throw new ApplicationException();
}
}
sw.Stop();
var listTime = sw.ElapsedMilliseconds;
Console.WriteLine("Iterate whole collection");
Console.WriteLine("Dict: " + dictTime);
Console.WriteLine("Keyd: " + keydTime);
Console.WriteLine("List: " + listTime);
sw.Reset();
sw.Start();
for (int r = 0; r < 1000; r++)
{
for (int i = 0; i < 10000; i += 10)
{
string s = i.ToString();
Data d = dict[s];
if (null == d) throw new ApplicationException();
}
}
sw.Stop();
dictTime = sw.ElapsedMilliseconds;
sw.Reset();
sw.Start();
for (int r = 0; r < 1000; r++)
{
for (int i = 0; i < 10000; i += 10)
{
string s = i.ToString();
Data d = keyd[s];
if (null == d) throw new ApplicationException();
}
}
sw.Stop();
keydTime = sw.ElapsedMilliseconds;
sw.Reset();
sw.Start();
for (int r = 0; r < 10; r++)
{
for (int i = 0; i < 10000; i += 10)
{
string s = i.ToString();
Data d = list.FirstOrDefault(item => item.Id == s);
if (null == d) throw new ApplicationException();
}
}
sw.Stop();
listTime = sw.ElapsedMilliseconds * 100;
Console.WriteLine("Keyed search collection");
Console.WriteLine("Dict: " + dictTime);
Console.WriteLine("Keyd: " + keydTime);
Console.WriteLine("List: " + listTime);
}
}
}
}
UPDATE:
更新：
Comparison of Dictionary with KeyedCollection as suggested by @Blam.
@Blam 建议将 Dictionary 与 KeyedCollection 进行比较。
The fastest method is iterating over an Array of KeyedCollection Items.
最快的方法是迭代 KeyedCollection Items 数组。
Note, however, that iterating over the dictionary values is faster than over the KeyedCollection without converting to an array.
但是请注意，在不转换为数组的情况下，遍历字典值比遍历 KeyedCollection 更快。
Note that iterating over the dictionary values is much, much faster than over the dictionary collection.
请注意，遍历字典值比遍历字典集合要快得多。
Iterate 1,000 times over collection of 10,000 items
Dictionary Pair: 519 ms
Dictionary Values: 95 ms
Dict Val ToArray: 92 ms
KeyedCollection: 141 ms
KeyedC. ToArray: 17 ms
Timings are from a Windows console application (Release build). Here is the source code:
计时来自 Windows 控制台应用程序（发布版本）。这是源代码：
using System;
using System.Collections.Generic;
using System.Linq;
namespace IterateCollections
{
public class GUIDkeyCollection : System.Collections.ObjectModel.KeyedCollection<Guid, GUIDkey>
{
// This parameterless constructor calls the base class constructor
// that specifies a dictionary threshold of 0, so that the internal
// dictionary is created as soon as an item is added to the
// collection.
//
public GUIDkeyCollection() : base() { }
// This is the only method that absolutely must be overridden,
// because without it the KeyedCollection cannot extract the
// keys from the items.
//
protected override Guid GetKeyForItem(GUIDkey item)
{
// In this example, the key is the part number.
return item.Key;
}
public GUIDkey[] ToArray()
{
return Items.ToArray();
}
//[Obsolete("Iterate using .ToArray()", true)]
//public new IEnumerator GetEnumerator()
//{
// throw new NotImplementedException("Iterate using .ToArray()");
//}
}
public class GUIDkey : Object
{
private Guid key;
public Guid Key
{
get
{
return key;
}
}
public override bool Equals(Object obj)
{
//Check for null and compare run-time types.
if (obj == null || !(obj is GUIDkey)) return false;
GUIDkey item = (GUIDkey)obj;
return (Key == item.Key);
}
public override int GetHashCode() { return Key.GetHashCode(); }
public GUIDkey(Guid guid)
{
key = guid;
}
}
class Program
{
static void Main(string[] args)
{
const int itemCount = 10000;
const int repetitions = 1000;
const string resultFormat = "{0,18}: {1,5:D} ms";
Console.WriteLine("Iterate {0:N0} times over collection of {1:N0} items", repetitions, itemCount);
var dict = new Dictionary<Guid, GUIDkey>();
var keyd = new GUIDkeyCollection();
for (int i = 0; i < itemCount; i++)
{
var d = new GUIDkey(Guid.NewGuid());
dict.Add(d.Key, d);
keyd.Add(d);
}
var sw = new System.Diagnostics.Stopwatch();
long time;
sw.Reset();
sw.Start();
for (int r = 0; r < repetitions; r++)
{
foreach (KeyValuePair<Guid, GUIDkey> w in dict)
{
if (null == w.Value) throw new ApplicationException();
}
}
sw.Stop();
time = sw.ElapsedMilliseconds;
Console.WriteLine(resultFormat, "Dictionary Pair", time);
sw.Reset();
sw.Start();
for (int r = 0; r < repetitions; r++)
{
foreach (GUIDkey d in dict.Values)
{
if (null == d) throw new ApplicationException();
}
}
sw.Stop();
time = sw.ElapsedMilliseconds;
Console.WriteLine(resultFormat, "Dictionary Values", time);
sw.Reset();
sw.Start();
for (int r = 0; r < repetitions; r++)
{
foreach (GUIDkey d in dict.Values.ToArray())
{
if (null == d) throw new ApplicationException();
}
}
sw.Stop();
time = sw.ElapsedMilliseconds;
Console.WriteLine(resultFormat, "Dict Val ToArray", time);
sw.Reset();
sw.Start();
for (int r = 0; r < repetitions; r++)
{
foreach (GUIDkey d in keyd)
{
if (null == d) throw new ApplicationException();
}
}
sw.Stop();
time = sw.ElapsedMilliseconds;
Console.WriteLine(resultFormat, "KeyedCollection", time);
sw.Reset();
sw.Start();
for (int r = 0; r < repetitions; r++)
{
foreach (GUIDkey d in keyd.ToArray())
{
if (null == d) throw new ApplicationException();
}
}
sw.Stop();
time = sw.ElapsedMilliseconds;
Console.WriteLine(resultFormat, "KeyedC. ToArray", time);
}
}
}
采纳答案by dasblinkenlight
This is relatively easy to check with a stopwatch:
这相对容易用秒表检查：
var d = new Dictionary<string, object>();
var s = new List<object>();
for (int i =0 ; i != 10000000 ; i++) {
d.Add(""+i, i);
s.Add(i);
}
var sw = new Stopwatch();
sw.Start();
foreach(object o in d.Values) {
if (o == null) throw new ApplicationException();
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
sw.Reset();
sw.Start();
foreach (object o in s) {
if (o == null) throw new ApplicationException();
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
This prints numbers that are reasonably close to each other:
这将打印出彼此相当接近的数字：
Dict List
---- ----
136 107
139 108
136 108
The Listalways wins, but the margins are not as large as one would expect, given the relative complexity of the two data structures.
该List总是获胜，但利润并不大正如人们所期望的那样，给出的两个数据结构相对复杂。
回答by nvoigt
回答by paparazzo
If you want lookup by key then Dictionary.
Dictionary lookup by key is very fast as that is what it is designed to do.
如果你想按键查找，那么字典。
按键查找字典非常快，因为这就是它的设计目的。
The difference in foreach will be minor.
foreach 的差异很小。
If the key is also a property then consider KeyedCollection
KeyedCollection Class
如果键也是属性，则考虑 KeyedCollection
KeyedCollection 类
Provides the abstract base class for a collection whose keys are embedded in the values.
为其键嵌入在值中的集合提供抽象基类。
As Servy commented pick the collection with the features you need
.NET has many collections.
System.Collections Namespaces
正如 Servy 评论的那样，选择具有您需要的功能的集合
。NET 有许多集合。
System.Collections 命名空间
And if your objects have a natural key that can be represented as an Int32 then consider OverRide GetHashCode().
如果您的对象具有可以表示为 Int32 的自然键，那么请考虑 OverRide GetHashCode()。
If your objects have a natural key of GUID then consider KeyedCollection and OverRide GetHashCode and Equals
如果您的对象具有 GUID 的自然键，请考虑 KeyedCollection 和 OverRide GetHashCode 和 Equals
And for seach on nonKey properties consider LINQ rather than ForEach with a break;
对于非键属性的搜索，请考虑使用 LINQ 而不是 ForEach 中断；
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections.ObjectModel;
using System.Diagnostics;
namespace IntIntKeyedCollection
{
class Program
{
static void Main(string[] args)
{
Guid findGUID = Guid.NewGuid();
GUIDkeyCollection gUIDkeyCollection = new GUIDkeyCollection();
gUIDkeyCollection.Add(new GUIDkey(findGUID));
gUIDkeyCollection.Add(new GUIDkey(Guid.NewGuid()));
gUIDkeyCollection.Add(new GUIDkey(Guid.NewGuid()));
GUIDkey findGUIDkey = gUIDkeyCollection[findGUID]; // lookup by key (behaves like a dict)
Console.WriteLine(findGUIDkey.Key);
Console.WriteLine(findGUIDkey.GetHashCode());
Console.WriteLine(findGUID);
Console.WriteLine(findGUID.GetHashCode());
Console.ReadLine();
}
public class GUIDkeyCollection : KeyedCollection<Guid, GUIDkey>
{
// This parameterless constructor calls the base class constructor
// that specifies a dictionary threshold of 0, so that the internal
// dictionary is created as soon as an item is added to the
// collection.
//
public GUIDkeyCollection() : base() { }
// This is the only method that absolutely must be overridden,
// because without it the KeyedCollection cannot extract the
// keys from the items.
//
protected override Guid GetKeyForItem(GUIDkey item)
{
// In this example, the key is the part number.
return item.Key;
}
}
public class GUIDkey : Object
{
private Guid key;
public Guid Key
{
get
{
return key;
}
}
public override bool Equals(Object obj)
{
//Check for null and compare run-time types.
if (obj == null || !(obj is GUIDkey)) return false;
GUIDkey item = (GUIDkey)obj;
return (Key == item.Key);
}
public override int GetHashCode() { return Key.GetHashCode(); }
public GUIDkey(Guid guid)
{
key = guid;
}
}
}
}
回答by Peter
Here is your test:
这是你的测试：
class speedtest
{
static void Main(string[] args)
{
int size = 10000000;
Dictionary<string, object> valuesDict = new Dictionary<string, object>();
List<object> valuesList = new List<object>();
for (int i = 0; i < size; i++)
{
valuesDict.Add(i.ToString(), i);
valuesList.Add(i);
}
// valuesDict loaded with thousands of objects
Stopwatch s = new Stopwatch();
s.Start();
foreach (object value in valuesDict.Values) { /* process */ }
s.Stop();
Stopwatch s2 = new Stopwatch();
s2.Start();
foreach (object value in valuesList) { /* process */ }
s.Stop();
Console.WriteLine("Size {0}, Dictonary {1}ms, List {2}ms",size,s.ElapsedMilliseconds,s2.ElapsedMilliseconds);
Console.ReadLine();
}
}
Outputs:
Size 10000000, Dictonary 73ms, List 63ms
However you should also test if you have hashing collisions in your dictionary. They can give you a different outcome.
但是，您还应该测试字典中是否存在散列冲突。他们可以给你不同的结果。
In cases of a real application, you have to consider the time spend creating, accessing and memory foot print of your structure.
在实际应用程序的情况下，您必须考虑创建、访问和存储结构所需的时间。
回答by CalebD
As others have said, premature optimization yadda yadda. Use the right collection for the right scenario and only worry about speed if it becomes a problem.
正如其他人所说，过早优化 yadda yadda。在正确的场景中使用正确的集合，如果出现问题，只需担心速度。
Anyway, the only way to know is to measure. I made a quick and dirty test which populates a dictionary and a list with 30,000 objects and then iterates them 10,000 times. Results are:
无论如何，唯一知道的方法就是测量。我做了一个快速而肮脏的测试，它填充了一个字典和一个包含 30,000 个对象的列表，然后迭代它们 10,000 次。结果是：
Dictionary: 2683ms
List: 1955ms
字典：2683ms
列表：1955ms
So, it would seem that Dictionary.Values is slightly slower to enumerate for whatever reason.
因此，无论出于何种原因，似乎 Dictionary.Values 的枚举速度都稍慢。
Here is the code:
这是代码：
void Main()
{
int i = 0;
var dict = new Dictionary<string, object>();
var list = new List<object>();
for (i = 0; i < 30000; i++)
{
var foo = new Foo();
dict.Add(i.ToString(), foo);
list.Add(foo);
}
var dictWatch = new Stopwatch();
dictWatch.Start();
for (i = 0; i < 10000; i++)
{
foreach (var foo in dict.Values) {}
}
dictWatch.Stop();
Console.WriteLine("Dictionary: " + dictWatch.ElapsedMilliseconds);
var listWatch = new Stopwatch();
listWatch.Start();
for (i = 0; i < 10000; i++)
{
foreach (var foo in list) {}
}
listWatch.Stop();
Console.WriteLine("List: " + listWatch.ElapsedMilliseconds);
}
class Foo {}
