Linq性能:任意与包含

本文关键字：包含 任意 性能 Linq | 更新日期: 2023-09-27 18:19:55

这个问题与这个问题有关，但不完全相同我认为。

给定：

class Foo
{
  public string Bar { get; set; }
}
...
var c1 = new List<Foo>() { ... };
var c2 = new List<Foo>() { ... };

以下2个循环给出相同的结果：

  foreach (var item in c2.Where(f => c1.Any(f1 => f1.Bar.Equals(f.Bar))))
  { ... }
  foreach (var item in c2.Where(f => c1.Select(f1 => f1.Bar).Contains(f.Bar)))
  { ... }

它们同样快吗？

与另一个问题的区别在于，这里额外的Select语句是否会改变底层集合性质的重要性。

换句话说：这个包含：吗

foos.Contains(foo1)

对与此相同的"种类集合"执行操作：

foos.Select(f=>f.Bar).Contains(foo1.Bar)

我可能天真的想法是："一旦我们支持Linq的Select，一切都只是‘Lists’，所以Any和Contains都是O（n）。"

Linq性能:任意与包含

这两个查询从根本上实现了相同的算法。它们将为c2中的每个项迭代c1，比较两个对象的Bar属性，并在找到匹配项后立即返回。这两种情况的渐近复杂性是相同的，这意味着随着两个集合的大小增加，它们的规模都会同样好（或者同样坏，因为情况恰好如此）。

在与一种方法相关的开销方面，两者之间可能存在微小差异，但差异不会很大，而且随着集合大小的增加，它们会越来越小。没有任何真正的表演理由来选择两者中的一个。

有一个选项是你没有显示的，它比这两个选项都快得多。您可以使用Join查找c1中也存在于c2中的所有项目，而无需通过以下序列进行线性搜索：

var query = from first in c1
    join second in c2
    on first.Bar equals second.Bar
    select first;

另一种选择是使用HashSet而不是List，因为它可以更容易地搜索：

var set = new HashSet<string>(c1.Select(item => item.Bar));
var query = c2.Where(item => set.Contains(item.Bar));

（这个解决方案非常接近Join内部的功能。）

这两种解决方案都将比您提出的任何一种解决方案快。

您的第一种方法将迭代和比较一次并返回结果。

第二个查询会比较慢，因为它会迭代并将Bar属性提取到集合中，然后迭代并与f.Bar进行比较以创建最终结果。

相关文章：