C＃HashSet <T>（ObservableCollectionと比較して）<T>？

Question

C＃汎用ハッシュセット< T>検索のパフォーマンスはO（1）、ObservableCollectionの検索のパフォーマンスはO（n）でなければなりません。

私は大量の一意の要素を持っていますが、各要素には一意ではないDateTimeプロパティがあります。

各要素は、単純にDateTime.GetHashCode（）を返すことによってHashCodeを計算します。

今、データのサブセットを取得したいとします。私は300.000要素のコレクションにこのLINQクエリを実行する場合は2012年3月と2012年6月

var result = from p in this.Elements 
       where p.Date >= new DateTime(2012, 03, 01) && 
         p.Date <= new DateTime(2012, 30, 06 
       select p; 

の間で日付を持っているすべての要素、それは与えられた範囲内にある80個の要素を返すために〜25ミリ秒かかります - HashSet < T>またはObservableCollection < T>を使用するかどうかは関係ありません。

すべての要素を手動でループしてチェックすると、〜25 msという同じ時間がかかります。

しかし、私は、指定された範囲内のすべての日付のHashCodeを知っています。私のHashSet < T>から、指定されたHashCodesを持つすべての要素を取得することは可能ですか？私はそれがはるかに速くなると思う...

LINQクエリをスピードアップすることは可能ですか？私はそれが私のHashSetの特別な能力を利用しないと仮定します< T>？

Answer 1

ハッシュセットは、指定されたハッシュがセットに含まれているかどうかを判断する上で非常に効率的です。あなたのクエリは、ハッシュセットがIEnumerableを実装してセット全体を反復処理し、日付比較を行うという事実を使用します。ハッシュはまったく使用されません。このため、手動の方法ではクエリと同じ時間がかかるのです。

ハッシュセットのハッシュに基づいて要素を取得することはできません。セット内の要素の存在のみをテストできます。辞書は、あなたがそれを入手する必要がある場合には、あなたが望むものです（そうは思われません）

あなたのデータで何が必要なのかを決定し、そのために最適化された構造を使用してください。これは、複数の内部構造を維持する独自のクラスで、それぞれが効率的であるもの（範囲を検索するものと、複数のフィールドによる存在をチェックするものなど）、または必要に応じて既存の構造が存在する可能性があります。しかし、あなたのデータで何をしたいのかを知らなくても、アドバイスは困難です。

他に考慮すべき点は、あなたが時期尚早に最適化しているかどうかです。手動で検索するのに25msが十分に速ければ、おそらくIEnumerableを実装する任意の構造体で十分です。この場合、必要な他の基準に基づいて1つを選択することができます。

Answer 2

あなたは正しいデータ構造を使用していません。ソートされたリスト（Dateプロパティでソートされている）のようなものを使用する必要があります。そこで、範囲の始めと終わりをバイナリ検索できます。