2015-11-24 3 views
5

私は問題の答えを見つけるのに苦労しています。私が取り組んでいることに固有のいくつかのコードがあり、Unionの仕組みに関するドキュメントを見つけることができません。 C#の中核となる力学。だから問題はこれです。C#Union vs連続したデータのリストが含まれています

私は、この例と同様に動作しますデータのセットを持っている:

 object[] someMainTypeArray = new object [n]; 
    List<object> objList2 = new List<object>(); 
    foreach (object obj in someMainTypeArray) { 
     List<object> objList1 = new List<object>() { "1","2","3" }; 
     //each obj has a property that will generate a list of data 
     //objList1 is the result of the data specific to obj 
     //some of this data could be duplicates 
     //Which is better, this: 
     foreach (object test in objList1) { 
      if (!objList2.Contains(test)) { 
       objList2.Add(test); 
      } 
     } 
     //or this: 
     objList2 = objList2.Union(objList1).ToList(); 
     //Also, assume this has to happen anywhere from 0 to 60 times per second 
    } 

は、連合はすべての仕事をやらせるために、それがより効率的ですか?あるいは、Containsを使って各要素を比較する方が良いでしょうか?

両方の場合、できるだけ少ない処理時間でユニークなリストを作成するにはどうすればよいですか?

これは効率が重要です。また、これは宿題ではなく、仕事関連のもので、学習に関連するものだけです。

リストは、最終的にきれいにされ、再投入されるように、実行時に連続しています。リストの変更は、この例に似ている最終的な結果リストが最終的なリストを提示するために使用され、そのリストが空の場合、その失敗条件、およびそのリストは空ではなく、その成功条件です。

は、ここで作成したリストのいずれかの問題のコードの抜粋です:

 Player.ClearMoves(); 
    List<Pair<BoardLocation, BoardLocation>> attacking = new List<Pair<BoardLocation, BoardLocation>>(); 
    foreach (ChessPiece p in Board[this.Player.Opponent]) { 
     if (p.TheoryMove(this.Location)) { 
      foreach (Pair<BoardLocation , BoardLocation> l in Utility.GetLocations(p.Location , this.Location)) { 
       if (!attacking.Contains(l)) { 
       attacking.Add(l); 
       } 
      } 
     } 
    } 
    if (attacking.Count < 1) { 
     return false; 
    } 
+0

ハッシュセットの代わりにリストを使用すると、Union()**(おそらく)効率的になる可能性があります。もしあなたがハッシュセットを使って自分ですれば、効率は少し上がりますが(ユニオンより)、私はそれが**実測された**パフォーマンスの問題であるときにだけ行います。 –

答えて

9

あなたはreference sourceEnumerable.Union実装を見つけることができます。

これは、それがどのように動作するかです:

public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) { 
    if (first == null) throw Error.ArgumentNull("first"); 
    if (second == null) throw Error.ArgumentNull("second"); 
    return UnionIterator<TSource>(first, second, null); 
} 

static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) 
{ 
    Set<TSource> set = new Set<TSource>(comparer); 
    foreach (TSource element in first) 
     if (set.Add(element)) yield return element; 
    foreach (TSource element in second) 
     if (set.Add(element)) yield return element; 
} 

あなたが見ることができるように、Unionは、これらのソースからの両方enumerables、降伏オブジェクトを反復処理します。すべてのLinqメソッドと同様に、リストを作成するのではなく、ジェネレータ関数として機能します。このリストは、.ToList()に電話すると作成されます。

重複を避けるため、Setを使用し、要素を生成する前に要素を追加しようとします。セットへの追加が成功した場合、要素はそこにまだ存在していないので、それが生成されます。

セットは要素が存在するかどうかを調べるのに非常に効率的です。それらは、償却された一定時間内に品目検索を提供する。したがって、あなたのobjList2.Containsよりはるかに効率的です。これは、各要素がその中に存在するかどうかを調べるために繰り返しリストを繰り返し処理する必要があります。

Unionは、入力列挙の順序を維持するために作成されています。必要がない場合は、これを完全にスキップして、最初にSetを使用してください。あなたはそれが構造を再利用するため、すべての時間を設定し、同じ目標に新しいアイテムを追加することを予定している場合、これは特に良いです:

HashSet<object> set = new HashSet<object>(); 

foreach (…) 
{ 
    List<object> objList1 = … 

    // expand the set with the items from `objList1` 
    set.UnionWith(objList1); 
} 

あなたが最初の場所でobjList1を作成回避し、ちょうどあなたを追加した場合はそれも良いだろうあなたのユースケースで可能な場合は、アイテムを直接セットに追加します。

+0

私はこのコードを見ましたが、具体的にどういう意味か分かりませんでした。しかし、そうであっても、複数のユニオンを実行し、最後にリストを返すことは効率的ですか?より効率的なリストを組み合わせる手段がありますか? – G1xb17

+0

私は自分のコードを表示していない唯一の理由は、タスクに関連する120行のコードがあるかもしれないからです。 – G1xb17

+1

複数の共用体を実行する場合は、すべての共用体に対して単一のセットを使用し、すべてのリストをループしてセットに要素を追加するカスタム・メソッドを実行する方がよいでしょう。 –

3

あなたは(UnionIteratorで検索)reference source for the LINQ extensionsを見れば、あなたはUnionが終わっ列挙された項目を追跡するためにSet<T>を使用することにより、内部で動作することを確認できます。残念ながら、Set<T>はライブラリの内部クラスであるため、直接使用することはできません。しかし、HashSet<T>と呼ばれる同様のコレクションがあります。

おそらく、実装の主な非効率性の1つは、外側ループの各繰り返しでobjList2の新しいリストを作成することです。これは毎回反復とメモリ割り当てをトリガーします。あなたがネストされたループを通じてリストを構築しているので、私は、次のいずれかを行うことをお勧めします:

  1. List<T>にすべてを追加し、重複を除外するために行われているとき.Distinctを使用しています。このアプローチでは、内部クラスSet<T>も使用しますが、Unionへの複数の呼び出しをチェーンするのと異なり、一意のリストを作成するためにはSetを1つだけ使用します。
  2. HashSet<T>を使用して、常にアイテムの一意のリストを持つコレクションを作成します。
+0

この実装には、私の詳細がたくさんあります。完全に作成されるのは、新しいリストを生成するために使用される関数です。この時点では、リストされているリストはすでにインスタンス化されているため、すべてを管理する「メインオブジェクト」も存在します。 – G1xb17

+0

質問にあるコード以外のものについてはコメントすることは難しいです。私は 'objList2 = objList2.Union(objList1).ToList();'という行を見ています。これにより、各繰り返しごとに新しいリストが作成されます。 – Erik

+0

これは、ループ内のリストのための方法です。外部から始まるリストは大部分が変わらず、要素を失うか要素を得ることができますが再初期化はできません。 – G1xb17

関連する問題