6

C# の汎用 HashSet<T> 検索パフォーマンスは O(1) である必要があり、ObservableCollection<T> の検索パフォーマンスは O(n) である必要があります。

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

各要素は、DateTime.GetHashCode() を返すだけで HashCode を計算します。

ここで、データのサブセット、たとえば 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;

この LINQ クエリを 300.000 要素のコレクションに対して実行すると、指定された範囲内の 80 要素を返すのに約 25 ミリ秒かかります。HashSet<T> と ObservableCollection<T> のどちらを使用しても問題ありません。

すべての要素を手動でループしてチェックすると、同じ時間、約 25 ミリ秒かかります。

しかし、指定された範囲内にあるすべての Dates の HashCode は知っています。HashSet<T> から指定された HashCodes を持つすべての要素を取得することは可能ですか? その方が早いと思いますが…

LINQ クエリを高速化することは可能ですか? 私の HashSet<T> の特別な能力を利用していないと思いますか?

4

2 に答える 2

5

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

于 2012-05-17T16:47:30.220 に答える
4

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

ハッシュセットからハッシュに基づいて要素を取得することはできません。テストできるのは、セット内の要素の存在のみです。 辞書は、持っていることで取得する必要がある場合に必要なものです（そうではないようです）

データをどのように処理する必要があるかを判断し、そのために最適化された構造を使用します。これは、それぞれが1つの点で効率的な複数の内部構造（範囲の検索用と複数のフィールドによる存在によるチェック用など）を維持する独自のクラスである場合もあれば、ニーズに合った既存の構造がある場合もあります。しかし、データをどのように処理したいかを知らなければ、アドバイスするのは困難です。

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

于 2012-05-18T09:27:34.050 に答える