13

我有课程：

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();

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

4

5 回答 5

29

您的猜测很接近 - Linq to Objects Except扩展方法在HashSet<T>内部使用 a 传入的第二个序列 - 这允许它在迭代第一个序列以过滤掉第二个序列中包含的元素时查找 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 变大时，这将变得非常慢，非常快。（这个解决方案也是错误的，因为它会创建重复的元素）。

于 2012-04-22T16:22:08.983 回答
2

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

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

这意味着它将a多次返回 list1 中的每个元素 - 对于blist2 中不等于的每个元素一次a。

对于“大”列表，这将需要很长时间。

于 2012-04-22T16:35:13.817 回答
2

from a in list1 from b in list2创建list1.Count * list2.Count元素和不一样list1.Except(list2)！

如果list1有 elements{ a, b, c, d }和list2elements { 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执行 with 的嵌套循环。O(m*n)使用哈希表，查询大致执行O(n)（忽略填充哈希表的成本）。

于 2012-04-22T16:36:55.277 回答
0

这就是我的想法。

IEnumerable<T> Except<T>(IEnumerable<T> a,IEnumerable<T> b)
{
    return a.Where(x => !b.Contains(x)).Distinct();
}
于 2014-02-24T11:06:58.487 回答
0

在我看来这会更有效率 

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.Contains(item))
        {
            yield return item;
        }
    }
}

包含是 O(1)

Add 是如果 Count 小于内部数组的容量，这个方法是 O(1) 操作。如果必须调整 HashSet 对象的大小，则此方法变为 O(n) 操作，其中 n 是 Count。

于 2016-09-16T00:14:58.630 回答