[解決済み] LINQメソッドの実行時の複雑さ（Big-O）にはどのような保証があるのでしょうか？

質問

私は最近LINQを使い始めたのですが、LINQのメソッドの実行時の複雑さについて言及したものを見たことがありません。明らかに、ここには多くの要因があるので、議論を単純な IEnumerable LINQ-to-Objects プロバイダーに限定して説明します。さらに、任意の Func セレクタ/ミューテータ/その他として渡されるものは、安価なO(1)操作であるとします。

シングルパス操作のすべてが明白なようです( Select , Where , Count , Take/Skip , Any/All など)は、シーケンスを一度だけ歩く必要があるので、O(n)になります。ただし、これでも怠慢には影響されます。

より複雑な演算については、より不明確です。集合のような演算子 ( Union , Distinct , Except など) を使って作業します。 GetHashCode をデフォルトで使うので、内部でハッシュテーブルを使っていると考えるのが妥当で、一般にこれらの演算も O(n) になります。では IEqualityComparer ?

OrderBy はソートが必要なので、O(n log n)を見ている可能性が高いです。すでにソートされている場合はどうでしょうか？もし私が OrderBy().ThenBy() と言って、両方に同じキーを提供するのはどうでしょうか？

私が見ることができたのは GroupBy (そして Join ) を、ソートかハッシュのどちらかを使って表示します。どちらなのでしょうか？

Contains は、O(n)であろう。 List では O(1)ですが HashSet - は、LINQが基礎となるコンテナをチェックして、高速化できるかどうかを確認するのでしょうか？

そして本当の質問ですが、これまで私は、操作がパフォーマンス的であることを信じていました。しかし、それを信頼してもよいのでしょうか。たとえば、STL コンテナでは、すべての操作の複雑さを明確に指定しています。.NETライブラリの仕様に、LINQのパフォーマンスに関する同様の保証はあるのでしょうか？

より多くの質問（コメントへの応答）。

オーバーヘッドについてあまり考えたことがありませんでしたが、単純なLinq-to-Objectsではあまりないと思っていました。CodingHorror の投稿は Linq-to-SQL について述べていますが、クエリの解析と SQL の作成がコストを追加することは理解できます - オブジェクト プロバイダーにも同様のコストがあるのでしょうか。もしそうなら、宣言型または関数型の構文を使用している場合、それは異なるのでしょうか？

どのように解決するのですか?

保証はほとんどありませんが、いくつかの最適化があります。

• インデックス付きアクセスを使用する拡張メソッド、例えば ElementAt , Skip , Last または LastOrDefault を実装しているかどうかを確認します。 IList<T> を実装しているかどうかを調べ、O(N)ではなくO(1)のアクセスを得られるようにします。

• は Count メソッドは ICollection の実装をチェックし、この操作が O(N) ではなく O(1) になるようにします。

• Distinct , GroupBy Join そして、私はセット・アグリゲーション・メソッド ( Union , Intersect と Except ) はハッシュを使うので、O(N²) ではなく O(N) に近くなるはずです。

• Contains がチェックします。 ICollection の実装があるかどうかをチェックし、その結果 は のような、基礎となるコレクションが O(1) である場合、O(1) になります。 HashSet<T> のように、基礎となるコレクションが O(1) であれば、は O(1) になる可能性がありますが、これは実際のデータ構造に依存し、保証されるものではありません。 ハッシュセットは Contains メソッドをオーバーライドするため、O(1)となります。

• OrderBy メソッドは安定したクイックソートを使用するので、O(N log N)平均ケースとなります。

組み込みの拡張メソッドのすべてではないにしても、ほとんどをカバーしていると思います。 Linq自体は効率的なデータ構造を利用しようとしますが、潜在的に非効率なコードを書くためのフリーパスではありません。