c# - 除了方法在 linq 中如何工作

Question

我有类(class):

class SomeClass
{
   public string Name{get;set;}
   public int SomeInt{get;set;}
}


class SomeComparison: IEqualityComparer<SomeClass>
{
     public bool Equals(SomeClass s, SomeClass d)
     {
         return s.Name == d.Name;
     }

     public int GetHashCode(SomeClass a)
     {
         return (a.Name.GetHashCode() * 251);
     }
}

我还有两个大的List<SomeClass>称为 list1和 list2

以前我有:

 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 方法的作用。该方法是否为每个列表创建一个哈希表，然后执行相同的比较？如果我要执行很多这样的比较，我应该创建一个哈希表吗？

---

编辑

现在我没有列表，而是有两个 HashSet<SomeClass>称为 hashSet1和 hashSet2

当我这样做时:

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

这仍然需要很长时间...我做错了什么？

Answer 1

您的猜测很接近 - Linq to Objects Except扩展方法使用 HashSet<T>在内部对于传入的第二个序列 - 这允许它在 O(1) 中查找元素，同时迭代第一个序列以过滤掉第二个序列中包含的元素，因此总体工作量为 O(n+m) 其中n 和 m 是输入序列的长度 - 这是您希望做的最好的事情，因为您必须至少查看每个元素一次。

关于如何实现的回顾，我推荐 Jon Skeet 的 EduLinq 系列，这里是 Except 的实现部分。以及指向 full chapter 的链接:

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

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