Linq
コレクションのイテレーションを気軽に回せる処理。
var intEnumerable = Enumerable.Range(0, 10); var intList = intEnumerable.ToList(); // 0, 1, 2, ... , 8, 9 var oddList = intEnumerable.Where(value => value % 2 == 1).ToList(); // 1, 3, 5, 7, 9
ここ数年でLinqに最適化が入っている
という話は知っていました。ただ、具体的にどうなのというのをちゃんと見たことがありませんでした。
IPartition<T>, IIListProvider<T>
Linqと言えばIEnumerable
、というイメージを持っていました。もちろん、MoveNext
してCurrent
を取ってくるのが基本ですからそれは間違いではないんですが、現在では特定の状況でパフォーマンス改善を図るためのより細かいインターフェースがありました。
IIListProvider<T>
using System.Collections.Generic; namespace System.Linq { internal interface IIListProvider<TElement> : IEnumerable<TElement> { TElement[] ToArray(); List<TElement> ToList(); int GetCount(bool onlyIfCheap); } }
つまり、これは直後にToArray
やToList
が来た場合に最適化するためのインターフェースと言えます。
何も考えずにIEnumerable
からToList
をしてしまうと、だいたいこういう処理になります。
var list = new List<T>(); foreach (var element in enumerable) { list.Add(element) };
enumerable
の数が多いと、List
の内部配列の再配置が頻発して酷く無駄なヒープアロケーションが発生します。なので、事前に要素数がわかるなら先に必要十分な配列長を確保したい気持ちがあります。それを独自に実装して呼び出させるためのインターフェース、ということですね。
例えば、OrderBy
で生成されうるイテレータクラスのToList
を見てみます。
OrderedEnumerableIterator.ToList
public List<TElement> ToList() { Buffer<TElement> buffer = new Buffer<TElement>(_source); int count = buffer._count; List<TElement> list = new List<TElement>(count); if (count > 0) { int[] map = SortedMap(buffer); for (int i = 0; i != count; i++) { list.Add(buffer._items[map[i]]); } } return list; }
確かにList
のキャパシティを指定して生成していますね。
IPartition<T>
using System.Diagnostics.CodeAnalysis; namespace System.Linq { /// <summary> /// An iterator that supports random access and can produce a partial sequence of its items through an optimized path. /// </summary> internal interface IPartition<TElement> : IIListProvider<TElement> { IPartition<TElement> Skip(int count); IPartition<TElement> Take(int count); TElement? TryGetElementAt(int index, out bool found); TElement? TryGetFirst(out bool found); TElement? TryGetLast(out bool found); } }
コレクションを全部見る必要が無いと思われる場合に最適化するためのインターフェースと考えられます。例えばIList<T>
型のインスタンスにSelect
を使うと生成されうるイテレータクラスのElementAt
を見てみましょう。
public TResult? TryGetElementAt(int index, out bool found) { if ((uint)index <= (uint)(_maxIndexInclusive - _minIndexInclusive) && index < _source.Count - _minIndexInclusive) { found = true; return _selector(_source[_minIndexInclusive + index]); } found = false; return default; }
sourceがIList
型だと知っているので、直接インデックスを渡して取得しているのがわかりますね。
終わり
C#を学び始めるとLinqは遅いと習ってしまいがちです。確かにListを回すならfor、配列ならforeachで良いですが、とはいえ、Linqには圧倒的な可読性、変更容易性の高さがあります。見てきたように、実は今ではLinqは可能なら無駄な処理を行わないように、という最適化もしっかり入っているので、Linqは遅いんだ、という先入観は卒業してもよいかもしれません。