graphics.hatenablog.com

テクニカルアーティストの技術を書き殴るためのメモ帳

C#における「列挙」の意味と、LINQについて。

こないだ会社の先輩と話しててあれこれ考えたので、自分がLINQを理解した過程を言語化してみる。

対象は、とりあえずC++あたりの適当な言語で数年程度の経験がある人。プログラミングの地力さえあれば、C#についてはなんとなく読み書きできる程度で構わない。LINQに対する解説は世の中に溢れてるので、ここでは特にその内部実装にフォーカスしてみる。「わかってるひと」向けには、「おまじない」とか一切ナシのガチ解説が最短距離だと信じてる。

必要なC#の前提知識についてはこちら

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 は単なるシンタックスシュガーであり、実際には、リストの型(ArrayやList<T>)に応じて for や while に展開される。
  • foreach が while に展開された場合、イテレータ内に定義された MoveNext() によって、実際の要素がリストから抽出される。

展開後の 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のメンバメソッドとなっているが、IEnumeratorはインターフェイス定義なので実際のメソッドはarray2.Select(selector).GetEnumerator()の返り値の型が持っていることになる。

知りたいのはMoveNext()の実装なのでVisualStudioのデバッガで確認してみると、、
f:id:hal1932:20160312110519j:plain

どうやらイテレータの型は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 の各種メソッドを呼び出すと、MoveNext() 等をメンバに持つイテレータが生成される。
  • イテレータが MoveNext() を呼び出すことで、selector() 呼び出しによってリスト内の各要素(を射影した結果)にアクセスすることができる。

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()というメソッドがあり、呼び出すと、それぞれSkipIteratorTakeIteratorに展開される。

この2つを使うと、例えば array.Skip(2).Take(3) という呼び出しで、arrayの先頭2要素を飛ばして3個の要素に、つまり3番目から5番目の要素に連続してアクセスできる。

SkipIterator はイテレータの現在地を進めるために MoveNext() を呼び出すので、飛ばしたぶんだけの predicate() と selector() が呼び出されることになる。検索と射影の結果を正確に反映するためだ。

また、First() はIEnumerableが持つ最初の要素を返す、より正確には、MoveNext() が最初に true を返す要素を返す。つまり、true を返すまで predicate() を呼び出し続けることになる。

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の全要素の評価結果が静的な配列にコピーされるToList()ToDictionary()の場合も同じく、全要素の評価結果がListなりDictionaryなりにコピーされる。Array, List, Dictionaryなどのコレクション型の中身を走査するときはイテレータを使う必要がないので、アクセスするたびにいちいちpredicate()やselector()が呼び出されることもない。

ここまでのまとめ

ふぅ。。

  • IEnumerable<T> を実装したクラスが持つデータに対する「問い合わせ演算」を総称して、LINQ と呼ぶ。
  • MoveNext() が呼び出されるたびに、各要素に対して「問い合わせ」を行われる。

全体のまとめ

  • C# における「列挙」とは、MoveNext() を呼び出しながら IEnumerable<T> が持つ要素にアクセスすることを指す。
  • LINQ とは、IEnumerable<T> が持つ要素に対する問い合わせ演算の集合体である。
  • LINQ は拡張メソッドラムダ式を駆使した黒魔術のように見えるかもしれないが、あくまで .NET を構成するソフトウェアライブラリの一部であり、Reference Sourceからすべての内部実装を確認することができる。迷ったらReference Sourceにアクセスする、それで駄目ならILSpyを使えばだいたい全部わかる。

つかれた。