9

我们在使用 LINQ 的一段代码中遇到了轻微的性能问题，它提出了一个关于 LINQ 在查找方面如何工作的问题

我的问题是这样的（请注意，我已经更改了所有代码，所以这是代码的指示性示例，而不是真实场景）：

给定

public class Person {
 int ID;
 string Name;
 DateTime Birthday; 
 int OrganisationID;
}

如果我有一个说 100k Person 对象的列表，然后是一个日期列表，比如 1000，我运行以下代码：

var personBirthdays = from Person p in personList
    where p.OrganisationID = 123
    select p.Birthday;

foreach (DateTime d in dateList)
{
    if (personBirthdays.Contains(d))
        Console.WriteLine(string.Format("Date: {0} has a Birthday", d.ToShortDateString()));
}

生成的代码将是以下代码的迭代：

100k（需要执行的循环以查找组织 ID 为 123 的用户）
乘以
1000（列表中的日期数量）
乘以
x（需要检查组织 ID 为 123 的用户数量） )

这是很多迭代！

如果我将代码 personBirthdays 更改为：

List<DateTime> personBirthdays = 
        (from Person p in personList
        where p.OrganisationID = 123
        select p.Birthday).ToList();

这应该将 100k 作为倍数删除，并且只执行一次？

所以你会有 100k + (1000 * x) 而不是 (100k * 1000 * x)。

问题是这似乎太容易了，我确信 LINQ 在某处做了一些聪明的事情，这应该意味着这不会发生。

如果没有人回答，我会进行一些测试并报告回来。

清晰度更新： 我们不考虑数据库查找，该personList对象是内存中列表对象。这都是 LINQ-to-Objects。

4

3 回答 3

8

这应该将 10k 作为倍数删除，并且只执行一次？

这意味着不是迭代personList100k 次，而是为每个迭代where执行andselect操作，您将迭代生成的100k 次，并且and操作只会在底层数据源上执行一次。Listwhereselect

问题是这似乎太容易了，我确信 LINQ 在某处做了一些聪明的事情，这应该意味着这不会发生。

不，您的第一个查询只是您不应该使用 LINQ 执行的操作，如果您计划多次迭代它们（这是您更改的内容），您应该获取查询结果并将它们放入数据结构中.

您可以通过使用适当的数据结构进一步改进此查询。在 a 上搜索List效率相当低，因为它需要进行线性搜索。最好使用 aHashSet来存储查询的结果。在平均情况下， A 的HashSet搜索速度为 O(1)，而 a 的搜索时间为 O(n) List。

var dates = new HashSet<DateTime>(from Person p in personList
                                  where p.OrganisationID = 123
                                  select p.Birthday);

foreach (DateTime d in dateList.Where(date => dates.Contains(date)))
{
    Console.WriteLine(string.Format("Date: {0} has a Birthday", d.ToShortDateString()));
}
于 2012-12-11T16:00:25.737 回答
3

这是一个典型的select n+1问题，你申请后.ToList()你已经部分解决了。下一步可能是：您不断迭代personBirthdays列表，将其替换为HashSet，您可以Contains(d)更快地执行并删除重复项：

var personBirthdays = new HashSet<DateTime>((from Person p in personList
    where p.OrganisationID = 123
    select p.Birthday).ToArray());
于 2012-12-11T16:01:41.807 回答
0

我假设您指的是 LINQ-to-Objects，因为每个 LINQ 提供程序都有自己的实现（LINQ-to-SQL、LINQ-to-Entities、LINQ-to-XML、LINQ-to-anything）。

以您的示例为例personBirthdays，创建该表达式的目的是为了遍历整个结果集并不是一个定论，因此 LINQ 无法自动将结果具体化为数组或列表。

这些操作非常不同：

personBirthdays.Distinct()
personBirthdays.FirstOrDefault(b => b.Month == 7)
personBirthdays.Select(b => b.Year).Distinct()

LINQ 作为一种“聪明”的技术，它允许构建表达式树并推迟执行。这就是阻止 - 在上面的第三个示例中 - 100k 迭代来获得生日，然后再 100k 来选择年份，然后是最终的、昂贵的传递来组装不同的值。

LINQ 使用者（你）必须拥有表达式的命运。如果您知道结果集将被迭代多次，那么您有责任将它们具体化为数组或列表。

于 2012-12-11T16:08:00.163 回答