インメモリLINQパフォーマンス

Question

LINQ to [お気に入りのプロバイダーをここに挿入する]以外にも、この質問はインメモリコレクションの検索またはフィルタリングに関するものです。

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

例：

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

この場合、listに対して'something'が順序付けされていない限り、すべてのアルゴリズムは少なくとも O（n）を使用します。その場合、検索は O（log （n））：バイナリ検索である必要があります。ただし、正しく理解すれば、このクエリは列挙によって解決されるため、<=>が以前に注文されていたとしても、 O（n）が必要です。

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

Answer 1

並列化でも、O（n）のままです。定数係数は異なります（コアの数によって異なります）が、nが変化しても合計時間は線形に変化します。

もちろん、さまざまなLINQ演算子の独自の実装を独自のデータ型で書くこともできますが、これらは非常に特定の状況でのみ適切です-述語はデータの最適化された側面。たとえば、年齢順に並べられた人のリストがある場合、特定の名前の人を見つけようとするクエリでは役に立ちません：）

述語を調べるには、デリゲートの代わりに式ツリーを使用する必要があり、人生はずっと難しくなります。

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

Answer 2

はい、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（キーを複数の値にマップ）が含まれています。このディクショナリ/ルックアップテーブルは1回作成して何度も使用できるため、LINQを集中的に使用するコードを桁違いに高速化できます。

Answer 3

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

これは、言語設計者がパフォーマンスを一般性と引き換えに決定した古典的なケースのようです。