Linq表现:Any vs. Contains

Question

这个问题关系到这一个,但不完全一样,我认为.

鉴于:

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)."

Answer 1

这两个查询基本上实现了相同的算法.它们将c1针对每个项目进行迭代c2,比较Bar两个对象的属性,并在找到匹配后立即返回.两种情况的渐近复杂性是相同的,这意味着随着两组的大小增加,它们都会同样很好地扩展(或者同样糟糕,因为情况恰好).在一个方法与另一个方法相关的开销中,两者之间可能存在微小的差异,但差异不会很大,并且随着集合的大小增加,它们将越来越小.没有任何真正的表现理由选择其中一个而不是另一个.

有一个选项,你没有显示它比其中任何一个快得多.您可以使用a Join来查找c1也存在的所有项目,c2而无需对序列进行线性搜索:

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

另一种选择是使用a HashSet而不是a List,因为它可以更容易搜索:

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

var query = c2.Where(item => set.Contains(item.Bar));

(这个解决方案与Join内部的解决方案非常接近.)

这两种解决方案将是一个很多比任何你提出的解决方案的速度更快.