LINQの仕組みと遅延評価の基礎知識

2011-01-13

新年明けましておめでとうございます。その第一弾の記事は実践 F# 関数型プログラミング入門の書評にしようと思っていたのですが、もう少し時間がかかりそうなので、せっかくの年始は基礎から考えようということで、LINQと遅延評価について最初から解説します。まあ、何をもって最初だとか基礎だとか言うのも難しいので私的な適当な基準で。つまり役に立たな（ry。なお、ここではLinq to Objects、IEnumerable<T>の連鎖についてのみ扱いますので、IQueryableについてはまた後日というか実のところ私はQueryableは全然分かってなくてやるやる詐欺が今も続いているといううがががが。

メソッドチェーン != return this

例によって単純なコードで。

var query = Enumerable.Range(1, 10).Select(i => i * i).Take(5);
foreach (var item in query)
{
    Console.WriteLine(item); // 1, 4, 9, 16, 25
}

1から10を二乗したうちの先頭5つを出力という、それだけのコードです。foreachする場合のinの右側が長くなるのは個人的に好きじゃないので、わざわざ変数に置いたりするのをよくやるのですが、これは好みですかねえ。なのでリスト内包表記とかあんま好きじゃなかったりはする、記法的に。

それはともかく、ドットで繋げていると実体が隠れてしまいがちなので、分解します。

var rangeEnumerable = Enumerable.Range(1, 10);
var selectEnumerable = rangeEnumerable.Select(i => i * i);
var takeEnumerable = selectEnumerable.Take(5);
foreach (var item in takeEnumerable)
{
    Console.WriteLine(item);
}

変数だらけでゴチャゴチャして余計に分からない。良く分からないものは、とりま図で。

こうなってます。中に、一つ前のものを内包している新しいオブジェクトを返しています。メソッドチェーンというと所謂ビルダー的な、もしくはjQueryなんかを想像してしまってチェーン毎に内部の状態が変化して return this するか、もしくは完全に新しいものを生成して返す（array.filter.mapしたら.filterで完全に新しい配列が生成され返って、.mapでも、的な。DeepCopyも同じようなものですか）みたいなのを想像してしまう感もあるのですが、そのどちらでもない。中に仕舞い込んで新しい包を返す。実に副作用レスでピュアい。

このことはデバッガで確認出来ます。

面白いのはSelectの戻り値の型で、WhereSelectEnumerableIteratorとなっていて、名前のとおりWhereとSelectが統合されていたりします。これは、Where->Selectが頻出パターンのためパフォーマンス向上のためでしょうねえ。面白いですがユーザー的にはあまり気にすることではないので深追いしないで次へ。

Takeの戻り値であるTakeIteratorはsourceとして中にSelectの戻り値であるWhereSelectEnumerableIteratorを抱えていて、Selectの戻り値はRangeの戻り値であるRangeIteratorを、中に抱えています。という連鎖が成り立っていることがしっかり確認できました。Visual Studioのデバッガは大変見やすくてよろしい。

遅延評価と実行

hogeEnumerableに包まれている状態では、まだ何も実行は開始されていません。そう、遅延評価！このままWhereやSkipを繋いでも、新たなhogeEnumerableで包んで返されるだけで実行はされません。ではいつ実行されるかといえば、IEnumerable<T>以外の、何らかの結果を要求した時です。それはToArrayであったり、Maxであったり、foreachであったり。

foreachを実行した時の動きを、図（但し致命的に分かりづらい）で見ると……

まず最初は最外周のtakeEnumerableに対しGetEnumeratorを実行し、IEnumerator<T>を取り出します。そして取り出したIEnumerator<T>に対しMoveNextの実行をすると、その先ではまた中に抱えたIEnumerable<T>に対しGetEnumeratorでIEnumerator<T>を取り出し、の連鎖が大元(この場合はrangeEnumerable)に届くまで続きます。

大元まで届いたら、いよいよMoveNextの結果が返されます。trueか、falseか。trueの場合は、通常は即座に現在値(Current)の取得も行うので、Currentが根本から下まで降りていくイメージとなります。あとは、どこかのMoveNextがfalseを返してくるまで、その繰り返し。今回はRangeが10個出力、Takeが5個出力なので、Rangeが5回分余りますがTakeで列挙は途中打ち切り。falseを流して終了させます。SumやCountなど値を返すものは、falseが届いたら結果を返しますが今回はforeachなのでvoid、何もなしで終了。

イテレータの実装

ついでなので、動作の実態であるイテレータも実装します。単純な、0から10までを返すだけのものを例として。

public class ZeroToTenIterator : IEnumerator<int>
{
    private int current = -1;

    public int Current
    {
        get { return current; }
    }

    public bool MoveNext()
    {
        return ++current <= 10;
    }

    // 必要でなければ空でもいいや、という感じ
    public void Dispose() { }

    // TじゃないほうはTのほうを返すようにするだけでおk
    object System.Collections.IEnumerator.Current { get { return Current; } }

    // Resetは産廃なのでスルー、実装しなくていいです、Interfaceからも削られて欲しいぐらい
    public void Reset() { throw new NotImplementedException(); }
}

// 使うときはこんな感じでしょーか
// IEnumerator<T>利用時はusingも忘れないように……
using (var e = new ZeroToTenIterator())
{
    while (e.MoveNext())
    {
        Console.WriteLine(e.Current);
    }
}

IEnumerator<T>ですが、見てきたとおり、中核となるのはMoveNextとCurrentです、といってもCurrentはキャッシュした値を中継するだけなので、実質実装しなければならないのはMoveNextだけ(場合によりDisposeも)。

見たとおりに一行の超単純な、10超えるまでインクリメントでtrue、超えたらfalse。なんかとってもいい加減な感じで、falseだろうとMoveNext()を呼んだらCurrentの値がどんどん増加していっちゃって大丈夫か？というと、全然問題ない。と、いうのも、そういうのは利用側の問題であって実装側が気にする必要はないから。

MoveNextする前のCurrentの値は保証されていないので使うな、であり、MoveNextがfalseを返した後のCurrentの値は保証されてないので使うな、です。大事なお約束です。お約束を守れない人は生イテレータを使うべからず。Linqのクエリ演算子やforeachは、そんな他所事を考えないで済むようになっているので、それらを使いましょう。生イテレータを取得したら負けです(拡張メソッド定義時は除く、つまりライブラリ的な局面以外では避けましょう)

ちなみにStringのイテレータは列挙前/列挙後のCurrentへのアクセスで例外が飛び、List<T>は列挙前は0、列挙後も0にリセットされ、Enumerable.Rangeでは列挙後は最後の値が返る、といったように、実際に挙動はバラバラです。

実装側が守らなければならないルールは、MoveNextが一度falseを返したら、以後はずっとfalseを返し続けること。で、その観点で、このZeroToTenIteratorを見ると、実のところ全然ダメです。MoveNextがint.MaxValue回呼び出されるとcurrentがオーバーフローしてint.MinValueになって、つまりはMoveNextの結果もfalseからtrueに変わってしまいます。腐ってますね。殺害されるべき。誰がそんなに呼ぶんだよ、という感じに普段はあんま気にしないゆとりな私ですが、いえいえ、こういう時ぐらいは気にしたりします。

オーバーフローはうっかりで見落としがちなので、ヘラヘラゆとりゆとりと笑ってないで、普段から注意すべきだと自戒するこの頃。

まあ、今時はイテレータの手実装なんてする必要ないのですがね！シンプルなものならばLinqの組み合わせで実現出来ますし、そうでないものはyield returnを使えばいいので。手実装じゃなきゃダメなシチュエーションってなにかある、かなあ？

まとめ

「return thisじゃなくて新しいオブジェクトを返してる」「配列的なイメージで扱えるけれど実体はストリームのほうが近い」「デバッガ素晴らしすぎる」「生禁止」の以上四点でした。

Linq to ObjectsのJavaScript移植であるlinq.jsも同じ仕組みでやっているので、そちらのコードのほうがブラックボックスでなく、また、素直に書いているので分かりやすくお薦め、かどうかは、微妙なところですんがー。ブラックボックスになっている部分(yield returnなど)を表に出しているので(というか出さないと実装出来ない)余計分かりにくい感も。

で、基礎からのLinqといえば紹介したいシリーズが一つ。

LondonのGooglerでMicrosoft MVPでC# in Depthの著者でStack Overflowで凄まじい解答量を誇るJon Skeet氏が、BlogでReimplementing LINQ to Objectsと称して、これまた凄まじい勢いで再実装&超詳細な解説をやっているので必見です。

詳細、どころの話じゃなく詳細で大変ヤバ素晴らしすぎる。単純なサンプルコードと結果を貼ってメソッド紹介、などという記事とは一線を画しすぎるクオリティ。私もこういう記事を書いていきたいものです。こんな量とスピードの両立は超人すぎて無理ですが、今年は記事のクオリティは上げたいですね。

C# in Depth 2nd Editionはつい二ヶ月前に出たばかりで、内容も良さそうですね、読んでみたい本です。しかし私の手元には積み本がいっぱいで、とほほ。で、本といえばもう一つ、C# 4.0 Unleashedがもうすぐ(2011/1/14、明日だね)出ます。これは著者がBart De Smet氏なので大注目です。B# .NET BlogでキレキレのLinqコード、だけじゃなくILからSQLからあらゆる領域にエキスパートな凄さを見せているので超楽しみです。こちらは予約してあるので、届くのが本当に楽しみで（洋書なので届くのは月末予定のよう、F#本が読み終えた頃になる予定なのでちょうどいいー）。

Bart氏は大学時代はベルギーのMicrosoft MVP for Visual C#、その後MicrosoftのWPFチームに入り、現在はCloud Programmability Team、つまりRxを開発しているチームに入ってます。氏が入ってからIQbservableとかヘンテコなのが次々と上がってきて、ますます目が離せない状態に。PDC10ではLINQ, Take Two - Realizing the LINQ to Everything Dreamというセッションを行ってましたが、これは本当に必見。Linqの過去、そして未来を見る素晴らしいセッションでした。感動しすぎて3回ぐらい見直した。

LINQは今後「ますます」重要になるので、しっかり土台を固めて、未来へ向かおう！

LINQの仕組みと遅延評価の基礎知識

メソッドチェーン != return this

遅延評価と実行

イテレータの実装

まとめ

Profile

Archive