如何在linq中使用方法

Question

我有课:

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方法的作用.该方法是否为每个列表创建哈希表,然后执行相同的比较？如果我要进行大量的比较,我应该创建一个Hashtable吗？

---

编辑

现在我没有列表,而是有两个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和完整章节的链接:

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;
        }
    }
}

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