C# Compare Two Lists of Different Objects

Question

I saw Quickest way to compare two List<> but I'm having trouble adapting it to my situation. My issue is that the lists are of different types.

My lists are like this:

List<Type1> firstList;
List<Type2> secondList;

Here is what I have now:

foreach (Type1 item in firstList)
{
    if (!secondList.Any(x => x.Id == item.Id))
    {
        // this code is executed on each item in firstList but not in secondList
    }
}
foreach (Type2 item in secondList)
{
    if (!firstList.Any(x => x.Id == item.Id))
    {
        // this code is executed on each item in secondList but not in firstList
    }
}

This works and all, but is O(n^2). Is there a way to make this more efficient? The solution in the questions I linked above says to use .Except but it doesn't take a lambda.

Edit: I mentioned this above, but this is still being flagged as duplicate. I DO NOT have two lists of the same object. I have two lists of different objects. Type1 and Type2 are different types. They just both have an id that I need to match on.

How is it a duplicate? The question that you marked is comparing two lists of MyObject. I DO NOT have two lists of the same type. I have a Type1 and Type2, they just both have an Id that I need to match on. And I need to do different things if its in firstList but not secondList, versus if its in secondList but not firstList. So basically I need two sections that say `//do something here`. — vkapadia, Apr 09 '15 at 23:52

score 1 · Answer 1 · answered Apr 09 '15 at 22:44

1

I would recommend converting the Ids of the 2 types to 2 HashSets. Then you can

HashSet<int> a = new HashSet<int>(firstList.Select(o => o.Id));

HashSet<int> b = new HashSet<int>(secondList.Select(o => o.Id));
if (a.IsSubsetOf(b) && b.IsSubsetOf(a))
{
    //Do your thing
}

answered Apr 09 '15 at 22:44

Murdock

4,352
3
34
63

With this method, how do i know which one it is? I need to do different things if its in set a but not in set b, versus if its in set b but not set a. – vkapadia Apr 09 '15 at 23:49

Koopakiller · Answer 2 · 2015-04-10T00:08:54.663

The Except-method has an overload, which takes an IEqualityComparer<T> as the last argument.

There is a sample in the MSDN: https://msdn.microsoft.com/en-us/library/bb336390.aspx

EDIT
It is possible to create an list of anonymous objects and compare them with a special IEqualityComparer<T>. Here is the comparer class:

class MyEqualityComparer : IEqualityComparer<object>
{
    #region IEqualityComparer<object> Members

    bool IEqualityComparer<object>.Equals(object x, object y)
    {
        return (x as dynamic).Id == (y as dynamic).Id;
    }

    int IEqualityComparer<object>.GetHashCode(object obj)
    {
        return ((obj as dynamic).Id as object).GetHashCode();
    }

    #endregion
}

And the LINQ Expression should look like this:

var result = lst1.Select(x => new { Id = x.Id, Obj = x })
    .Except(lst2.Select(x => new { Id = x.Id, Obj = x }),
            new MyEqualityComparer())
    .Select(x => (x as dynamic).Obj as Type1);

I know, it is a bad style to use dynamic in this case, you can change it without any problem to a real type.

As far as i can tell, IEqualityComparer takes in one type to compare with each other. I need to do this with two different types, just that they both have the Id property that needs to be matched. — vkapadia, Apr 09 '15 at 23:50

score 0 · Answer 3 · answered Apr 09 '15 at 23:11

I'm not sure about the available C#/Linq methods. From an algorithmic point of view, you could sort both lists (usually O(n*log(n))). Then you just need to scan through the lists (linear, aka O(m+n) where m is the number of elements in list 1 and n the number of elements in list 2). Assuming list 1 is the longer list, the total complexity is O(m*log(m)). Depending on the C# HashSet implementation, the answer by Murdock might be faster though.

C# Compare Two Lists of Different Objects

3 Answers3

Linked