C#における「列挙」の意味と、LINQについて。
こないだ会社の先輩と話しててあれこれ考えたので、自分がLINQを理解した過程を言語化してみる。
対象は、とりあえずC++あたりの適当な言語で数年程度の経験がある人。プログラミングの地力さえあれば、C#についてはなんとなく読み書きできる程度で構わない。LINQに対する解説は世の中に溢れてるので、ここでは特にその内部実装にフォーカスしてみる。「わかってるひと」向けには、「おまじない」とか一切ナシのガチ解説が最短距離だと信じてる。
C#における「ループ」の実態
foreachの中身
以下のコードについて考える。
var array = new int[] { 0, 1, 2, 3, 4 };
foreach (var item in array) {
Console.WriteLine(item);
}これをビルドしてILSpyで開くと、コンパイラによって以下のように展開されていることがわかる。
var array = new int[] { 0, 1, 2, 3, 4 };
for (int i = 0; i < array.Length; i++) {
Console.WriteLine(array[i]);
}次にこのコード。
var list = new List<int> { 0, 1, 2, 3, 4 };
foreach (var item in list) {
Console.WriteLine(item);
}こうなる。
using (List<int>.Enumerator enumerator = new List<int> { 0, 1, 2, 3, 4 }.GetEnumerator()) {
while (enumerator.MoveNext()) {
Console.WriteLine(enumerator.Current);
}
}GetEnumerator()とか見慣れないのが出てきたけど、とりあえずここで大事なのは、foreachというのはあくまでシンタックスシュガーであって、実際にはforなりwhileなりに展開されている、ということ。
たぶんここが、LINQを理解する第一歩。
イテレータの使われ方
EnumeratorってのはC++でいうところのiteratorだと思っておけば問題ない。というわけで、List<T>.Enumerator.MoveNext()の実装を追ってみる。以下はその抜粋。
public bool MoveNext() {
List<T> localList = list;
if ((uint)index < (uint)localList._size) {
current = localList._items[index];
index++;
return true;
}
return MoveNextRare();
}
private bool MoveNextRare() {
index = list._size + 1;
current = default(T);
return false;
}↑の4行目にあたる処理で、リストの要素の実体（localList_.items[index]）が評価されてることがわかる。つまりC++の場合と同じく、MoveNext()の中でリストのindex番目の要素が選択されて、current変数（Enumerator.Currentの実体）に代入されることになる。
展開後の foreach における「セレクタ」の呼び出しタイミング
イテレータとセレクタ
イテレータを経由してindex番目の要素を取り出す処理をセレクタと呼ぶことにする。C#の場合はインデクサもIList<T>に定義されているインターフェイスのひとつで、実態はよくあるメンバ関数と同じだったりもする。なので、MoveNext()は以下のように書き換えることもできなくはない。
public bool MoveNext(Func<List<T>, int, T> selector) {
List<T> localList = list;
if ((uint)index < (uint)localList.size) {
current = selector(list, index);
index++;
return true;
}
return MoveNextRare()
}この場合、呼び出し側はこうなる。
using (List<int>.Enumerator enumerator = new List<int> { ... }.GetEnumerator()) {
Func<List<T>, int, T> selector = (list, index) => list.Items[index];
while (enumerator.MoveNext(selector)) {
....
}
}つまり、MoveNext()の中ではselector()が呼ばれていて、その返り値がイテレータの現在地に設定されている、というふうにも理解できる。
LINQにおけるイテレータとセレクタ
ここまできてようやくLINQの話ができる。
LINQというのはIEnumerable<T>に対して定義されている拡張メソッドの集合体で、C#では配列型もIEnumerable<T>を実装してる。なので、配列に対してLINQのメソッド群を使うことができる。
Select()もLINQに定義されているメソッドのひとつで、引数に指定された式を使って、IEnumerable<T>内の要素を射影する。
たとえば以下の場合、array の各要素に対して item => item、つまり int selector(int arg) { return arg; } という式を適用して返す。
var array = new int[] { 0, 1, 2, 3, 4 };
var arraySelected = array.Select(item => item);
foreach (var item in arraySelected) {
Console.WriteLine(item);
}これの中身をILSpyで覗いてみるとこうなる。実際にはもう少し複雑だけど、まぁだいたいこんなかんじ。
class functor {
internal int selector(int item) {
return item;
}
}
int[] array = new int[] { 0, 1, 2, 3, 4 };
IEnumerable<int> array2 = array;
Func<int, int> selector = new Func<int, int>(functor.selector);
using (IEnumerator<int> enumerator = array2.Select(selector).GetEnumerator()) {
while (enumerator.MoveNext()) {
Console.WriteLine(enumerator.Current);
}
}さて、肝心のMoveNext()はIEnumerator
知りたいのはMoveNext()の実装なのでVisualStudioのデバッガで確認してみると、、
どうやらイテレータの型はWhereSelectArrayIteratorというものらしい。Reference Sourceで中身を確認する。
public override bool MoveNext() {
switch (state) {
case 1:
enumerator = source.GetEnumerator();
state = 2;
goto case 2;
case 2:
while (enumerator.MoveNext()) {
TSource item = enumerator.Current;
if (predicate == null || predicate(item)) {
current = selector(item);
return true;
}
}
Dispose();
break;
}
return false;
}↑の11行目でselector()が呼ばれているがわかる。selector自体はWhereSelectArrayIteratorのコンストラクタで渡されているらしい。
つまり、Select()が呼び出された時点でWhereSelectArrayIteratorのコンストラクタが呼ばれ、そこでselectorがイテレータに設定される。そして、MoveNext()が呼びだされた時点で、selector()の呼び出しが行われる。Select()の実態はイテレータの生成であって、ループ内でMoveNext()が呼びだされた時点で、リスト内の要素にアクセスされる。
なんだか当たり前のことを言ってるような気がするけど、例えばLINQではarray.Select(item => item * 2)という式も書くことができる。つまり、selector()の中身をプログラマが自分で定義できる。この場合、イテレータからMoveNext()が呼びだされた時点で、item * 2という式が評価されることになる。
なので、LINQを使うとこういうことが起きる。
var array = new int[] { 0, 1, 2, 3, 4 };
var arraySelected = array.Select(item => {
Console.WriteLine("selector: " + item);
return item * 2;
});
Console.WriteLine("begin foreach");
foreach (var item in arraySelected) {
Console.WriteLine("foreach: " + item);
}
Console.WriteLine("end foreach");
/* 実行結果
begin foreach
selector: 0
foreach: 0
selector: 1
foreach: 2
selector: 2
foreach: 4
selector: 3
foreach: 6
selector: 4
foreach: 8
end foreach
*/
LINQ におけるクエリ呼び出しの実態
クエリ
LINQという言葉はLanguage INtegrated Queryの略で、ここでいう「クエリ」というのはSQL等のQueryと同じ意味を持つ。これは、リスト内の要素、つまり、IEnumerable<T>を実装したクラスが持つデータに対する「問い合わせ演算」のことを指す。
実際にSQLのようなクエリ式を書くことも可能で、これはコンパイラによってメソッド呼び出しに展開される。
例えばこのコードは、
var array = new int[] { 0, 1, 2, 3, 4 };
var arrayWhereSelected =
from item in array
where item % 2 == 0
select item * 2;
foreach (var item in arrayWhereSelected) {
Console.WriteLine(item);
}
/* 実行結果
0
4
8
*/コンパイラによってこのように展開される。
var array = new int[] { 0, 1, 2, 3, 4 };
var arrayWhereSelected = array
.Where(item => item % 2 == 0)
.Select(item => item * 2);
foreach (var item in arrayWhereSelected) {
Console.WriteLine(item);
}これをILSpyで展開すると、こんなかんじになる。
private sealed class functor {
internal bool predicate(int item) {
return item % 2 == 0;
}
internal int selector(int item) {
return item * 2;
}
}
IEnumerable<int> array = new int[] { 0, 1, 2, 3, 4 };
Func<int, bool> predicate = new Func<int, bool>(Program.functor.<>9.predicate);
Func<int, int> selector = new Func<int, int>(Program.functor.<>9.selector);
IEnumerable<int> arrayWhere = array.Where(predicate);
IEnumerable<int> arrayWhereSelected = arrayWhere.Select(selector);
using (IEnumerator<int> enumerator = arrayWhereSelected.GetEnumerator()) {
while (enumerator.MoveNext()) {
Console.WriteLine(enumerator.Current);
}
}predicate() で検索した結果を、selector() で射影していることがわかる。前述のWhereSelectIteratorというのは、最適化のためにこの2つの操作を結合したもので、Where()が存在しない場合はpredicateにnullが渡されている。実際、MoveNext()の実装を読み返すとif (predicate != null) predicate(item) という意味合いの式がある。
遅延評価
さて、ここまでくるとLINQを使ったときの挙動はだいたい把握できるんじゃなかろうか。
例えば、Linqメソッド群の中にはSkip()とTake()というメソッドがあり、呼び出すと、それぞれSkipIteratorとTakeIteratorに展開される。
この2つを使うと、例えば array.Skip(2).Take(3) という呼び出しで、arrayの先頭2要素を飛ばして3個の要素に、つまり3番目から5番目の要素に連続してアクセスできる。
SkipIterator はイテレータの現在地を進めるために MoveNext() を呼び出すので、飛ばしたぶんだけの predicate() と selector() が呼び出されることになる。検索と射影の結果を正確に反映するためだ。
また、First() はIEnumerable
「LINQ」という単語でぐぐってると、「LINQを使うと遅延評価が行われる」といったようなフレーズによく出くわすことになる。このフレーズが意味することは、LINQを使ったときはMoveNext()が呼ばれるまでpredicate()やselector()が呼び出されないということで、逆に言えば、MoveNext()を呼び出すたびにpredicate()やselector()が呼び出される、ということでもある。
なので、例えばこういうコードを書くと、
var array = new int[] { 0, 1, 2, 3, 4 };
var arraySelected = array.Select(item => {
Console.WriteLine("selector: " + item);
return item;
});
foreach (var item in arraySelected) {
Console.WriteLine(item);
}
foreach (var item in arraySelected) {
Console.WriteLine(item);
}こういうことが起こる。
selector: 0 0 selector: 1 1 selector: 2 2 selector: 3 3 selector: 4 4 selector: 0 0 selector: 1 1 selector: 2 2 selector: 3 3 selector: 4 4
ループの中でMoveNext()が呼ばれるたびにselector()が呼び出されている。つまり、イテレータを何度も使いまわすと、その回数分だけselector()が呼び出されて、なんていうかすごく無駄だ。
なので、そんな場合はこういうふうに書く。
var array = new int[] { 0, 1, 2, 3, 4 };
var arraySelected = array.Select(item => {
Console.WriteLine("selector: " + item);
return item;
});
var arraySelectedArray = arraySelected.ToArray();
foreach (var item in arraySelectedArray) {
Console.WriteLine(item);
}
foreach (var item in arraySelectedArray) {
Console.WriteLine(item);
}
/* 実行結果
selector: 0
selector: 1
selector: 2
selector: 3
selector: 4
0
1
2
3
4
0
1
2
3
4
*/ToArray()を使うと、IEnumerable
ここまでのまとめ
ふぅ。。
- IEnumerable<T> を実装したクラスが持つデータに対する「問い合わせ演算」を総称して、LINQ と呼ぶ。
- MoveNext() が呼び出されるたびに、各要素に対して「問い合わせ」を行われる。
