2つのICollection＆lt;＆gt;が存在するかどうかを確認する最も速い方法コレクションには同じオブジェクトが含まれます

StackOverflow https://stackoverflow.com/questions/308476

質問

2つの ICollection＆lt; T＆gt; コレクションにまったく同じエントリが含まれているかどうかを確認する最も速い方法は何ですか？ブルートフォースは明確で、もっとエレガントな方法があるのだろうかと思っていました。

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

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

役に立ちましたか？

解決

C5を使用

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

ContainsAll

  

＆quot;すべてのアイテムが   提供されたコレクションはこのバッグにあります
  （多重度のカウント）。
     の   探すアイテム。
  
  すべてのアイテムが   ＆quot; 

[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;
}

他のヒント

最初にコレクションの。カウントを比較します。同じカウントの場合は、すべての要素についてブルートフォース比較を実行します。最悪のシナリオはO（n）です。これは、要素の順序を同じにする必要がある場合です。

順序が同じではない2番目のケースでは、コレクション内で見つかった要素の数を保存するために辞書を使用する必要があります。これは可能なアルゴリズムです

  • コレクション数の比較：異なる場合はfalseを返します
  • 最初のコレクションを繰り返す
    • ディクショナリにアイテムが存在しない場合は、キー=アイテム、値= 1（カウント）のエントリを追加および入力します
    • アイテムが存在する場合、ディクショナリ内のアイテムのカウントを増やします。
  • 2番目のコレクションの反復
    • アイテムが辞書にない場合はfalseを返します
    • アイテムがディクショナリのデクリメントカウントにある場合
      • count == 0の場合、アイテムの削除;
  • Return Dictionary.Count == 0;

順序付けられたコレクションの場合、 System.Linq.Enumerable で定義された SequenceEqual（）拡張メソッドを使用できます：

if (firstCollection.SequenceEqual(secondCollection))

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

とにかく、同じ順序で同じエントリが含まれているかどうかを比較したい場合は、「ブルートフォース」 C＃2.0で唯一のオプションです。エレガントではないという意味は知っていますが、アトミック比較自体がO（1）である場合、プロセス全体はO（N）である必要があります。これはそれほど悪いことではありません。

エントリを同じ順序にする必要がある場合（同じであることに加えて）、最適化として、両方のコレクションを同時に反復処理し、各コレクションの現在のエントリを比較することをお勧めします。それ以外の場合、ブルートフォースが道です。

ああ、別の提案-コレクションクラスのEqualsをオーバーライドして、そこに等値を実装できます（ただし、プロジェクトによって異なります）。

再び、2つのセットを持つC5ライブラリを使用すると、次のように使用できます。

C5.ICollection<T> set1 = C5.ICollection<T> ();
C5.ICollection<T> set2 = C5.ICollecton<T> ();
if (set1.UnsequencedEquals (set2)) {
  // Do something
}

C5ライブラリには、最初に2つのセットのシーケンスされていないハッシュコードを実際にテストするヒューリスティックが含まれています（ C5.ICollection＆lt; T＆gt; .GetUnsequencedHashCode（）を参照）。セットは等しくないため、すべてのアイテムを繰り返して同等性をテストする必要はありません。

また、 C5.ICollection＆lt; T＆gt; は System.Collections.Generic.ICollection＆lt; T＆gt; を継承しているため、C5実装を使用できます.NETインターフェースを引き続き使用します（ただし、.NETのケチなインターフェースを介してより少ない機能にアクセスできます）。

ブルートフォースはO（n）を取ります-すべての要素を比較します（それらがソートされていると仮定します）。

ソートされていない場合、そのO（n * n）を推測します。

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

たとえば、コレクションが1つだけになるようにモデルを変更できますか？または、コレクションAのみのコレクション、Bのみのコレクション、両方のコレクションの3つのコレクション-AのみとBのみが空の場合、それらは同じです...おそらく完全に間違った接線になりますこちら...

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top