c# - 整数のコレクションで存在を確認する最も効率的な方法は何ですか?

Question

Web サービスに送信される整数の大きなリストがあります。ビジネス ルールでは、これらの値は一意でなければならないと規定しています。重複があるかどうかを確認する最も効率的な方法は何ですか? 値を知る必要はありません。2 つの値が等しいかどうかだけを知る必要があります。

最初は整数のジェネリック リストと list.Exists() メソッドを使用することを考えていましたが、これは O(n); のものです。

次に、Dictionary と ContainsKey メソッドを使用することを考えていました。しかし、必要なのはキーだけで、値は必要ありません。そして、これも線形検索だと思います。

リスト内の一意性を見つけるために使用するより良いデータ型はありますか? または、線形検索で立ち往生していますか?

Answer 1

次を使用しHashSet<T>ます。

HashSet クラスは、高パフォーマンスのセット操作を提供します。セットは、重複する要素を含まず、要素が特定の順序になっていないコレクションです

HashSet<T>を受け入れるコンストラクターIEnumerable<T>も公開します。List<T>コンストラクターに yourを渡すと、元の とは異なるアイテムのシーケンスを含むHashSet<T>'snew への参照が作成されます。HashSet<T>List<T>

Answer 2

ハッシュセットの仕事のように聞こえます...

Answer 3

フレームワーク 3.5 を使用している場合は、HashSetコレクションを使用できます。

それ以外の場合、最適なオプションはDictionary. 各アイテムの価値は無駄になりますが、それが最高のパフォーマンスを発揮します。

アイテムを後でカウントするのではなく、HashSet/Dictionary にアイテムを追加するときに重複をチェックすると、重複がある場合に O(n) よりも優れたパフォーマンスが得られます。これは、最初の重複を見つけた後に探し続ける必要がないためです.

Answer 4

数値のセットがまばらな場合は、他の人が提案するように HashSet を使用してください。

しかし、数字のセットの大部分が連続しており、時折ギャップがある場合は、数字のセットをソートされた配列または開始と終了のペアのバイナリ ツリーとして保存した方がはるかに優れています。次に、検索キーよりも小さい開始値が最大のペアを検索して検索し、そのペアの終了値と比較して、セットに存在するかどうかを確認できます。