大きなリストの同じプロパティを持つオブジェクトを検索 - パフォーマンスが遅い

Question

私はオブジェクトの大きなList<MyClass>を持って、MyClass 600000の周りには10体の特性のように、のはproperty10まで... property1、property2などを言わせました。

リストのうち、いくつかのプロパティに同じ値を持つオブジェクトでList<MyClass>のListを取得したいとします。

これは、例えば、property2,property4,property8およびproperty10が同じオブジェクトを意味します。

これを行うにはどうすればよいですか？現在、私は私のList<MyClass>以上のループを行い、そのループ内で私はList<MyClass>.FindAll()を経由して、すべての類似したオブジェクトを取得し、ダミーコード：

forach(var item in myClassList) 
{ 
    if(!found.Contains(item)) 
    { 
     var similarObjects = myClassList.FindAll(x => x.property2 == item.property2 && x.property4 == item.property4 && x.property8 == item.property8 && x.property10 == item.property10); 

     //adding the objects to the "already found" list 
     foreach(var foundItem in similarOjbects) 
     { 
     found.Add(foundItem); 
     } 

    if(similarObjects.Count > 1) 
    { 
     similarObjectsList.Add(similarObjects); 
    } 
    } 
} 

しかし、それはList.FindAll()方法が非常に遅い、年齢を取ります。

もっと効率的なアルゴリズムがありますか？

Answer 1

あなたは非常に効率的にこの問題を解決するためにgroup byを使用することができます。

var grouped = 
    from item in myClassList 
    group item 
    by new {item.Property2, item.Property4, item.Property8, item.Property10}; 

あなたに、各グループが同じを持っているすべてのオブジェクトが含まれているグループのシーケンスを与えます指定されたプロパティの値。グループの結果のシーケンスの各グループ内のすべてのアイテムを反復処理するための一例として、

、あなたはこのような何か行うことができます。これは、各プロパティのタイプはIEquatable<T>とGetHashCode()を実装することを前提としていること

foreach (var group in grouped) 
{ 
    foreach (var item in group) 
    { 
     // Do something with item 
    } 
} 

注意を。あなたは、以下の@BertPersynによる可能性が言及したようPLINQに

を使用して

1A, 1B, 1C 
2A, 2B, 2C 
3A, 3B, 3C 

---

可能な最適化：出力上記

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace Demo 
{ 
    class Data 
    { 
     public string Name { get; set; } 
     public int Property1 { get; set; } 
     public int Property2 { get; set; } 
     public int Property3 { get; set; } 
     public int Property4 { get; set; } 
     public int Property5 { get; set; } 
     public int Property6 { get; set; } 
     public int Property7 { get; set; } 
     public int Property8 { get; set; } 
     public int Property9 { get; set; } 
     public int Property10 { get; set; } 
    } 

    class Program 
    { 
     static void Main(string[] args) 
     { 
      List<Data> myClassList = new List<Data> 
      { 
       new Data {Name = "1A", Property2 = 1, Property4 = 1, Property8 = 1, Property10 = 1}, 
       new Data {Name = "1B", Property2 = 1, Property4 = 1, Property8 = 1, Property10 = 1}, 
       new Data {Name = "1C", Property2 = 1, Property4 = 1, Property8 = 1, Property10 = 1}, 
       new Data {Name = "2A", Property2 = 2, Property4 = 2, Property8 = 2, Property10 = 2}, 
       new Data {Name = "2B", Property2 = 2, Property4 = 2, Property8 = 2, Property10 = 2}, 
       new Data {Name = "2C", Property2 = 2, Property4 = 2, Property8 = 2, Property10 = 2}, 
       new Data {Name = "3A", Property2 = 3, Property4 = 3, Property8 = 3, Property10 = 3}, 
       new Data {Name = "3B", Property2 = 3, Property4 = 3, Property8 = 3, Property10 = 3}, 
       new Data {Name = "3C", Property2 = 3, Property4 = 3, Property8 = 3, Property10 = 3}, 
      }; 

      var grouped = 
       from item in myClassList 
       group item 
       by new {item.Property2, item.Property4, item.Property8, item.Property10}; 

      foreach (var group in grouped) 
      { 
       Console.WriteLine(string.Join(", ", group.Select(item => item.Name))); 
      } 
     } 
    } 
} 

例：ここでは

はコンパイル可能な例ですおそらくPLINQを使ってこれをスピードアップします。

はそれを行うには、単に（.AsParallel()の追加に注意してください）groupedを生成するには、次の使用：

var grouped = 
    from item in myClassList.AsParallel() 
    group item 
    by new {item.Property2, item.Property4, item.Property8, item.Property10}; 

を判断するには、これは実際に物事をスピードアップした場合、あなたには、いくつかのタイミングを行うことが不可欠です。

Answer 2

まず、クラス内に一意のキー（ハッシュ）を返すメソッドGetUniqueKeyを追加します。そして

、使用は、同様のキーでアイテムを見つけるためにグループ化：

List<List<Item>> = items 
    .GroupBy(item => item.GetUniqueKey()) 
    .Select(g => g.ToList()) 
    .ToList(); 

GetUniqueKey方法は、必要とされる特性のタイプに基づいて実装され、最適化されるべきです。

GetUniqueKey例の方法自体は、最適化されないことがあり

public object GetUniqueKey() 
{ 
    return new { P1 = Prop1, P2 = Prop2 }; 
} 

、あなたは別のものを見つけることが

public string GetUniqueKey() 
{ 
    return Prop1.ToString() + "-" + Prop2.ToString(); 
} 

OR（より多くの最適化）：プロパティ1とProperty2が整数である場合たとえば、あなたは以下の方法を使用することができます最適化された実装。

全例：

class Item 
{ 
    public int Prop1 {get; set;} 

    public int Prop2 {get; set;} 

    public string GetUniqueKey() 
    { 
     return Prop1.ToString() + "-" + Prop2.ToString(); 
    } 
} 

public void DoWork() 
{ 
    Random rnd = new Random(); 

    List<Item> items = new List<Item>(); 

    for(int i = 0; i < 600000; i++) 
    { 
     items.Add(new Item { Prop1 = rnd.Next(1, 10) }); 
    } 

    for(int i = 0; i < 600000; i++) 
    { 
     items[i].Prop2 = rnd.Next(1, 13); 
    } 

    List<List<Item>> = items 
     .GroupBy(item => item.GetUniqueKey()) 
     .Select(g => g.ToList()) 
     .ToList(); 
}