c# - 2 つの ICollection があるかどうかを調べる最速の方法コレクションには同じオブジェクトが含まれています

Question

ICollection<T>2 つのコレクションにまったく同じエントリが含まれているかどうかを確認する最も速い方法は何ですか? 総当りは明らかですが、もっとエレガントな方法があるのではないかと考えていました。

C# 2.0 を使用しているため、可能であれば拡張メソッドは使用しないでください。

編集: 答えは、順序付けされたコレクションと順序付けられていないコレクションの両方にとって興味深いものであり、うまくいけばそれぞれで異なるでしょう。

score 4 · Accepted Answer

C5を使用

http://www.itu.dk/research/c5/

すべてを含む

" 提供されたコレクション内のすべてのアイテムがこのバッグにあるかどうかを確認します
(多重度を数えます)。
探すアイテム。

すべてのアイテムが見つかった場合は true。"

[Tested]

public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T
{
  HashBag<T> res = new HashBag<T>(itemequalityComparer);

  foreach (T item in items)
    if (res.ContainsCount(item) < ContainsCount(item))
      res.Add(item);
    else
      return false;

  return true;
}

score 3 · Accepted Answer

まずは比較。コレクションの数が同じ場合は、すべての要素を力ずくで比較します。最悪のシナリオは O(n) です。これは、要素の順序を同じにする必要がある場合です。

順序が同じでない 2 番目のケースでは、コレクション内で見つかった要素の数を格納するために辞書を使用する必要があります: 考えられるアルゴリズムは次のとおりです。

コレクション Count の比較 : 異なる場合は false を返します
最初のコレクションを繰り返す
- アイテムがディクショナリに存在しない場合は、キー = アイテム、値 = 1 (カウント) のエントリを追加します。
- アイテムが存在する場合、ディクショナリ内のアイテムのカウントを増やします。
2 番目のコレクションを繰り返す
- アイテムがディクショナリにない場合は、false を返します
- アイテムがディクショナリにある場合、アイテムのカウントを減らします
  - count == 0 の場合はアイテムを削除します。
Dictionary.Count == 0 を返します。

score 3 · Accepted Answer

順序付けられたコレクションの場合、次のようにSequenceEqual()定義された拡張メソッドを使用できSystem.Linq.Enumerableます。

if (firstCollection.SequenceEqual(secondCollection))

score 2 · Accepted Answer

同じエントリまたは同じ順序の同じエントリを意味しますか?

とにかく、同じエントリが同じ順序で含まれているかどうかを比較したい場合、C# 2.0 では「ブルートフォース」しか選択肢がありません。非エレガントの意味はわかりますが、アトミック比較自体が O(1) の場合、プロセス全体が O(N) になるはずです。これはそれほど悪くはありません。

score 1 · Accepted Answer

エントリを同じ順序にする必要がある場合 (同じであることに加えて)、最適化として、両方のコレクションを同時に反復し、各コレクションの現在のエントリを比較することをお勧めします。それ以外の場合は、力ずくで行く方法です。

ああ、もう 1 つの提案 - コレクションクラスの Equals をオーバーライドし、そこに等価性を実装することができます (ただし、プロジェクトによって異なります)。

score 1 · Accepted Answer

繰り返しますが、2 つのセットを持つ C5 ライブラリを使用すると、以下を使用できます。

C5.ICollection<T> set1 = C5.ICollection<T> ();
C5.ICollection<T> set2 = C5.ICollection<T> ();
if (set1.UnsequencedEquals (set2)) {
  // 何かをする
}

C5 ライブラリには、最初に 2 つのセットのシーケンス化されていないハッシュコードを実際にテストするヒューリスティックが含まれているC5.ICollection<T>.GetUnsequencedHashCode()ため (「参考文献」を参照)、2 つのセットのハッシュコードが等しくない場合に、等しいかどうかをテストするためにすべての項目を反復処理する必要はありません。

また、はからC5.ICollection<T>継承されSystem.Collections.Generic.ICollection<T>ているため、.NET インターフェイスを使用しながら C5 実装を使用できることにも注意してください (ただし、.NET のけちなインターフェイスを介してより少ない機能にアクセスできます)。

score 0 · Accepted Answer

ブルートフォースは O(n) を取ります - すべての要素を比較します (それらがソートされていると仮定します)。これは、それを容易にするデータのプロパティがない限り、あなたができる最善の方法だと思います。

ソートされていない場合は、O（n * n）だと思います。

その場合、マージソートに基づくソリューションがおそらく役立つと思います。

たとえば、コレクションが 1 つだけになるように再モデル化できますか? または 3 つのコレクション、1 つはコレクション A のみ、もう 1 つは B のみ、両方のコレクション - したがって、A のみと B のみが空の場合、それらは同じです...おそらく完全に間違った接線でオフになっている可能性がありますここ...

c# - 2 つの ICollection があるかどうかを調べる最速の方法コレクションには同じオブジェクトが含まれています

7 に答える 7

Related

Reference