C# Сравнение двух списков разных объектов

Question

Я видел Quickest way to compare two List<>, но мне трудно адаптировать его к моей ситуации. Моя проблема в том, что списки имеют разные типы.

Мои списки так:

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

Вот что я сейчас:

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

Это работает и все, но O(n^2). Есть ли способ сделать это более эффективным? Решение в вопросах, которые я связывал выше, говорит, чтобы использовать .Except, но он не принимает лямбда.

Редактировать: Я упомянул об этом выше, но это по-прежнему помечено как дубликат. У меня нет двух списков одного и того же объекта. У меня есть два списка разных объектов. Тип1 и Type2 - разные типы. У них просто есть идентификатор, который мне нужно совместить.

Answer 1

Я бы рекомендовал преобразовать идентификаторы двух типов в 2 хэш-набора. Тогда вы можете

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 
} 

Answer 2

Except -метод имеет перегрузку, которая принимает IEqualityComparer<T> в качестве последнего аргумента.

Существует пример в MSDN: https://msdn.microsoft.com/en-us/library/bb336390.aspx

EDIT
Можно создать список анонимных объектов и сравнить их с помощью специальной IEqualityComparer<T>. Вот класс Comparer:

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 
} 

и выражение LINQ должен выглядеть следующим образом:

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

Я знаю, это плохой стиль, чтобы использовать динамический в этом случае, вы можете изменить его без каких-либо проблема с реальным типом.

Answer 3

Я не уверен в доступных методах C#/Linq. С алгоритмической точки зрения вы можете сортировать оба списка (обычно O(n*log(n))). Затем вам просто нужно просканировать списки (линейные, aka O(m+n), где m - количество элементов в списке 1 и n количество элементов в списке 2). Предполагая, что список 1 является более длинным, общая сложность составляет O(m*log(m)). В зависимости от реализации C# HashSet ответ Мердока может быть быстрее.