8

LINQ to [お気に入りのプロバイダーをここに挿入] についてというよりも、この質問はメモリ内コレクションの検索またはフィルター処理に関するものです。

IEnumerableorを実装するオブジェクトでLINQ（または拡張メソッドの検索/フィルタリング）が機能することを知っていますIEnumerable<T>。問題は、列挙の性質上、すべてのクエリの複雑さは少なくともO(n)ですか?

例えば：

var result = list.FirstOrDefault(o => o.something > n);

この場合、すべてのアルゴリズムは少なくともO(n)を要します。ただし、私の理解が正しければ、このクエリは列挙によって解決されるため、以前に注文した場合でもO(n)を取る必要があります。list'something'list

  • O(log(n))でクエリを解決するためにできることはありますか?
  • パフォーマンスが必要な場合、Array.Sort と Array.BinarySearch を使用する必要がありますか?
4

3 に答える 3

5

並列化しても、まだ O(n) です。定数係数は (コアの数に応じて) 異なりますが、n が変化すると、合計時間は直線的に変化します。

もちろん、独自のデータ型に対してさまざまな LINQ 演算子の独自の実装を作成することもできますが、それらは非常に特定の状況でのみ適切です。述語が最適化された側面でのみ動作することを確認する必要があります。データ。たとえば、年齢順に並べられた人々のリストを持っている場合、特定の名前を持つ人を見つけようとするクエリでは役に立ちません:)

述語を調べるには、デリゲートの代わりに式ツリーを使用する必要があり、作業は非常に困難になります。

私は通常、データ型のインデックス付き/順序付き/その他の性質を使用していることを明らかにし、常に適切に機能する新しいメソッドを追加すると思います。もちろん、これらの追加のメソッドをクエリ式から簡単に呼び出すことはできませんが、ドット表記で LINQ を使用することはできます。

于 2008-09-27T17:28:03.603 に答える
3

はい、Sklivvz が言ったように、一般的なケースは常に O(n) です。

ただし、多くの LINQ メソッドは、IEnumerable を実装するオブジェクトが実際に ICollection などを実装する場合の特殊なケースです。(これは IEnumerable.Contains で見たことがあります。)

実際には、これは、たとえば IEnumerable が実際に HashSet である場合、LINQ IEnumerable.Contains が高速な HashSet.Contains を呼び出すことを意味します。

IEnumerable<int> mySet = new HashSet<int>();

// calls the fast HashSet.Contains because HashSet implements ICollection.
if (mySet.Contains(10)) { /* code */ }

リフレクターを使用して、LINQ メソッドがどのように定義されているかを正確に確認できます。これが私がこれを理解した方法です。

ああ、LINQ にはメソッド IEnumerable.ToDictionary (キーを単一の値にマップする) と IEnumerable.ToLookup (キーを複数の値にマップする) も含まれています。このディクショナリ/ルックアップ テーブルは、一度作成すれば何度でも使用できるため、LINQ を多用するコードを桁違いに高速化できます。

于 2008-09-27T17:29:24.380 に答える
2

はい、そうでなければなりません。an の任意のメンバーにアクセスする唯一の方法は、IEnumerableそのメソッドを使用することです。つまり、O(n) です。

これは、言語設計者が一般性のためにパフォーマンスを犠牲にすることを決定した典型的なケースのようです。

于 2008-09-27T16:59:53.453 に答える