C＃でオブジェクトの2つの大きなリストのプロパティを効率的に比較するにはどうすればよいですか？

Question

私は2つのリストのデータセットを持っていますが、どちらのリストでも一貫性のあるIDがありますが、異なるかもしれないし違うかもしれない他のプロパティもあります。 1つ以上のプロパティに基づいて異なるものを最も効率的に取得するにはどうすればよいですか？

私の通常のアプローチはこれに沿ったものでした。私のオブジェクトは次のように設定されています：

public class Person 
     { 
      public int ID { get; set; } 
      public string Name { get; set; } 
      public int Age { get; set; } 

      public bool IsEqual(Person other) 
      { 
       if (Name != other.Name) 
       { 
        return false; 
       } 
       if (Age != other.Age) 
       { 
        return false; 
       } 
       return true; 
      } 
     } 

ここで、IsEqualコンパレータを使用して、それと同等のオブジェクトを比較します。修正の人を見つけるための私の方法は以下のようであるその後、

そして：私のデータセットでは

public static List<Person> FindModifiedPeople(List<Person> listA, List<Person> listB) 
     { 
      var modifiedPeople = new List<Person>(); 
      foreach (var personA in listA) 
      { 
       var matchingPerson = listB.FirstOrDefault(e => e.ID == personA.ID); 
       if (matchingPerson == null) 
       { 
        continue; 
       } 

       if (!personA.IsEqual(matchingPerson)) 
       { 
        modifiedPeople.Add(personA); 
       } 
      } 
      return modifiedPeople; 
     } 

、私はListBの中にいる人ではなくLISTA気にしないので、私はをループする必要はありません。両方のリスト。リストBの要素をlistAでチェックするだけで、リストAの要素を使って変更された人のリストを返すことができます。

このアプローチは、合理的に小さいリストではうまくいきましたが、現在は約160,000人のリストが2つあり、このアプローチには数分かかります。この方法をより効率的にする方法はありますか？それでも必要なものを返すのですか？

Answer 1

あなたのリストをDictionary<int, Person>に変更することができれば、その人物のIDをキーとして使用することができます。これはO(n^2)ではなく、O(n)で実行されます。

public static List<Person> FindModifiedPeople(Dictionary<int, Person> dictA, Dictionary<int, Person> dictB) 
{ 
    var modifiedPeople = new List<Person>(); 
    foreach (var personA in dictA) 
    { 
     Person matchingPerson; 
     if(dictB.TryGetValue(personA.Key, out matchingPerson)) 
     { 
      if (!personA.Value.IsEqual(matchingPerson)) 
      { 
       modifiedPeople.Add(personA.Value); 
      } 
     } 
    } 
    return modifiedPeople; 
} 

また、あなたがそれを必要とするものに応じてだけでなく、他の辞書にリストから戻り値の型を変更することができます。

EDIT

@maccetturaが彼のコメントで指摘したように、あなたは本当に、equalsメソッドに建てオーバーライドする必要があります。それはあなたのコードをこのように見えるようにします。

public override bool Equals(Object obj) 
{ 
    if (obj == null || GetType() != obj.GetType()) 
     return false; 

    var otherPerson = (Person)obj; 

    if (Name != otherPerson.Name) 
    { 
     return false; 
    } 
    if (Age != otherPerson.Age) 
    { 
     return false; 
    } 
    return true; 
} 

これにより、独自のコードではなく、デフォルトのEqualsメソッドを使用することを想定しているコードでもコードを使用できます。

Answer 2

比較がボトルネックかどうか確認してください。そこ

var matchingPerson = listB.FirstOrDefault(e => e.ID == personA.ID); 

、あなたはforeachループに結合されたO（n）と、のlogartihmic複雑で検索を行っているの総複雑さを与える：私はこの問題は、あなたがこの行で行う検索を形成くると思いますO（n^2）である。その代わりに、辞書を先に作成することができますが、時間がかかりますが、参照がはるかに高速です。辞書はキーとしてIDを持つ必要があり、簡単にforeachループの前に、このように作成することができます。その後

var dictB = listB.ToDictionary(p => p.ID); 

、あなたのルックアップは、このように、はるかに高速になります：

Person matchingPerson; 
    if (dictB.TryGetValue(personA.ID, out matchingPerson)) 
    { 
     if (!personA.IsEqual(matchingPerson)) 
     { 
      modifiedPeople.Add(personA); 
     } 
    }