c# - 最も最適化された方法での 2 つのセットの交差

Question

2 つの値のセットが与えられた場合、それらの間に共通の要素があるかどうか、つまり、それらの交差が null かどうかを確認する必要があります。

この目的に (パフォーマンスの点で) 最も適しているのは、標準の C# コレクションのどれですか? linq2 つのリスト/配列の交差を見つけるための拡張メソッドがあることは知っていIntersectますが、私の焦点はBig-O notation.

また、2 つの集合の交点も見つけなければならない場合はどうすればよいでしょうか?

Answer 1

LINQ のIntersectメソッドを使用すると、2 番目のシーケンスが構築され、HashSetそれに対して最初のシーケンスの各要素がチェックされます。つまり、O(M+N) です...そしてfoo.Intersect(bar).Any()、アーリーアウトを取得するために使用できます。

もちろん、最初に 1 つの (どちらかの) セットを に保存する場合はHashSet<T>、各ステップでの封じ込めをチェックするもう 1 つのセットを反復処理することができます。ただし、最初にセットを作成する必要があります。

基本的に、何をするにも O(M+N) 問題があります - それよりも安くなることはありません (すべての要素を調べなければならない可能性が常にあります) ハッシュコードが妥当である場合、その複雑さを簡単に達成できるはずです。もちろん、一部のソリューションは他のソリューションよりも優れた定数係数を提供する場合があります...しかし、それは複雑さではなくパフォーマンスです;)

編集:コメントに記載されているようにISet<T>.Overlaps、静的な型ISet<T>または具体的な実装のいずれかを既に設定している場合は、呼び出すと、Overlaps何をしているのかが明確になります。両方のセットが として静的に型指定されている場合は、 の実装が引数を反復処理し、呼び出したセットの内容に対して各要素をチェックすることを期待しているため、(大小はセットのサイズに関して) をISet<T>使用します。それをオンにします。 larger.Overlaps(smaller)Overlaps