2次元LINQ操作の効率的なデータ構造を作成する方法は？

Question

問題：2種類のオブジェクトがあり、BuildingとImprovementと呼ぶことができます。おおよそ30個のImprovementインスタンスがありますが、1〜1000個のBuildingがあります。 BuildingとImprovementの各組み合わせに対して、重い計算を実行して、結果をResultオブジェクトに格納する必要があります。

BuildingsとImprovementsは整数IDで表すことができます。

私はその後のことができるようにする必要があります。

• のアクセスが与えられ Buildingと Improvement効率的 （EDIT：さらに下のコメントを参照）のためのResult
• はすべてImprovementためResultの上の集計を実行します所与Buildingに対するS、.SUM（）と.Average（）のような
• 所与のためのすべてのBuilding秒間Result S上の同じ集計を実行します

これはWebサーバーのバックエンドで発生するため、メモリが問題になる可能性がありますが、速度が最も重要です。これまで

思考：

1. キーとして<BuildingID, ImprovementID>とDictionary<Tuple<int, int>, Result>を使用してください。これは私にスピーディーなインサートとシングルルックアップを与えるはずですが、私は.Where()と.Sum()の性能を懸念しています。
2. BuildingIDsに1つ、ImprovementIDsに1つ、値としてResultの2次元配列を使用します。さらに、BuildingIDおよびImprovementIDを対応する配列行/列インデックスにマップする2つのDictionary<int, int>を構築します。これは潜在的に最大1000 + Dictionary秒を意味する可能性があります、これは問題になりますか？
3. List<Tuple<int, int, Result>>を使用してください。私は間違っている可能性がありますが、これはO（n）のインサートで、これが最も効率が悪いと思います。

ここで明らかに優れたオプションがありませんか？

EDIT：集計された値のみです（BuildingとImprovement）。興味があります。私の答えを見てください。

Answer 1

私が持っていたとして答えてくれてありがとう、テストコードが本当に有益だった:)

私のためのソリューションは、LINQを見送る、と重い計算の後に手動で直接集計を実行することが判明とにかくBuilding and Improvementの各組み合わせを繰り返します。

また、オブジェクトがEntity Frameworkに永続化される前に計算を実行するために、オブジェクト自体をキーとして使用する必要がありました（つまり、IDはすべて0でした）。

コード：

public class Building { 
    public int ID { get; set; } 
    ... 
} 

public class Improvement { 
    public int ID { get; set; } 
    ... 
} 

public class Result { 
    public decimal Foo { get; set; } 
    public long Bar { get; set; } 
    ... 

    public void Add(Result result) { 
     Foo += result.Foo; 
     Bar += result.Bar; 
     ... 
    } 
} 

public class Calculator { 
    public Dictionary<Building, Result> ResultsByBuilding; 
    public Dictionary<Improvement, Result> ResultsByImprovement; 

    public void CalculateAndAggregate(IEnumerable<Building> buildings, IEnumerable<Improvement> improvements) { 
     ResultsByBuilding = new Dictionary<Building, Result>(); 
     ResultsByImprovement = new Dictionary<Improvement, Result>(); 
     for (building in buildings) { 
      for (improvement in improvements) { 
       Result result = DoHeavyCalculation(building, improvement); 

       if (ResultsByBuilding.ContainsKey(building)) { 
        ResultsByBuilding[building].Add(result); 
       } else { 
        ResultsByBuilding[building] = result; 
       } 

       if (ResultsByImprovement.ContainsKey(improvement)) { 
        ResultsByImprovement[improvement].Add(result); 
       } else { 
        ResultsByImprovement[improvement] = result; 
       } 
      } 
     } 
    } 
} 

public static void Main() { 
    var calculator = new Calculator(); 
    IList<Building> buildings = GetBuildingsFromRepository(); 
    IList<Improvement> improvements = GetImprovementsFromRepository(); 
    calculator.CalculateAndAggregate(buildings, improvements); 
    DoStuffWithResults(calculator); 
} 

私は私が望んでいたまさにその集計を知っていたので、私はそれをこのようにしました。よりダイナミックなアプローチが必要な場合は、おそらく@ MatthewWatsonのDictionary of Dictionariesのようなものになっていたでしょう。

Answer 2

一般的に、辞書は最も効率的なルックアップです。キーを介してアクセスすると、検索効率と操作効率の両方が一定のO（1）になります。これは、最初のポイント、アクセスに役立ちます。

2番目と3番目にはすべてのアイテムO（n）を歩く必要があるため、指定した順序で歩きたい場合を除いてスピードを上げる方法はありません。O（n * n） SortedDictionray O（n）を使用できますが、参照と操作の効率（O（log n））が損なわれます。

私はあなたが投稿する第1の解決策に行きます。

Answer 3

あなたは、たとえば、結果のデータを保持するために、「辞書の辞書」を使用することができます

//    Building ID ↓    ↓ Improvement ID 
var data = new Dictionary<int, Dictionary<int, Result>>(); 

これは、あなたがすぐに特定の建物のための改善点を見つけてみましょうでしょう。

しかし、特定の改善を含む建物を見つけるには、すべての建物を繰り返し処理する必要があります。ここではいくつかのサンプルコードです：

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

namespace Demo 
{ 
    sealed class Result 
    { 
     public double Data; 
    } 

    sealed class Building 
    { 
     public int Id; 
     public int Value; 
    } 

    sealed class Improvement 
    { 
     public int Id; 
     public int Value; 
    } 

    class Program 
    { 
     void run() 
     { 
      //    Building ID ↓    ↓ Improvement ID 
      var data = new Dictionary<int, Dictionary<int, Result>>(); 

      for (int buildingKey = 1000; buildingKey < 2000; ++buildingKey) 
      { 
       var improvements = new Dictionary<int, Result>(); 

       for (int improvementKey = 5000; improvementKey < 5030; ++improvementKey) 
        improvements.Add(improvementKey, new Result{ Data = buildingKey + improvementKey/1000.0 }); 

       data.Add(buildingKey, improvements); 
      } 

      // Aggregate data for all improvements for building with ID == 1500: 

      int buildingId = 1500; 
      var sum = data[buildingId].Sum(result => result.Value.Data); 
      Console.WriteLine(sum); 

      // Aggregate data for all buildings with a given improvement. 

      int improvementId = 5010; 

      sum = data.Sum(improvements => 
      { 
       Result result; 
       return improvements.Value.TryGetValue(improvementId, out result) ? result.Data : 0.0; 
      }); 

      Console.WriteLine(sum); 
     } 

     static void Main() 
     { 
      new Program().run(); 
     } 
    } 
} 

（与えられたIDを持つすべての改善のためのデータを合計するための）第2の集約をスピードアップするために、我々は第二の辞書を使用することができます。

//      Improvment ID ↓    ↓ Building ID 
var byImprovementId = new Dictionary<int, Dictionary<int, Result>>(); 

あなたは余分な辞書を持っているでしょう維持するが、それほど複雑ではない。このようにいくつかのネストされた辞書を持つと、あまりにも多くのメモリを取るかもしれませんが、考慮する価値があります。

以下のコメントに記載されているように、IDと辞書自体の型を定義する方が良いでしょう。一緒にそれを置くことはできます：

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

namespace Demo 
{ 
    sealed class Result 
    { 
     public double Data; 
    } 

    sealed class BuildingId 
    { 
     public BuildingId(int id) 
     { 
      Id = id; 
     } 

     public readonly int Id; 

     public override int GetHashCode() 
     { 
      return Id.GetHashCode(); 
     } 

     public override bool Equals(object obj) 
     { 
      var other = obj as BuildingId; 

      if (other == null) 
       return false; 

      return this.Id == other.Id; 
     } 
    } 

    sealed class ImprovementId 
    { 
     public ImprovementId(int id) 
     { 
      Id = id; 
     } 

     public readonly int Id; 

     public override int GetHashCode() 
     { 
      return Id.GetHashCode(); 
     } 

     public override bool Equals(object obj) 
     { 
      var other = obj as ImprovementId; 

      if (other == null) 
       return false; 

      return this.Id == other.Id; 
     } 
    } 

    sealed class Building 
    { 
     public BuildingId Id; 
     public int Value; 
    } 

    sealed class Improvement 
    { 
     public ImprovementId Id; 
     public int Value; 
    } 

    sealed class BuildingResults : Dictionary<BuildingId, Result>{} 

    sealed class ImprovementResults: Dictionary<ImprovementId, Result>{} 

    sealed class BuildingsById: Dictionary<BuildingId, ImprovementResults>{} 

    sealed class ImprovementsById: Dictionary<ImprovementId, BuildingResults>{} 

    class Program 
    { 
     void run() 
     { 
      var byBuildingId = CreateTestBuildingsById();   // Create some test data. 
      var byImprovementId = CreateImprovementsById(byBuildingId); // Create the alternative lookup dictionaries. 

      // Aggregate data for all improvements for building with ID == 1500: 

      BuildingId buildingId = new BuildingId(1500); 

      var sum = byBuildingId[buildingId].Sum(result => result.Value.Data); 
      Console.WriteLine(sum); 

      // Aggregate data for all buildings with a given improvement. 

      ImprovementId improvementId = new ImprovementId(5010); 

      sum = byBuildingId.Sum(improvements => 
      { 
       Result result; 
       return improvements.Value.TryGetValue(improvementId, out result) ? result.Data : 0.0; 
      }); 

      Console.WriteLine(sum); 

      // Aggregate data for all buildings with a given improvement using byImprovementId. 
      // This will be much faster than the above Linq. 

      sum = byImprovementId[improvementId].Sum(result => result.Value.Data); 
      Console.WriteLine(sum); 
     } 

     static BuildingsById CreateTestBuildingsById() 
     { 
      var byBuildingId = new BuildingsById(); 

      for (int buildingKey = 1000; buildingKey < 2000; ++buildingKey) 
      { 
       var improvements = new ImprovementResults(); 

       for (int improvementKey = 5000; improvementKey < 5030; ++improvementKey) 
       { 
        improvements.Add 
        (
         new ImprovementId(improvementKey), 
         new Result 
         { 
          Data = buildingKey + improvementKey/1000.0 
         } 
        ); 
       } 

       byBuildingId.Add(new BuildingId(buildingKey), improvements); 
      } 

      return byBuildingId; 
     } 

     static ImprovementsById CreateImprovementsById(BuildingsById byBuildingId) 
     { 
      var byImprovementId = new ImprovementsById(); 

      foreach (var improvements in byBuildingId) 
      { 
       foreach (var improvement in improvements.Value) 
       { 
        if (!byImprovementId.ContainsKey(improvement.Key)) 
         byImprovementId[improvement.Key] = new BuildingResults(); 

        byImprovementId[improvement.Key].Add(improvements.Key, improvement.Value); 
       } 
      } 

      return byImprovementId; 
     } 

     static void Main() 
     { 
      new Program().run(); 
     } 
    } 
} 

は最後に、ここでは、特定の改善のための建物/改善の組み合わせのすべてのインスタンスのデータを集計するのにかかる時間を決定し、辞書でタプルの辞書の結果を比較して修正されたバージョンです辞書の任意のデバッガ外で実行リリースビルドのための

マイ結果：

Dictionary of dictionaries took 00:00:00.2967741 
Dictionary of tuples took 00:00:07.8164672 

これは、辞書の辞書を使用するために非常に高速ですが、あなたはこれらの集計の多くを行うつもり場合にのみ重要です。

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

namespace Demo 
{ 
    sealed class Result 
    { 
     public double Data; 
    } 

    sealed class BuildingId 
    { 
     public BuildingId(int id) 
     { 
      Id = id; 
     } 

     public readonly int Id; 

     public override int GetHashCode() 
     { 
      return Id.GetHashCode(); 
     } 

     public override bool Equals(object obj) 
     { 
      var other = obj as BuildingId; 

      if (other == null) 
       return false; 

      return this.Id == other.Id; 
     } 
    } 

    sealed class ImprovementId 
    { 
     public ImprovementId(int id) 
     { 
      Id = id; 
     } 

     public readonly int Id; 

     public override int GetHashCode() 
     { 
      return Id.GetHashCode(); 
     } 

     public override bool Equals(object obj) 
     { 
      var other = obj as ImprovementId; 

      if (other == null) 
       return false; 

      return this.Id == other.Id; 
     } 
    } 

    sealed class Building 
    { 
     public BuildingId Id; 
     public int Value; 
    } 

    sealed class Improvement 
    { 
     public ImprovementId Id; 
     public int Value; 
    } 

    sealed class BuildingResults : Dictionary<BuildingId, Result>{} 

    sealed class ImprovementResults: Dictionary<ImprovementId, Result>{} 

    sealed class BuildingsById: Dictionary<BuildingId, ImprovementResults>{} 

    sealed class ImprovementsById: Dictionary<ImprovementId, BuildingResults>{} 

    class Program 
    { 
     void run() 
     { 
      var byBuildingId = CreateTestBuildingsById();   // Create some test data. 
      var byImprovementId = CreateImprovementsById(byBuildingId); // Create the alternative lookup dictionaries. 
      var testTuples  = CreateTestTuples(); 

      ImprovementId improvementId = new ImprovementId(5010); 

      int count = 10000; 

      Stopwatch sw = Stopwatch.StartNew(); 

      for (int i = 0; i < count; ++i) 
       byImprovementId[improvementId].Sum(result => result.Value.Data); 

      Console.WriteLine("Dictionary of dictionaries took " + sw.Elapsed); 

      sw.Restart(); 

      for (int i = 0; i < count; ++i) 
       testTuples.Where(result => result.Key.Item2.Equals(improvementId)).Sum(item => item.Value.Data); 

      Console.WriteLine("Dictionary of tuples took " + sw.Elapsed); 
     } 

     static Dictionary<Tuple<BuildingId, ImprovementId>, Result> CreateTestTuples() 
     { 
      var result = new Dictionary<Tuple<BuildingId, ImprovementId>, Result>(); 

      for (int buildingKey = 1000; buildingKey < 2000; ++buildingKey) 
       for (int improvementKey = 5000; improvementKey < 5030; ++improvementKey) 
        result.Add(
         new Tuple<BuildingId, ImprovementId>(new BuildingId(buildingKey), new ImprovementId(improvementKey)), 
         new Result 
         { 
          Data = buildingKey + improvementKey/1000.0 
         }); 

      return result; 
     } 

     static BuildingsById CreateTestBuildingsById() 
     { 
      var byBuildingId = new BuildingsById(); 

      for (int buildingKey = 1000; buildingKey < 2000; ++buildingKey) 
      { 
       var improvements = new ImprovementResults(); 

       for (int improvementKey = 5000; improvementKey < 5030; ++improvementKey) 
       { 
        improvements.Add 
        (
         new ImprovementId(improvementKey), 
         new Result 
         { 
          Data = buildingKey + improvementKey/1000.0 
         } 
        ); 
       } 

       byBuildingId.Add(new BuildingId(buildingKey), improvements); 
      } 

      return byBuildingId; 
     } 

     static ImprovementsById CreateImprovementsById(BuildingsById byBuildingId) 
     { 
      var byImprovementId = new ImprovementsById(); 

      foreach (var improvements in byBuildingId) 
      { 
       foreach (var improvement in improvements.Value) 
       { 
        if (!byImprovementId.ContainsKey(improvement.Key)) 
         byImprovementId[improvement.Key] = new BuildingResults(); 

        byImprovementId[improvement.Key].Add(improvements.Key, improvement.Value); 
       } 
      } 

      return byImprovementId; 
     } 

     static void Main() 
     { 
      new Program().run(); 
     } 
    } 
}