パフォーマンスを本気で気にするLINQプログラマのためのオペーレータ表
NOTE: こちらは以前Qiitaに投稿した記事のバックアップです。
標準ライブラリのLINQオペレータにはパフォーマンス向上のための様々なトリックが仕込まれている。 実装をざっと調べたので、その成果をここにまとめておく。
- 調査対象は.Net Core 2.。
- オーダーが同じだからと言ってパフォーマンスが同じとは限らない。
- 結構雑な調査なので信用しすぎないように。
- 項目について
- オーダーの記号について
集計メソッド
| メソッド名 | シグニチャの特殊化 | ソースの特殊化 | 時間計算量 | 備考 |
|---|---|---|---|---|
Aggregate |
$O(n)$ | |||
Any |
$O(n)$ | |||
All |
$O(n)$ | |||
Average |
$O(n)$ | |||
Contains |
$O(n)$ | |||
Count |
$O(n)$ | |||
ElementAt |
$O(n)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
ElementAtOrDefault |
$O(n)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
First |
$O(1)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
FirstOrDefault |
$O(1)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
Last |
$O(n)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
LastOrDefault |
$O(n)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
Max |
$O(n)$ | |||
Min |
$O(n)$ | |||
SequenceEqual |
$O(n)$ | 両シーケンスがICollectionの場合、事前に要素数チェックが入る。両シーケンスがIListの場合、イテレータではなくインデクサでアクセスするためcallvirt呼び出しが減る。 |
||
ICollection |
$O(n)$ | |||
IList |
$O(n)$ | |||
Single |
$O(1)$ | シーケンスがIListの場合、Countとインデクサにより処理される。 |
||
IList |
$O(1)$ | |||
Sum |
$O(n)$ | |||
ToArray |
$O(n)$ | シーケンスがIListProviderの場合、各インターフェースに実装されたアルゴリズムで処理される。 |
||
IListProvider |
$O(n)$ | |||
ToList |
$O(n)$ | |||
IListProvider |
$O(n)$ | |||
ToDictionary |
$O(n)$ | シーケンスが配列またはListの場合、専用のアルゴリズムで処理される。シーケンスが ICollectionの場合、Countをもとに初期キャパシティを取得する。 |
||
ICollection |
$O(n)$ | |||
T[] |
$O(n)$ | |||
List |
$O(n)$ | |||
ToHashSet |
$O(n)$ |
射影メソッド
| メソッド名 | シグニチャの特殊化 | ソースの特殊化 | コールスタック | 時間計算量 | 戻り値の特殊化型 | 備考 | |
|---|---|---|---|---|---|---|---|
| 最初の1件 | 全件 | ||||||
Append |
1 | $O(1)$ | $O(n)$ | AppendPrependIterator, Iterator, IListProvider |
AppendPrependIteratorはソースと前後のリンクリストを保持する。AppendPrependIteratorへのAppend/Prependはリンクリストを延長するだけなのでコールスタックが深くならない。 |
||
AppendPrependIterator |
0 | $O(1)$ | $O(n)$ | ||||
Prepend |
1 | $O(1)$ | $O(n)$ | AppendPrependIterator, Iterator, IListProvider |
|||
AppendPrependIterator |
0 | $O(1)$ | $O(n)$ | ||||
OfType |
1 | $O(1)$ | $O(n)$ | ||||
Cast |
1 | $O(1)$ | $O(n)$ | ||||
Concat |
1 | $O(1)$ | $\sum O(n)$ | ConcatIterator, Iterator, IListProvider |
ConcatIteratorはシーケンスのリンクを保持する。ConcatIteratorへのConcatはリンクを延長するだけなのでコールスタックが深くならない。 |
||
ConcatIterator |
0 | $O(1)$ | $\sum O(n)$ | ||||
DefaultIfEmpty |
1 | $O(1)$ | $O(n)$ | ||||
Distinct |
1 | $O(1)$ | $O(n)$ | Iterator, IListProvider |
|||
Except |
1 | $O(n_{inner})$ | $\sum O(n)$ | Setに依存。 |
|||
GroupJoin |
1 | $O(n_{inner})$ | $\sum O(n)$ | Lookupに依存。 |
|||
GroupBy |
1 | $O(n)$ | $O(n)$ | ||||
Intersect |
1 | $O(n_{inner})$ | $\sum O(n)$ | Setに依存。 |
|||
Join |
1 | $O(n_{inner})$ | $\sum O(n)$ | Lookupに依存。 |
|||
ToLookup |
1 | $O(n)$ | $O(n)$ | IListProvider |
戻り値の実体はLookup。 |
||
OrderBy |
1 | $O(n)$ | $O(n)$ | IPartition, IOrderedEnumerable |
|||
Reverse |
1 | $O(n)$ | $O(n)$ | ||||
Select |
Func<T, TResult> |
1 | $O(1)$ | $O(n)$ | Iterator, IListProvider |
配列、ListはIListと同じオーダーだが、一部のメソッド呼び出しにより強力な最適化が働く。セレクタにインデックスをとるオーバーロードは最適化が弱い。 |
|
Iterator |
1 | $O(1)$ | $O(n)$ | Iterator, IListProvider |
|||
T[] |
1 | $O(1)$ | $O(n)$ | Iterator, IPartition |
|||
List |
1 | $O(1)$ | $O(n)$ | Iterator, IPartition |
|||
IList |
1 | $O(1)$ | $O(n)$ | Iterator, IPartition |
|||
IPartition |
1 | $O(1)$ | $O(n)$ | Iterator, IPartition |
|||
Func<T, int, TResult> |
1 | $O(1)$ | $O(n)$ | ||||
SelectMany |
Func<TSource, IEnumerable<TResult>> |
1 | $O(1)$ | $O(n)$ | Iterator, IListProvider |
セレクタにインデックスをとるオーバーロードは最適化が弱い。 | |
Func<TSource, int, IEnumerable<TResult>> |
1 | $O(1)$ | $O(n)$ | ||||
Skip |
1 | $O(k)$ | $O(n)$ | Iterator |
|||
IIterator |
0 ～ 1 | $O(k)$ | $O(n)$ | Iterator |
|||
IPartition |
0 | $O(1)$ | $O(n)$ | IPartition |
|||
SkipWhile |
1 | $O(k)$ | $O(n)$ | ||||
SkipLast |
1 | $O(1)$ | $O(n)$ | ||||
Take |
1 | $O(1)$ | $O(k)$ | Iterator, IPartition |
|||
IPartition |
0 | $O(1)$ | $O(k)$ | Iterator, IPartition |
|||
IList |
1 | $O(1)$ | $O(k)$ | Iterator, IPartition |
|||
TakeWhile |
1 | $O(1)$ | $O(k)$ | ||||
TakeLast |
1 | $O(n)$ | $O(n)$ | ||||
IPartition |
0 | $O(1)$ | $O(k)$ | Iterator, IPartition |
|||
IList |
1 | $O(1)$ | $O(k)$ | Iterator, IPartition |
|||
Union |
1 | $O(1)$ | $\sum O(n)$ | UnionIterator, Iterator, IListProvider |
UnionIteratorはシーケンスのリンクを保持し、イテレート時に重複の除外を行う。ソースがUnionIteratorで、かつ同じcomparerを使っているときはリンクを追加するだけなのでコールスタックが深くならない。 |
||
UnionIterator |
0 ～ 1 | $O(1)$ | $\sum O(n)$ | UnionIterator, Iterator, IListProvider |
|||
Where |
1 | $O(k)$ | $O(n)$ | Iterator, IListProvider |
配列、Listは一部のメソッド呼び出しにより強力な最適化が働く。セレクタにインデックスをとるオーバーロードは最適化が弱い。 |
||
T[] |
1 | $O(k)$ | $O(n)$ | Iterator, IListProvider |
|||
List |
1 | $O(k)$ | $O(n)$ | Iterator, IListProvider |
|||
Func<T, int, bool> |
1 | $O(k)$ | $O(n)$ | Iterator, IListProvider |
|||
Zip |
1 | $O(1)$ | $\min(O(n))$ | ||||
最適化に用いられる型
Iteratorクラス
LINQオペレータで広く利用される抽象クラス。IEnumerable, IEnumeratorを実装している。
ステートとスレッドIDを管理しており、自身を生成したスレッド内かつ唯一の利用ならGetEnumeratorが自身を返すことでオブジェクト数を増やさないようになっていたりする。
ステートフィールドの解釈は子クラス側に委ねられており、OOP的にはあまりよろしくない設計となっているが、パフォーマンスを出すためには仕方ないことなのだろうか。
IListProviderインターフェース
ToArray, ToListの専用実装を用意できるようにするインターフェース。
IPartitionインターフェース
ランダムアクセス可能なシーケンスであることを表すインターフェース。参照型向けのSpanみたいなもの。
Lookupクラス
ILookupの実装。ToLookupやGroupByなどで用いられる、グループキーとシーケンスの軽量な辞書。
Setクラス
軽量なハッシュセットクラス。System.Collections.Generic.HashSetはコアライブラリで使うにはリッチすぎるということだろうか。
まとめ
- 同じオペレータを連続適用すると効率が良い(ことがそこそこある)
Select/Whereはインデックス込みで評価できるオーバーロードを使うと最適化が利かなくなったりする。
最後に
正直こういうの考える必要があるほどパフォーマンスが大事なら素直にforeachで書いた方がいいと思う。
