如何在linq中使用方法

我有课程:

class SomeClass { public string Name{get;set;} public int SomeInt{get;set;} } class SomeComparison: IEqualityComparer { public bool Equals(SomeClass s, SomeClass d) { return s.Name == d.Name; } public int GetHashCode(SomeClass a) { return (a.Name.GetHashCode() * 251); } } 

我还有两个名为list1list2大型List

在我以前有:

  var q = (from a in list1 from b in list2 where a.Name != b.Name select a).ToList(); 

这花了大约1分钟来执行。 我现在有:

 var q = list1.Except(list2,new SomeComparison()).ToList(); 

这需要不到1秒!

我想了解Except方法的作用。 该方法是否为每个列表创建哈希表,然后执行相同的比较? 如果我将进行大量的这种比较,我应该创建一个Hashtable吗?


编辑

现在我没有列表,而是有两个名为hashSet1hashSet2 HashSet

当我做:

  var q = (from a in hashSet1 form b in hashSet2 where a.Name != b.Name select a).ToList(); 

那还需要很长时间……我做错了什么?

您的猜测很接近 – Linq to Objects Except扩展方法在内部对传入的第二个序列使用HashSet – 这允许它在迭代第一个序列时查找O(1)中的元素以过滤掉元素包含在第二个序列中,因此整体努力是O(n + m),其中n和m是输入序列的长度 – 这是你可以希望做的最好的,因为你必须至少查看一次每个元素。

有关如何实现这一点的回顾,我推荐Jon Skeet的EduLinq系列,这是它的实现部分,以及完整章节的链接:

 private static IEnumerable ExceptImpl( IEnumerable first, IEnumerable second, IEqualityComparer comparer) { HashSet bannedElements = new HashSet(second, comparer); foreach (TSource item in first) { if (bannedElements.Add(item)) { yield return item; } } } 

另一方面,您的第一个实现会将第一个列表中的每个元素与第二个列表中的每个元素进行比较 – 它正在执行交叉产品 。 这将需要n m个操作,因此它将在O(n m)中运行 – 当n和m变大时,这变得非常快速地变慢。 (此解决方案也是错误的,因为它会创建重复的元素)。

这两个代码示例不会产生相同的结果。

您的旧代码会创建两个列表的笛卡尔积 。

这意味着它将多次返回list1中的每个元素b – 对于list2中不等于a每个元素b a

使用“大”列表,这将花费很长时间。

from a in list1 from b in list2创建list1.Count * list2.Count元素并且与list1.Except(list2)

如果list1具有元素{ a, b, c, d }并且list2具有元素{ a, b, c } ,那么您的第一个查询将产生以下对:

 (a,a),(a,b),(a,c),  
 (b,a),(b,b),(b,c),  
 (c,a),(c,b),(c,c),  
 (d,a),(d,b),(d,c)

因为你排除了相同的项目,结果将是

 (a,a) ,(a,b),(a,c),  
 (b,a), (b,b) ,(b,c),  
 (c,a),(c,b), (c,c) ,  
 (d,a),(d,b),(d,c)

而且因为你只选择了对中的第一个元素,你就会得到

{ a, a, b, b, c, c, d, d, d }


第二个查询将产生{ a, b, c, d }减去{ a, b, c } ,即{ d }


如果在Exclude没有使用哈希表,则会产生使用O(m*n)执行的嵌套循环。 使用哈希表,查询近似用O(n)执行(忽略填充哈希表的成本)。

这是我想到的方式。

 IEnumerable Except(IEnumerable a,IEnumerable b) { return a.Where(x => !b.Contains(x)).Distinct(); } 

在我看来,这会更有效率

 private static IEnumerable ExceptImpl( IEnumerable first, IEnumerable second, IEqualityComparer comparer) { HashSet bannedElements = new HashSet(second, comparer); foreach (TSource item in first) { if (!bannedElements.Contains(item)) { yield return item; } } } 

包含是O(1)

如果Count小于内部数组的容量,则此方法为O(1)操作。 如果必须调整HashSet对象的大小,则此方法将成为O(n)操作,其中n为Count。