【C#】How LINQ works – foreachとLINQの仕組み

最初の記事はLINQについて。C#においてLINQは必要不可欠と言っても良いほど便利な機能ですが、その仕組みをよく知らずに使っている方も多いんじゃないかなーと思ってます。

というわけで仲間内でLT的なものをやったんですが、わかりやすいという感想もいただけて結構評判が良さげだったので記事としてまとめておきます。一応その時の資料もドクセルに上げてあるので、合わせて見ていただけると幸いです。(急ぎで作った資料なので割とミスりまくってますが、その辺はまあ気のせいということで)

この記事を読めば、きっとLINQについてある程度は理解できる…はず…！

LINQ、使ってますか？

まずそもそもLINQって何かというと、こんな感じのやつです。

var collection = Enumerable.Range(1, 40);
var query = collection.Where(x => x % 3 == 0).Take(5);

foreach (var i in query)
{
    Console.WriteLine(i);
}

このコードの内容を簡単に説明すると

1. Enumerable.Range(1, 40)で1〜40のシーケンスを取得
2. Whereでxが3の倍数であるものを抽出
3. Takeで最初の5つの要素のみを抽出
4. foreachで各要素を取り出してコンソールに表示

といった感じですね。

見た目は非常にシンプルなのですが、実際にLINQの仕組みを理解しようとするとなかなか大変です。まず、非常にシンプルであるが故に、パッと見て実際の実装がどうなっているのかよくわからん。インターフェースにしても、IEnumerableとかIEnumeratorとか似たような名前が多くて意味わからん。それはそう。

とまあ、使うのは簡単でも仕組みは難しそうなLINQですが、広く使われている技術である上、実装を知れば様々なことに応用できます。今回はコレクションとLINQの基礎から応用までを4段階に分けて解説していきたいと思います。

Lv1 foreachとIEnumerable

LINQの仕組みについて考える前に、まずはforeach構文について見ていきましょう。

var collection = Enumerable.Range(1, 10);

foreach (var element in collection)
{
    Console.WriteLine(element);
}

皆さんご存知、foreach。コレクションの各要素にアクセスするために使う構文です。
そして、このコードはコンパイル時に以下のような形に変わります。

var collection = Enumerable.Range(1, 10);

IEnumerator e = collection.GetEnumerator();
while (e.MoveNext())
{
    int element = (int)e.Current;
    Console.WriteLine(element);
}

実際にはコンパイラによる最適化やDisposeの処理などが入りますが、その部分は一旦省略。重要なのはIEnumeratorの処理です。

1. GetEnumeratorでIEnumeratorを取得
2. MoveNextでシーケンスの終了まで１つずつ進める
3. Currentで現在の値を取得

といった流れになっているのがわかると思います。ここで重要なのは、IEnumeratorとIEnumerableです。

IEnumerator

public interface IEnumerator
{
    bool MoveNext();
    object Current { get; }
    void Reset();
}

public interface IEnumerator<T> : IEnumerator, IDisposable
{
    T Current { get; }
}

IEnumeratorの中身はこんな感じです。

IEnumeratorは列挙処理のためのインターフェースです。使い方は先ほどforeachのコードで見た通り、
MoveNextで次の要素に進み、Currentで値を取得、MoveNextがfalseを返したら最後の要素に到達したとみなして処理を終了します。

「あれ？Resetは？」というと、Resetは初期状態に戻すためのメソッドなんですが、互換性のために維持されているだけなので基本的には使用しません。自分でこのインターフェースを実装する際にはNotSupportedExceptionをスローすればOKです。また、IEnumerator<T>がIDisposableを継承している点については後ほど。

IEnumerable

public interface IEnumerable
{
    IEnumerator GetEnumerator();
}

public interface IEnumerable<T> : IEnumerable
{
    IEnumerator<T> GetEnumerator();
}

今度はIEnumerableの中身を見てみます。

IEnumerableは、列挙(foreach)可能であることを示すインターフェースです。すなわち、このインターフェースを実装すればforeach内で使用することが可能になります。

中身としては、列挙処理用の列挙子(要するにIEnumerator)を取得するためのメソッド、GetEnumeratorを持ちます。先ほども見たように、foreachを呼ぶ際にはGetEnumeratorが呼ばれ、取得したIEnumeratorをwhile文でMoveNextする、といった動作ですね。

配列やListなどのコレクションは全てIEnumerableを実装しています。データ構造に関係なくforeachで回すことができるのはそのためです。

[余談] foreachとIDisposable

先ほどforeachは以下のような形で展開されると説明しました。

var collection = Enumerable.Range(1, 10);

IEnumerator e = collection.GetEnumerator();
while (e.MoveNext())
{
    int element = (int)enumerator.Current;
    Console.WriteLine(element);
}

このコードでは説明の都合上一部の処理を省略されています。では、実際にはどのような形で展開されるのかというと、以下のようなコードになります。

var collection = Enumerable.Range(1, 10);

IEnumerator e = collection.GetEnumerator();
try
{
    while (e.MoveNext())
    {
        int element = (int)e.Current;
        Console.WriteLine(element);
    }
}
finally
{
    IDisposable d = e as IDisposable;
    if (d != null) d.Dispose();

    // コンパイル時にeがIDisposableであるとわかっている場合はこのようになる
    // ((IDisposable)e).Dispose();
}

try-finallyが追加されています。つまり、eがIDisposableである場合には、foreachの終了時に必ずDisposeが呼ばれます。列挙子がファイルの読み込み等の用途で何らかのリソースを保持している場合には、Disposeを記述しておけばforeachを抜けた際に勝手に解放してくれます。便利。

ただ一つ注意としては、foreachを使って回す場合にはそれで良いのですが、IEnumerator<T>をそのまま扱う場合にはDisposeは呼ばれません。その場合には必ずusingで囲ってDisposeが呼ばれるようにしておきましょう。

Lv1 まとめ

・foreachはwhile (enumerator.MoveNext()) … のような形に展開される
・列挙子であるIEnumerator、列挙(foreach)可能であることを示すIEnumerable
・全てのコレクションはIEnumerableを実装する

Lv2 イテレータ構文

続いては、IEnumerableを生成するための機能である「イテレータ」について説明します。

IEnumeratorとIEnumerableは列挙処理を行う上で非常に便利なインターフェースですが、実際に実装するとなると相当な労力を要します。そのため、C#にはIEnumerator・IEnumerableを簡単に実装するための「イテレータ」という構文が用意されています。

public IEnumerable<int> OneToFive()
{
    yield return 1;
    yield return 2;
    yield return 3;
    yield return 4;
    yield return 5;
}

こんな感じで、メソッド内にyield returnを書いて値を返していきます。あとはこれをforeachに突っ込めば…

foreach (var i in OneToFive())
{
    Console.WriteLine(i);
}

コンソールに1、2、3、4、5と表示されます。

このようにyield returnを含むブロックを「イテレータブロック」と呼び、通常のメソッドのような記述で簡単にIEnumerableを生成することができます。

通常はIEnumerableを実装したクラスを作らなければなりませんが、イテレータではコンパイラがIEnumerableを実装したクラスを自動で生成してくれるので、メソッドを呼ぶ感覚でIEnumerableを利用できます。

当然forやwhileなども使えるので…

static IEnumerable<int> FromTo(int from, int to)
{
    while (from <= to)
    {
        yield return from++;
    }
}

static void Main()
{
    foreach (var i in FromTo(1, 10))
    {
        Console.WriteLine(i);
    }
}

こんな感じで書くことも可能です。

IEnumerator or IEnumerable?

イテレータの戻り値は必ずIEnumerator、IEnumerator<T>、IEnumerable、IEnumerable<T>のいずれかである必要があります。IEnumeratorとIEnumerableのどちらでもイテレータとしては動作するので混乱しますが、Lv1で説明した通り両者は役割の異なるインターフェースであり、用途によってどちらを戻り値にするかを使い分けます。

基本的にforeachやLINQなどで使いたい場合にはIEnumerableを利用します。

[余談] イテレータとコルーチン

ここまでイテレータについて書いてきたわけですが、Unity使いであれば、yield文が全く異なる用途で使われているのを見たことがあるかもしれません。そう、「コルーチン」です。

イテレータメソッドは通常のメソッドと異なり、MoveNextを呼ぶたびに最後に到達したyield returnの続きから実行されます。例えば、

IEnumerator Test()
{
    Console.WriteLine("One");
    yield return null;
    Console.WriteLine("Two");
    yield return null;
    Console.WriteLine("Three");
}

というイテレータがあったとして、これに対してMoveNextを呼ぶと、

var e = Test();
e.MoveNext(); // Oneが表示される
e.MoveNext(); // Twoが表示される
e.MoveNext(); // Threeが表示される

このように、メソッドの途中から実行されています。Unityのコルーチンは、イテレータのこの性質を利用して実装されています。

IEnumerator CoroutineExample()
{
    Debug.Log("Start");
    yield return new WaitForSeconds(1f);
    Debug.Log("Complete");
}

これをStartCoroutineに渡して実行すると、Updateの度にMoveNextを呼ばれるようになります。これがUnityにおけるコルーチンの仕組みです。

当時Unityで使われていたC#のバージョンではasync/awaitが利用できなかったため、イテレータを使って非同期処理っぽいものを実現しています。

Lv2 まとめ

・イテレータ構文を使えばIEnumerableを簡単に生成可能
・yield returnで値を返し、yield breakで処理を終了
・コルーチンはイテレータの性質を利用して動いている

Lv3 LINQの仕組み

タイトルが「How LINQ works」なのにも関わらずここまでLINQのLの字も出てきませんでしたが、Lv3ではようやくLINQについてを扱います。

Lv1では、IEnumeratorはMoveNextによって要素を進め、Currentによって値を取り出すと説明しました。foreachがこの二つを使ってコレクションの全ての要素にアクセスしていることも確認したかと思います。

では、MoveNextの処理やCurrentの値を別のものに変えてみたら…？と言っても分かりづらいので、具体的に例を挙げながら見ていきましょう。

Where

1から順番に数が並び、MoveNextで次の要素へ進んでいます。では、MoveNextの際に、値が偶数なら飛ばして次の要素に進むようにしたらどうなるでしょうか。

値の順が1、3、5に変わりました。偶数が飛ばされるので、ちゃんと奇数だけが取り出されてます。

要するにこれが、LINQにおけるWhereの考え方になります。実際にこれをLINQで書くとこんな感じ。

var collection = Enumerable.Range(1, 6);
var query = collection.Where(x => x % 2 == 1);

では、実際にWhereの実装を見てみましょう。

public static IEnumerable<TSource> Where<TSource>(
    this IEnumerable<TSource> source,
    Func<TSource, bool> predicate)
{
    foreach (var item in source)
    {
        if (predicate(item))
        {
            yield return item;
        }
    }
}

実際には例外処理やら引数の検証やらが入りますが、処理部分自体はこんな感じ。先ほどLv2で登場した「イテレータ」が出てきてますね。

predicateで渡された条件をもとに要素を検証し、trueならyield returnすることによって、値がフィルター処理された新たなIEnumerable<T>を生成しています。

Select

ついでにSelectについても考えてみます。まずはWhereの時と同じように、普通のコレクションを用意します。

今度は、foreachの際に取り出すCurrentの値を変えてみたらどうなるでしょうか。例えば、取り出したCurrentの値を文字列に変換してみます。

値がintのコレクションからstringのコレクションに変わりました。これがSelectの動作です。

これを実際にLINQで書いてみるとこんな感じ。

var collection = Enumerable.Range(1, 6);
var query = collection.Select(x => x.ToString());

では、Selectの実装も見ていきましょう。

public static IEnumerable<TResult> Select<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, TResult> selector)
{
    foreach (var item in source)
    {
        yield return selector(item);
    }
}

foreachというのはMoveNext毎にCurrentの値を取り出す操作ですから、このコードでは取り出したCurrentの値をselectorで変換してyield returnすることで新たなIEnumerable<T>を生成していることがわかると思います。

このように、LINQのメソッドではイテレータを利用することで元のIEnumerable<T>から新たなIEnumerable<T>を生成しています。これがLINQの基本的な仕組みになります。

IEnumerable<T>を連鎖させる

基本的にLINQの操作は、イテレータによって受け取ったIEnumerable<T>から新たなIEnumerable<T>を生成するものです。つまり、これらの操作は全て合成できます。

var collection = Enumerable.Range(1, 100);
var query = collection.Where(x >= 50) 
                      .Where(x <= 70)
                      .Select(x => x * x)
                      .Select(x => x.ToString)
                      .Take(5);

どんな複雑な操作であっても、このようにメソッドチェーンで繋ぐだけで簡単に記述できます。このようなコードは非常に見やすい上、IntelliSenseと併用した際の書き心地も最高です。これがLINQを使って書くことの最大の利点と言っても過言ではないでしょう。

Lv3 まとめ

・MoveNextやCurrentの処理を変えることでLINQを実現する
・LINQのメソッドはイテレータによって実装されている
・LINQはIEnumerable<T>の連鎖

Lv4 遅延評価と即時評価

最後のレベルでは、LINQにおける遅延評価と即時評価の違いについてを説明します。

Lv3で説明した通り、LINQのWhereやSelectではイテレータによってIEnumerable<T>を生成しています。が、イテレータの性質上、実際の処理はMoveNextが呼ばれるまで実行されません。(この辺りはコルーチンのあたりでも説明した通りです)

var collection = Enumerable.Range(1, 40);
var query = collection.Where(x => x % 3 == 0)
                 .Select(x => x.ToString())
                 .Take(5);

例えばこのようにLINQで処理を記述したとしても、ここでは何の処理も行われていません。内部的には受け取ったIEnumerable<T>を内包した新しいオブジェクトが返ってきているだけで、実際に結果を処理しているわけではないからです。

「じゃあいつ処理されるの？」というと、簡単です。MoveNextを呼ぶ瞬間、すなわちforeachした時に実行されます。

foreach (var element in query)
{
    Console.WriteLine(element);
}

こんな感じでforeachで回してあげると、MoveNextが呼ばれるたびに実際の処理が実行されていきます。このように、必要になるまで実行しない(必要な分だけ実行する)ことを「遅延評価」と呼びます。

遅延評価の問題と即時評価

必要になるまで実行しない遅延評価は、毎回結果を生成しないためメモリ効率は良いですが問題もあります。

まず、foreachの度に処理が行われるため、foreachした回数だけ処理が実行されます。LINQに値のキャッシュ機能はないので、同じ結果であっても何度も処理が走ってしまうことになります。もし操作の中に重い処理が含まれているとしたら、結果を読み取るたびに負荷がかかってしまいます。

また、実際に結果を保持しているわけではないため、同じ結果を取り出そうとした時に意図しない動作を起こすことも考えられます。要するに、同じ結果を読み取りたい場合には、遅延評価は向いていません。

そこで、ToArrayやToListを呼ぶことで即座に処理を実行して結果を受け取ることが可能です。これを遅延評価に対して「即時評価」と呼びます。

var collection = Enumerable.Range(1, 40);
var query = collection.Where(x => x % 3 == 0)
                      .Select(x => x.ToString())
                      .Take(5);

// 即座に処理が実行されて結果が返ってくる
var array = query.ToArray();

必要になるまで実行しないという遅延評価の利点は失われますが、何度も同じ結果を読み取りたい時には即時評価を使った方が効率的です。

LINQにおける遅延評価 / 即時評価

では、実際にどの操作が遅延評価でどの操作が即時評価なのか、という話になるわけですが、その判別は非常にシンプルで

・Where, Select, Take, OrderBy…など、「IEnumerable<T>」を返すものは遅延評価
・ToArray, ToList, Sum, First..など、「それ以外の結果」を返すものは即時評価

となっています。

この辺りの詳しい分類について知りたい場合には、実行方法による標準クエリ演算子の分類 (C#)が参考になります。

Lv4 まとめ

・LINQのメソッドには遅延評価と即時評価がある
・IEnumerable<T>を返すものが遅延評価、それ以外の結果を返すものが即時評価
・同じ結果を繰り返し取得したい場合には即時評価を使う

終わりに

いかがだったでしょうか。LINQは一見シンプルですが、内部の実装はなかなか奥深いものになっています。だからこそ、LINQの仕組みを理解した上で使いこなしていきましょう。