c# - 为什么 IEnumerable 慢而 List 快？

Question

遇到了这段代码。

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() 被评论时它很慢，当没有评论时 - 它很快。可复制here这怎么解释呢？我是否应该始终制作所有 ToList() 以确保速度(即在哪些情况下 IEnumerable 更可取)？请注意，我只是在谈论 linq to objects，我知道 linq to sql 惰性和其他东西。

Answer 1

这是因为延迟执行:当您注释掉 ToList 时，枚举是通过评估字典中每个项目的过滤器序列生成的。但是，当您执行 ToList 时，序列会在内存中“具体化”，因此所有计算都只执行一次。

没有 ToList 的第二个 Where 背后的逻辑如下所示:

// 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) 程序转换为 O(2*n)，包含两个大小为 n 的顺序循环。