20

遇到了这段代码。

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 to objects，我知道 linq to sql 懒惰和东西。

4

4 回答 4

29

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

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

// 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的程序转换为每个具有两个大小顺序循环的程序。O(n^2)nO(2*n)n

于 2013-10-30T17:07:59.910 回答
14

LINQ 使用延迟执行。
除非您调用.ToList()，否则查询的结果永远不会存储在任何地方；相反，它会在您每次迭代结果时重新迭代查询。

通常，这要快得多。通常没有理由首先将所有结果存储在内存中。

但是，您的代码会反复迭代查询；每次调用Where()回调一次。

您应该用Join()call 和 no替换该行ToList()，这将比任何一种方法都快。

于 2013-10-30T17:08:01.177 回答
3

因为当您没有.ToList()调用时，list2实例化将遍历list字典中每个项目的整个可枚举。因此，如果您使用延迟执行，则从 O(n) 变为 O(n^2)。

于 2013-10-30T17:22:58.877 回答
2

它是由延迟执行引起的。IEnumerable 不必是静态集合。一般来说，它是一些数据源（dic在您的情况下）+所有方法和表达式（Where、Contains 等）导致最终集。

.ToList() 执行所有这些方法和表达式并生成最终结果。

因此，如果您使用 ToList()，它会生成一个标准的 .NET 列表（整数数组）并对该列表执行所有操作。

如果您不调用 ToList() （或任何其他 To 方法），则可以多次枚举 IEnumerable。

于 2013-10-30T17:11:58.393 回答