Tono Nam Tono Nam - 2 months ago 12
C# Question

how does except method work in linq

I have the classes:

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


I also have two large
List<SomeClass>
called
list1
and
list2


before I used to have:

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


and that took about 1 minute to execute. Now I have:

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


and that takes less than 1 second!

I will like to understand what does the Except method do. Does the method creates a hash table of each list and then perform the same comparison? If I will be performing a lot of this comparisons should I create a Hashtable instead?




EDIT



Now instead of having lists I have two
HashSet<SomeClass>
called
hashSet1
and
hashSet2


when I do:

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


that still takes a long time... What am I doing wrong?

Answer

Your guess was close - the Linq to Objects Except extension method uses a HashSet<T> internally for the second sequence passed in - that allows it to look up elements in O(1) while iterating over the first sequence to filter out elements that are contained in the second sequence, hence the overall effort is O(n+m) where n and m are the length of the input sequences - this is the best you can hope to do since you have to look at each element at least once.

For a review of how this might be implemented I recommend Jon Skeet's EduLinq series, here part of it's implementation of Except and the link to the 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;
        }
    }
}

Your first implementation on the other hand will compare each element in the first list to each element in the second list - it is performing a cross product. This will require n*m operations so it will run in O(n*m) - when n and m become large this becomes prohibitively slow very fast. (Also this solution is wrong as is since it will create duplicate elements).