アルゴリズムを記述する拡張メソッドは色々書いてみただろうか？
拡張メソッドを書きたくなる場合を考えると、結局のところは、いかにループロジックを書かなくて済むように出来るか？と言う所から始まるように思う。
他の例として：
- 連続する隣り合う要素をペアにして列挙
→ [A, B, C, D, E] を [{A, B}, {B, C}, {C, D}, {D, E}] で列挙できるようにする。
ループロジックで書くと、最後の要素を覚えておいて、次回に利用できるようにするとか、ループ回数を-1するだとか、簡単な事なのに泥臭いコードを書く必要がある。 - STLのsort/uniqueでDistinctのような事をするのと同様の操作
→LINQにはもちろんDistinct拡張メソッドが存在する。しかし、stableであろうとするからだろうか、異様に遅い。そこで、OrderByでソートしておいて（もちろん、PLINQで）、Unique拡張メソッドを用意し、連続する同じ要素を無視したシーケンスを返すことで、高速に一意化する事が出来る。この、連続する要素を無視するというアルゴリズムが、ループロジック的にやはり汚くなる。だから、拡張メソッド内に押し込めて、そういう事を考えなくても済むようにするわけだ。
ここまでで見てきたように、LINQには「クエリ構文」と「メソッド構文」があり、クエリ構文で記述出来ることは全てメソッド構文で記述可能で、結局のところ、LINQを支えているのは大量の拡張メソッド群となっている。
int[] datas = new int[] { 1, 2, 5, 3, 9, 7, 4 };
// クエリ構文 #1
IEnumerable<string> resultByQuery1 =
from data in datas
select data.ToString();
// メソッド構文 #1
IEnumerable<string> resultByMethod1 =
datas.
Select(delegate(int data) { return data.ToString(); });
// クエリ構文 #2
IEnumerable<string> resultByQuery2 =
from data in datas
orderby data descending
select data.ToString();
// メソッド構文 #2
IEnumerable<string> resultByMethod2 =
datas.
OrderByDescending(delegate(int data) { return data; }).
Select(delegate(int data) { return data.ToString(); });
// クエリ構文 #3
string[] resultByQuery3 =
(from data in datas
orderby data descending
select data.ToString()).
ToArray();
// メソッド構文 #3
string[] resultByMethod3 =
datas.
OrderByDescending(delegate(int data) { return data; }).
Select(delegate(int data) { return data.ToString(); }).
ToArray();
LINQ入門のような記事は、大方クエリ構文で紹介される。つまるところ、SQL構文がネイティブにC#でサポートされたかのように使えますよ、と。しかし、LINQのクエリ構文は、いわゆる「構文糖」なので、上記の例で見せたように、コンパイラはメソッド構文に置き換えた状態でコンパイルを行う。このメソッド構文こそが、LINQの真の姿ということだ。
最後の例では、ToArray拡張メソッドの違和感がよく表れている。メソッド構文では綺麗につながって記述されているが、クエリ構文ではfrom句からselect句まで括弧でくくり、その結果をToArrayしなければならない。括弧を使わないと、select句の一部と見なされ、違ったコードとなってしまう。
そして、メソッド構文で考えると、LINQのパイプライン実行がどのようなものかも見えてくる。
// 一行で記述
string[] resultByOne =
datas.
OrderByDescending(delegate(int data) { return data; }).
Select(delegate(int data) { return data.ToString(); }).
ToArray();
// 分割して記述
IEnumerable<int> resultStep1 =
datas.
OrderByDescending(delegate(int data) { return data; });
IEnumerable<string> resultStep2 =
resultStep1.
Select(delegate(int data) { return data.ToString(); });
string[] resultStep3 =
resultStep2.
ToArray();
一行で全て記述した場合と、分割して記述した場合で、（バイナリは多少変わるが）コードの効率は全く変わらない（理由は後述）。その上で、分割したそれぞれの式の結果型を見ると、IEnumerable<T>となっていることが分かる。LINQの拡張メソッドの戻り値は、殆どが列挙子で返されるようになっている。ちなみに、ToArrayで返される配列も、IEnumerable<T>を実装しているため、配列に対して更にLINQの拡張メソッドを使用する事が出来る（元々、datasは配列だ）。
この、「列挙子」がパイプライン実行を担っていて、クエリの遅延実行を可能にする。遅延実行とは何だろうか？
唐突だが、ToArrayの中身について考えてみる。ToArrayは列挙子の「遅延実行」が行われず、その場で評価される。
// ToArrayの疑似コード
public static T[] ToArray<T>(this IEnumerable<T> enumerable)
{
List<T> results = new List<T>();
foreach (T value in enumerable)
{
results.Add(value);
}
return results.ToArray();
}
引数で与えられた列挙子は、要素数が分からないため、List<T>を使って要素値を移し替えた（コピー）あと、配列に変換している（Listの使い方としては例が悪いが、趣旨とはずれるので勘弁）。
foreachは、実際には以下のように変換出来る。
public static T[] ToArray<T>(this IEnumerable<T> enumerable)
{
List<T> results = new List<T>();
// foreach (T value in enumerable)
IEnumerator<T> enumerator = enumerable.GetEnumerator();
while (enumerator.MoveNext() == true)
{
T value = enumerator.Current;
results.Add(value);
}
return results.ToArray();
}
例外に対処するコードは省いた。
IEnumerable<T>から、GetEnumeratorメソッドで列挙子本体（IEnumerator<T>）を取得し、これで列挙を実行するループを形成している。resultStep2.ToArray()とした場合、resultStep2.GetEnumerator()を呼び出している事になる。resultStep2はSelectが返しているのだが、Select内部の実装はどうなっているだろうか？
// Selectの疑似コード
public static IEnumerable<U> Select<T, U>(this IEnumerable<T> enumerable, Func<T, U> predict)
{
// foreach (T value in enumerable)
IEnumerator<T> enumerator = enumerable.GetEnumerator();
while (enumerator.MoveNext() == true)
{
T value = enumerator.Current;
U result = predict(value);
yield return result;
}
}
ををを、こりゃいかん。yield returnを説明で使ってしまった。これは以下のように展開される（うぅ、面倒だ）。
public static IEnumerable<U> Select<T, U>(this IEnumerable<T> enumerable, Func<T, U> predict)
{
// ※1
return new SelectEnumerable<T, U>(enumerable, predict);
}
private sealed class SelectEnumerable<T, U> : IEnumerable<U>
{
private readonly IEnumerable<T> enumerable_;
private readonly Func<T, U> predict_;
public SelectEnumerable(IEnumerable<T> enumerable, Func<T, U> predict)
{
enumerble_ = enumerable;
predict_ = predict;
}
public IEnumerator<U> GetEnumerator()
{
// ※2
return new SelectEnumerator<T, U>(enumerator_.GetEnumerator(), predict_);
}
}
private sealed class SelectEnumerator<T, U> : IEnumerator<U>
{
private readonly IEnumerator<T> enumerator_;
private readonly Func<T, U> predict_;
public SelectEnumerator(IEnumerator<T> enumerator, Func<T, U> predict)
{
enumerator_ = enumerator;
predict_ = predict;
}
public U Current
{
get
{
return predict_(enumerator_.Current);
}
}
public bool MoveNext()
{
return enumerator_.MoveNext();
}
}
説明に不要なコードは省略している。Selectを呼び出すと、結果としてSelectEnumerableのインスタンスが返される（※1）。この時点ではまだ元の列挙子（Selectの引数。resultStep1）は操作していない。
resultStep2にはSelectEnumerableのインスタンスが入っているので、resultStep2.GetEnumerator()を呼び出すということは、SelectEnumerableのGetEnumerator()を呼び出すことだ（※2）。ここで初めてresultStep1のGetEnumeratorが呼び出され、SelectEnumeratorのインスタンスが生成されて返される。
既に忘れているかもしれないが :-) ToArrayの中身のforeach（そしてそれを展開したwhile文）は、IEnumerator<T>を取得した後、MoveNextを呼び出している。上記のMoveNextを見ると、resultStep1のMoveNextに転送しているだけだ。その後、Currentプロパティを参照する。Currentプロパティの中身は、predictデリゲートを使ってresultStep1のCurrentプロパティの値を変換して返している。変換の内容は？LINQクエリを書いた本人が定義するわけだ。
そして、その結果をList<T>に追加し、whileの先頭に戻り、またMoveNextを呼び出す。後は、上記の動作が繰り返されるわけだ。
ここでは複雑すぎるので示していないが、resultStep1へのMoveNext呼び出しも、Currentプロパティの参照も、同じような流れに従っている。
全体を通して、以下のような構造となる。
これを俯瞰して見ると、ToArrayのforeachによるループ1回で、LINQクエリのパイプラインで接続されたメソッド群を「行ったり来たり」していることが分かると思う。この動作が「パイプライン実行」の正体だ。そして、GetEnumeratorが呼び出されるまでは、接続されたクエリが全く動作していないこともわかる。これが「遅延実行」と呼ばれる動作だ。
一行で書いても分割して書いても効率は変わらないと書いた理由が分かるだろうか？遅延実行をサポートするLINQの拡張メソッドは、結局SelectEnumerableのような「クエリ条件だけ保持して何もしない」クラスのインスタンスを返しているだけだからだ。それを一時変数に入れたところで、動作は全く変わらない。
