Custom intersect in lambda

Question

I would like to know if this is possible to solve using a lambda expression:

List<Foo> listOne = service.GetListOne();
List<Foo> listTwo = service.GetListTwo();
List<Foo> result = new List<Foo>();

foreach(var one in listOne)
{
    foreach(var two in listTwo)
    {
        if((one.Id == two.Id) && one.someKey != two.someKey)
           result.Add(one);
    }
}

Ronnironnica

Answer 1

Sure you can! You can use this overload of Linq's Intersect extension method which takes an IEqualityComparer<T>, like this:

public class FooComparer : IEqualityComparer<Foo> 
{
    public bool Equals(Foo x, Foo y)
    {
        return x.Id == y.Id && x.someKey != y.someKey;
    }

    public int GetHashCode(Foo x)
    {
        return x.Id.GetHashCode();
    }
}

...

var comparer = new FooComparer();
List<Foo> listOne = service.GetListOne();
List<Foo> listTwo = service.GetListTwo();
List<Foo> result = listOne.Intersect(listTwo, comparer).ToList();

Ludovick

Nice, thanks! It doesn't matter if I intersect list one on list two or vice versa, right? – Ronnironnica

@Ronnironnica I believe there may be some performance differences, depending on which set is bigger. And of course if you implement the IEqualityComparer in a way which isn't fully symmetrical, then it will make a difference. – Ludovick

Sooo... start with the biggest to be on the safe side? – Ronnironnica

In the original code, if there two items in listTwo that match one item in listOne, that one item out of listOne will be added to the result list twice. I haven't tried, but I believe that in your code that is not the case. – Joh

@Ronnironnica I don't recall the specifics about performance tuning, so you might want to run some tests first, if this is a performance-critical application. – Ludovick

Regarding the second argument in intersect: Do I have to put it in a separate class that implements IEqualityComparer? – Ronnironnica

Thank you. Final question: Is there any way to make the comparer class generic (as far as types are concerned)? So that I can add similar stuff to other types later on. IEqualityComparer<T> didn't work :) – Ronnironnica

@Ronnironnica Yes. IEqualityComparer<T> is an interface, not a delegate. I apologize for my earlier blunder. See my updated answer for a sample implementation. – Ludovick

@Ronnironnica You can try to make the comparer as generic as possible, but you'd have to have the id's / key's your comparing generalized, too. Without knowing the actual classes your concerned with, it's hard to say how that might look. – Ludovick

@Ludovick I just missed the <T> after FooComparer. Thanks a lot for helping! – Ronnironnica

Answer 2

listOne.SelectMany(x=>listTwo.Where(y=>x.Id==y.Id && x.someKey != y.someKey));

Modernize

It seems that Johan is concerned about performance. While this is a direct translation of his intial code, it also suffers from the same O(n x m) complexity. It is the least efficient of all the answers given so far. – Joh

Why not? The solution using join us much more efficient than his original code. While he could write code that is more efficient than the Linq solution, it would probably take him a long time and result in unreadable, unmaintainable code. – Joh

@KrisVandermotten question was solve using a lambda expression..OP never mentioned anything about performance..! – Modernize

I didn't say your answer is bad. I only added information to it for the benefit of OP and other readers. And I said "It seems that" because he asks about performance in the comments to other answers. – Joh

.SelectMany is performing nested loops. .Join is performing a hash lookup. I suggest you benchmark both answers on big lists. – Joh

Answer 3

var result = from one in listOne
             join two in listTwo on one.Id equals two.Id
             where one.SomeKey != two.SomeKey
             select one;

Update: It seems that some people feel that this is not answering the question, as it supposedly is not using lambdas. Of course it is, it's just using the friendly query syntax.

Here's the exact same code, only less readable:

var result = 
    listOne.Join(listTwo, one => one.Id, two => two.Id, (one, two) => new { one, two })
           .Where(p => p.one.someKey != p.two.someKey)
           .Select(p => p.one);

Joh

Answer 4

You may try:

var result = listOne.Join(listTwo,
    (one) => one,
    (two) => two,
    (one, two) => one,
    new MyFooComparer());

Where MyFooComparer could look like:

class MyFooComparer : IEqualityComparer<Foo>
{
    public bool Equals(Foo x, Foo y)
    {
        return x.Id == y.Id && x.someKey != y.someKey;
    }

    public int GetHashCode(Foo obj)
    {
        return obj.Id.GetHashCode();
    }
}

[UPDATE]

I was curious about the performance of Intersect vs. Join so I made a small performance comparison between my solution and @p.s.w.g.'s (listOne and listTwo have 10 items each):

var comparer = new MyFooComparer();
var sw = new Stopwatch();
sw.Start();
for (int i = 0; i < 100000; i++)
{
    var result1 = listOne.Intersect(listTwo, comparer).ToList();
}
Console.WriteLine("Intersect: {0}",sw.Elapsed);
sw.Restart();
for (int i = 0; i < 100000; i++)
{
    var result = listOne.Join(listTwo,
        (one) => one,
        (two) => two,
        (one, two) => one,
        comparer);
}
Console.WriteLine("Join:      {0}", sw.Elapsed);

The output:

Intersect: 00:00:00.1441810
Join:      00:00:00.0037063

Doralin

.net would tweak the code in some way..It's better you run those test's differently and by warming up for some time..This is not the way to benchmark – Modernize

@Anirudh, I totally agree, not the best way to test it. But even by reversing the order, the results are the same. – Doralin