LINQは本当に強力だ (7) 範囲変数と構文の選択

LINQのクエリ構文には、範囲変数と呼ばれている機能がある。
たとえば、文字列で与えられた半径と円周を対にしてみる。

string[] values = new string[] { "234.56", "456.78", "345.67", "123.45" };
IEnumerable<Tuple<double, double>> results =
    from value in values
    select Tuple.Create(double.Parse(value), double.Parse(value) * 2 * Math.PI);

これで正しい結果が得られるのだが、文字列の数値をdoubleにパースする操作は2回行われる。
CLRがとても賢くなったとしたら、double.Parseに副作用が存在しないことをJITで確認して、1回の呼び出しに変換するかもしれないが、あまり期待できない。
そこで、普通ならパースした結果をローカル変数に入れておき、使いまわしたりするのだが、このような目的のために、LINQには「範囲変数」が存在する。

string[] values = new string[] { "234.56", "456.78", "345.67", "123.45" };
IEnumerable<Tuple<double, double>> results =
    from value in values
    let parsed = double.Parse(value)    // 範囲変数parsedに代入
    select Tuple.Create(parsed, parsed * 2 * Math.PI);

これなら確実に1回だけパースを行う。その結果を、範囲変数”parsed”に代入し、後で何度でも使いまわす事が出来る。
そういう訳で、このletは実に使い出がある。というより、これが無いとかなり困ったことになる。
ここで、新たな「let」という予約語(厳密には予約語ではないが、ここでは詳しく述べない)が登場するのだが、最初に見たときは「何でvarにしなかったんだ?」と思った。

もはやvarについて知らない人はいないと思うが、

// 右辺から、文字列の配列って分かるよね?
var values = new string[] { "234.56", "456.78", "345.67", "123.45" };
// 右辺から、Tuple<double, double>の列挙子って分かるよね?
var results =
    from value in values
    let parsed = double.Parse(value)
    select Tuple.Create(parsed, parsed * 2 * Math.PI);

というように書き直せる。右辺の結果の型が明確であれば、左辺にわざわざ型名を書かなくても良いでしょうというのが一点。もう一点は連載でもちらりと述べたが、匿名クラスをローカル変数に保持するのに、型名が書けないからという理由だ。

さて、やっとvarについて書けた。以後は注目すべき点がない場合はvarで書く :-)
varの意味づけがイメージ出来るように、実際に匿名クラスを使ってみようか。

var values = new string[] { "234.56", "456.78", "345.67", "123.45" };
// 型名が無いから、書きようがない
var results =
    from value in values
    let parsed = double.Parse(value)
    select new  // 匿名クラスだから、型名はない
    {
        R = parsed,
        Length = parsed * 2 * Math.PI
    };

上記の「results」は、varでしか宣言出来ない。故にvarという予約語が必要になった訳だ。
で、範囲変数であるletも事情は同じだ。場合によっては、型名が書けない事がある。それならば、letという予約語を作るよりもvarが使えたほうが、覚える予約語が減って良いのではないか?

var values = new string[] { "234.56", "456.78", "345.67", "123.45" };
var results =
    from value in values
    var parsed = double.Parse(value)    // varでいいじゃん?(もちろんNG)
    select new
    {
        R = parsed,
        Length = parsed * 2 * Math.PI
    };

何故letが導入されたのかは明らかではないが、私が感じた理由を示そうと思う。
まず、上のコードのアウトプットを少し増やす。

var values = new string[] { "234.56", "456.78", "345.67", "123.45" };
var rand = new Random();
var results =
    from value in values
    let parsed = double.Parse(value)
    let randomValue = rand.Next((int)parsed)    // 乱数を生成する
    select new
    {
        R = parsed,
        Length = parsed * 2 * Math.PI,
        Rand = randomValue
    };

ちょっと強引な例だが、パースした数値の範囲の乱数を加えた。見ての通り、あらかじめ代入した範囲変数parsedを使って、別の範囲変数を生成することも出来る。この辺りは、通常のローカル変数の感覚と全く変わらない。次のようなコードを書くまでは:

var values = new string[] { "234.56", "456.78", "345.67", "123.45" };
var rand = new Random();
var results =
    from value in values
    let parsed = double.Parse(value)
    let randomValue = rand.Next((int)parsed)
    orderby parsed  // ちょっとソートしてみようか。
    select new
    {
        R = parsed,
        Length = parsed * 2 * Math.PI,
        Rand = randomValue
    };

私は、上記のselectまで書いたところで、「凍り付いた」。意味が分かるだろうか?
parsedの値で昇順にソートするために、orderbyを書いた。ここまでは良いのだが、その下のselectが一体どうなってしまうのか、非常に不安になった。もちろん、parsedは昇順に並び替えられた順序でやってくる(select句はSelect拡張メソッドに対応している。OrderByの列挙子で順番に値が渡される事を思い出そう)。
では、randomValueはどうなのか?

上のクエリ構文を見ていると、randomValueはorderbyとは関係がないように見える。実際、その下のselect句でrandomValueをそのまま使っている。と言うことは?ソートされるのはparsedの値だけで、randomValueはソートされずに渡されるのか?すると、組み合わせるべき結果がメチャメチャになってしまうのではないか?
(いやいやいや、GetEnumeratorで渡されるというインフラを無視して、ワープしたかのように別のルートで値を渡すなど不可能、不可能なハズだ…?)

もし、let句が無く、varと「書けた」としたら、益々この罠に掛かったことだろう。

翌々書いておく。「ローカル変数」と「範囲変数」は異なるのだ。異なるのだ。異なるのだ。
上記のクエリ構文をメソッド構文に置き換える事が出来るだろうか? この罠に掛かってからは、メソッド構文のイメージが全く掴めなかった。結局、ILSpyでコードを確認して、以下のように変換されることが分かった。

var values = new string[] { "234.56", "456.78", "345.67", "123.45" };
var rand = new Random();
var results =
    values.
    Select(delegate(value)
        {
            var parsed = double.Parse(value);
            return new  // 不可視の匿名クラス
            {
                parsed = parsed,    // let parsedに対応
                randomValue = rand.Next((int)parsed)    // let randomValueに対応
            };
        }).
    OrderBy(delegate(entry)
        {
            return entry.parsed;
        }).
    Select(delegate(entry)
        {
            return new
            {
                R = entry.parsed,
                Length = entry.parsed * 2 * Math.PI,
                Rand = entry.randomValue
            };
        });

letのあるべき部分に、上記のような不可視の匿名クラスが作られ、Selectで一旦射影される。つまり、parsedとrandomValueはその時点の値がセットとして扱われる。だから、直後のOrderByでソートされても、parsedとrandomValueが誤った組み合わせになる事は無い。最後のSelectまで、この組み合わせは維持される。

letとletの間にwhereを入れたりした場合でも、新たな不可視の匿名クラスが作られ、Selectで射影される。分離されたletが存在するだけ、匿名クラスが増えることになる。これはつまり、分離されたletが沢山あるほど、匿名クラスの種類が膨れ上がると言う事だ。まあ、それはまだいい(コンパイラが勝手にやっていることだから)が、その度にnewされるというのは気持ちの良いことではない。この匿名クラスの生成とnewはかなりパターン化していると思われるので、ひょっとするとJITは何か工夫するかもしれない。

実際、範囲変数を正しく振る舞わせる為には、上記のようにするしかないだろう。で、メソッド構文が最も正確にLINQを表現できるとしても、上記のようなコードを書くのは面倒だ。やはりletが使えるクエリ構文が手放せない。私はいつも直感で書くのであまり注意していなかったが、自分でパターンを考えてみると、基本はクエリ構文で書き、letが不要な場合にはメソッド構文を選択しているようだ。

しかし、クエリ構文で書くデメリットもある。以前に述べた拡張メソッドとの相性の問題もあるが、クエリに問題があった場合に追跡が面倒だ。メソッド構文で書いていると、適当な場所でパイプラインをぶった切って、ToList()をかますことで、そこに流れたデータを直接デバッガで可視化出来る(データ量が多いとこの方法は使えないが、デバッグ時だから与えるデータを工夫すればいい)。

クエリ構文だと「ぶった切る」事が出来ない。letを使っているとクエリが複雑化しやすい上にこの制限があるのが辛い。
将来のVisual Studioでパイプラインの流れを可視化出来る何かが追加されると、非常に強力なのだが…
#使った事は無いが、Resharperはクエリ構文をリファクタリングで分割出来るようだ。さすがに強力。

LINQは本当に強力だ (6) TextFieldContext

抽象的な話ばかり続いたので、今回は、実用的な例を示そう。
.NETでCSVファイルを読み取るとき、まさか自分でパースしたりしていないと思うが、知っていると便利なクラスが「VB.NET」のライブラリに存在する。TextFieldParserクラスだ。VB向けの実装の割には、Streamからの読み取りに対応しているなど、割としっかり作ってある。
今回はこのクラスをLINQで「楽に」使えるようにする。

public static class TextField
{
    // 指定されたCSVファイルへのコンテキストを生成する
    public static IEnumerable<string[]> Context(
        string path, string separator = ",", Encoding encoding = null)
    {
        using (Stream stream =
            new FileStream(path, FileMode.Open, FileAccess.Read, FileShare.Read))
        {
            using (TextFieldParser parser =
                new TextFieldParser(stream, encoding ?? Encoding.UTF8, true, false))
            {
                parser.TextFieldType = FieldType.Delimited;
                parser.Delimiters = new[] { separator };
                parser.HasFieldsEnclosedInQuotes = true;
                parser.TrimWhiteSpace = true;
                while (parser.EndOfData == false)
                {
                    string[] fields = parser.ReadFields();
                    yield return fields;
                }
            }
        }
    }
}

このクラスのアイデアは、LINQ to Entitiesだ。Contextメソッドで一旦「コンテキスト」を作ってしまえば、面倒な事を一切考えなくても読み取りが可能になる。これでロジックから解放だ。
郵便局 郵便番号データ(全国)を使う。

static void Main(string[] args)
{
    // 郵便番号データのコンテキストを生成
    IEnumerable<string[]> context = TextField.Context(
        @"KEN_ALL.CSV", ",", Encoding.GetEncoding(932));

    // (クエリは遅延実行なので、以下の式ではまだ処理を開始していない)
    IEnumerable<string> results =
        // コンテキストからフィールド群を取得
        from fields in
            context.
            AsParallel() // 並列化
        // 郵便番号データの住所部分に「字」と「条」が含まれている行を抽出し、
        where fields[8].Contains("字") || fields[8].Contains("条")
        // 郵便番号の降順でソートし、
        orderby fields[2] descending
        // 文字列形式にフォーマットする
        select string.Format("〒{0} {1}{2}{3}", fields[2], fields[6], fields[7], fields[8]);

    // 取りあえず、結果をコンソールに出してみた(ここでGetEnumeratorが呼ばれて実行が開始される)
    foreach (string result in results)
    {
        Console.WriteLine(result);
    }
}

データ量が少ないので、並列化の恩恵はあまりないが、AsParallelしてみた。AsParallelを付けたり外したりしてみて、タスクマネージャのCPUリソースの具合を確認して見ると良い。

前回、LINQのパイプライン実行について説明したが、上記のコードの良い点は、コンテキストからデータが流れるようにやってきて、クエリで加工されて結果が出力される(コンソールに表示される)というところだ。実は、orderby句(OrderByDescending拡張メソッド)は、内部でバッファリングを行っているので、件数に応じてメモリ使用量が増加してしまうが、orderbyが無ければゴミをGCが回収するため、メモリ使用量が増え続けてしまう事はない。
(orderbyはソートを行うのだが、ソートを行うためにはすべてのデータが揃わなければならない。いくらパイプライン実行でも、不可能なことはある。その代わり、AsParallelしていれば、スレッド数に応じてソートが高速化される。)

さあ、仕上げだ。目の前にCSVファイルの山があったとしよう。

static void Main(string[] args)
{
    IEnumerable<string> results =
        from path in
            Directory.GetFiles("CSV_FILES", "*.csv", SearchOption.AllDirectories).
            AsParallel()
        from fields in
            TextField.Context(path, ",", Encoding.GetEncoding(932))
        where fields[8].Contains("字") || fields[8].Contains("条")
        orderby fields[2] descending
        select string.Format("〒{0} {1}{2}{3}", fields[2], fields[6], fields[7], fields[8]);

    foreach (string result in results)
    {
        Console.WriteLine(result);
    }
}

涙が出るほど簡単で、しかも速い。鳥肌が立つね :-)

LINQは本当に強力だ (5) クエリ構文とメソッド構文

アルゴリズムを記述する拡張メソッドは色々書いてみただろうか?

拡張メソッドを書きたくなる場合を考えると、結局のところは、いかにループロジックを書かなくて済むように出来るか?と言う所から始まるように思う。

他の例として:

  • 連続する隣り合う要素をペアにして列挙
    → [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のような「クエリ条件だけ保持して何もしない」クラスのインスタンスを返しているだけだからだ。それを一時変数に入れたところで、動作は全く変わらない。