为什么IEnumerable慢而List快? [英] Why IEnumerable slow and List is fast?
问题描述
输入此代码.
var dic = new Dictionary<int, string>();
for(int i=0; i<20000; i++)
{
dic.Add(i, i.ToString());
}
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key);//.ToList(); //uncomment for fast results
Console.WriteLine(list.GetType());
var list2 = dic.Where(f => list.Contains(f.Key)).ToList();
Console.WriteLine(list2.Count())
因此,对.ToList()进行注释时,它很慢,否则则很慢-很快.可复制的此处如何解释?我是否应该始终使用ToList()来确保速度(即在哪种情况下IEnumerable更可取)?注意,我只在谈论对象的linq,我知道sql惰性和其他东西的linq.
So when .ToList() is commented it's slow, when not - it's fast. Reproducable here How could this be explained? Should I always make everything ToList() to ensure speed (i.e. in which circumstances IEnumerable would be more preferable)? Note I'm talking only about linq to objects, I know linq to sql laziness and stuff.
推荐答案
这是由于延迟执行所致:当您注释掉ToList
时,枚举是通过评估以下对象的过滤器序列而产生的字典中的每个项目.但是,当您执行ToList
时,序列将在内存中物化",因此所有评估都将执行一次.
This is because of deferred execution: when you comment out ToList
, the enumeration is produced by evaluating the sequence of filters for each item in the dictionary. When you do a ToList
, however, the sequence is "materialized" in memory, so all the evaluations are performed exactly once.
没有ToList
的第二个Where
的逻辑如下:
The logic behind the second Where
without ToList
looks like this:
// The logic is expanded for illustration only.
var list2 = new List<KeyValuePair<int,string>>();
foreach (var d in dict) {
var list = new List<int>();
// This nested loop does the same thing on each iteration,
// redoing n times what could have been done only once.
foreach (var f in dict) {
if (f.Value.StartsWith("1")) {
list.Add(f.Key);
}
}
if (list.Contains(d.Key)) {
list2.Add(d);
}
}
ToList
的逻辑如下:
// The list is prepared once, and left alone
var list = new List<int>();
foreach (var f in dict) {
if (f.Value.StartsWith("1")) {
list.Add(f.Key);
}
}
var list2 = new List<KeyValuePair<int,string>>();
// This loop uses the same list in all its iterations.
foreach (var d in dict) {
if (list.Contains(d.Key)) {
list2.Add(d);
}
}
如您所见,ToList
将具有两个大小为n
的嵌套循环的O(n^2)
程序转换为具有两个大小为n
的顺序循环的O(2*n)
.
As you can see, the ToList
transforms an O(n^2)
program with two nested loops of size n
into O(2*n)
with two sequential loops of size n
each.
这篇关于为什么IEnumerable慢而List快?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!