リストの高速検索<T>

Question

私は2つの一般的なリストを持っています。たとえば、List<A>とList<B>としましょう。

クラスAには、タイプがList<B>であるプロパティがあります。このプロパティはBタイプのオブジェクトを含み、オブジェクトAの他のいくつかのプロパティによってフィルタリングされます。だから、

：私はAをobjectにリストとしてすべてのオブジェクトBを追加したい

class A{ 
    public int Something1; 
    public int Something2; 
    public List<B> Something3; 
} 

class B{ 
    public int Anything1; 
    public int Anything2; 
} 

（プロパティにはSomething3と呼ばれる）、のオブジェクトA.Something1 == B.Anything1をしましょう。

質問：List<B>アイテムをList<A>に追加する最も効率的な方法は何ですか？両方のリストに数十万のオブジェクトがあることに注意してください。

（VS2010、C＃の、.Net4）私はそれがBのリストに存在する場合Anything1性質上

Answer 1

グループリストにB年代を追加する前に、地図の確認を使用して置く

Answer 2

辞書に入れる。その後のことができますAをループ年代的かつ効率的にBのリスト選び出す年代を：あなたが言及したように、多くのデータがある場合は

Dictionary<int, List<B>> beegroups = bees.GroupBy(b => b.Anything1).ToDictionary(g => g.Key, g => g.ToList()); 

foreach (A a in ayes) { 
    List<B> group; 
    if (beegroups.TryGetValue(a.Something1, out group)) { 
    a.Something3 = group; 
    } 
} 

Answer 3

、&挿入する操作を選択するのパフォーマンスは以下の順です。Generic Dictionaries in C#から

：

1. Dictionary<int,A>

   • 選択：O（1）（複雑さを意味する）
   • 追加：O（1）またはO（N）]
   • ハッシュテーブルに基づく

2. SortedDictionary<int,A>

   • 選択：O（n個のログ）
   • 追加：バイナリ検索ツリー

3. SortedList<int,A>

   • に基づいて、O（n個のログ）
   • 選択：O（log n）[またはO（n）]
   • 追加：O分別回収（かなりの配列）に基づいて、（n）は

データの数が比較的小さい場合、それはList<int, A>いいだろうということに注意してください。 （データのサイズによっては、上記の順序を並び替えることになる。）

一方、あなたは、C＃にCollection種類の容量を考慮する必要があります。 Collectionタイプはサイズ変更可能です。サイズが足りない場合、コレクションは以前よりも大きく再作成され、エレメントが再び挿入されます。この点は、コレクションのサイズをすでに知っている場合は、コレクションコンストラクターで容量を設定する必要があることを示しています。

Answer 4

各Aのリストを置き換えるのではなく、LINQをより効果的に使用する代替アプローチがあります。グループ結合を使用して、各グループの項目を対応するAに追加します。

List<A> myAs = ...; 
List<B> myBs = ...; 

var pairs = from a in myAs 
      join b in myBs on a.Something1 equals b.Anything1 into TheseBs 
      select new { A = a, TheseBs }; 

foreach (var pair in pairs) 
{ 
    pair.A.Something3.AddRange(pair.TheseBs); 
}