Advent LINQ (10): .NET 2.0でLINQを使う

LINQは、正式には.NET 3.5 / C# 3.0でサポートされた。しかし、強力な柔軟性と拡張性の高さを、.NET 2.0のプロジェクトでも使いたいと思う事がある。実は、工夫さえすれば、.NET 2.0環境でもLINQを使う事が出来る。
LINQを使うためには、2つの要件を満たす必要がある。

  • C#コンパイラが、LINQクエリ構文を解釈出来るようにする。
    これを満たすためには、C# 3.0以上のコンパイラを使用すればよい。つまり、Visual Studio 2008以上の環境を使えば、コンパイラはfrom・where・select・orderbyなどのLINQクエリ構文や、ラムダ式を解釈可能になる。例え、コンパイラのターゲットが.NET 2.0に設定されていても、これらの構文は解釈可能だ。
  • LINQの拡張メソッド群(Enumerableクラスなど)が必要。
    これは当然、.NET 2.0のmscorlib.dllやSystem.dllには含まれていない。従って、何とかして用意する必要がある。

前者の要件に絡む、分かりにくい問題がある。「拡張メソッド」の扱いだ。C# 3.0以上のコンパイラを使えば、拡張メソッド構文は解釈可能だ。但し、拡張メソッドが定義されたクラスは特殊な扱いを受ける。

// 独自実装のEnumerable
[Extension] // <-- Extension属性
public static class Enumerable
{
    // 独自実装のWhere
    [Extension] // <-- Extension属性
    public static IEnumerable<T> Where<T>(this IEnumerable<T> enumerable, Func<T, bool> predict)
    {
        foreach (var value in enumerable)
        {
            if (predict(value) == true)
            {
                yield return value;
            }
        }
    }
}

C# 3.0以上のコンパイラで拡張メソッドを定義すると、暗黙にExtensionAttribute属性がクラスとメソッドに適用される(上の例ではわざと書いた)。そのため、アセンブリを生成する際にこの拡張メソッドが見つからないと、ビルドに失敗する。当然、.NET 2.0のmscorlib.dllやSystem.dllには存在しないため、以下のようなコードも盛り込んでおく必要がある。

namespace System.Runtime.CompilerServices
{
    // オレオレExtension属性
    [AttributeUsage(AttributeTargets.Assembly | AttributeTargets.Class | AttributeTargets.Method)]
    public sealed class ExtensionAttribute : Attribute
    {
        public ExtensionAttribute()
        {
        }
    }
}

そして、こまごまとしたクラス(例えば、Func<T>やAction<T>など)と、あなたが使いたい標準的なLINQ拡張メソッド群(Where<T>やSelect<T>やOrderBy<T>等)を用意する必要がある。これらを用意すれば、「ほぼ」C# 3.5以降のLINQを模倣できる。
ほぼ、と書いたのは、どうしても回避出来ない制限が一つだけあるためだ。それは、IEnumerable<T>が、ジェネリック共変性をサポートしていない事による。これによって発生する問題は別の機会に譲るとして、実際問題、大量のLINQ拡張メソッドを自前で準備するのはなかなか難しい。

そして、同じような事を考える人は世の中にも大勢いて、NuGetでパッケージ化されていたりもするので、特に理由が無ければ、このようなパッケージを利用したほうが良いだろう。以下の「linqbridge」は、単一ソースコードのバージョンもあるので、自分のライブラリに容易に組み込みやすいだろう。

linqbridge – Re-implementation of LINQ to Objects for .NET Framework 2.0
NuGet LINQBridge
NuGet LINQBridge (Embedded)

なお、linqbridgeはPLINQをサポートしていない。AsParallel()から始まるPLINQを用意するのは複雑すぎる。自前で実装するのは不可能ではないが、そんな事を考えるならC# 3.0に移行する事を真剣に考えた方が良い。どうしても並列実行を諦めることが出来ないのなら、TPLの自前実装で我慢しよう。Palallel.ForEach()なら、自力でも実装できるはずだ。

Advent LINQ (9): ParallelQuery対応拡張メソッドの実装

LINQクエリ中で使用出来る拡張メソッドを実装するとき、その引数シグネチャはIEnumerable<T>で受ける事になる。

public static class LinqExtensions
{
    // パブリックなデフォルトコンストラクタを持つ型を抽出する
    public static IEnumerable<Type> OfCreatable(this IEnumerable<Type> enumerable)
    {
        return
            from type in enumerable
            where
                (type.IsPublic == true) &&  // パブリックであり、
                (type.IsClass == true) &&   // クラスであり、
                (type.IsAbstract == false) &&   // 抽象クラスではなく
                (type.GetConstructor(Type.EmptyTypes) != null)  // パブリックなデフォルトコンストラクタがある
            select type;
    }
}

この拡張メソッドを使ってみる。

// mscorlib.dllのすべての型から、生成可能なクラスを抽出する
var types = typeof(object).Assembly.GetTypes();
var creatables = types.OfCreatable();

この時、typesはType[]なので、引数のIEnumerable<Type>に合致する。OfCreatableに実装したLINQクエリは以下のように拡張メソッドで書き直せる。

public static class LinqExtensions
{
    // パブリックなデフォルトコンストラクタを持つ型を抽出する
    public static IEnumerable<Type> OfCreatable(this IEnumerable<Type> enumerable)
    {
        return
            enumerable.Where(type =>
                (type.IsPublic == true) &&  // パブリックであり、
                (type.IsClass == true) &&   // クラスであり、
                (type.IsAbstract == false) &&   // 抽象クラスではなく
                (type.GetConstructor(Type.EmptyTypes) != null));    // パブリックなデフォルトコンストラクタがある
    }
}

ここで、typesを並列化したらどうなるだろうか。

// mscorlibのすべての型から、生成可能なクラスを抽出する
var types = typeof(object).Assembly.GetTypes().AsParallel();    // 並列化
var creatables = types.OfCreatable();

varを書き直すと、以下のようになる。

// mscorlib.dllのすべての型から、生成可能なクラスを抽出する
ParallelQuery<Type> types = typeof(object).Assembly.GetTypes().AsParallel();  // 並列化
IEnumerable<Type> creatables = types.OfCreatable();

AsParallel()によって、列挙子の方がParallelQuery<Type>となる。しかし、OfCreatableの引数はIEnumerable<Type>なので、暗黙のキャストが発生し、結局OfCreatable内のLINQクエリは並列化されないまま実行される(以前の連載で述べたように、これは暗黙のゲートだ)。念のため、こういうことだ:

// mscorlib.dllのすべての型から、生成可能なクラスを抽出する
ParallelQuery<Type> types = typeof(object).Assembly.GetTypes().AsParallel();  // 並列化
IEnumerable<Type> creatables = LinqExtensions.OfCreatable((IEnumerable<Type>)types);    // IEnumerable<Type>に戻してから渡される

では、OfCreatable内のLINQクエリを並列化したい場合はどうすれば良いだろうか?

public static class LinqExtensions
{
    // パブリックなデフォルトコンストラクタを持つ型を抽出する
    public static IEnumerable<Type> OfCreatable(this IEnumerable<Type> enumerable)
    {
        return
            from type in enumerable.AsParallel()    // <-- ここで並列化
            where
                (type.IsPublic == true) &&  // パブリックであり、
                (type.IsClass == true) &&   // クラスであり、
                (type.IsAbstract == false) &&   // 抽象クラスではなく
                (type.GetConstructor(Type.EmptyTypes) != null)  // パブリックなデフォルトコンストラクタがある
            select type;
    }
}

並列化したいのだから、内部のLINQクエリでもAsParallel()で並列化すればよいと思うかもしれないが、これは微妙だ。引数のところでゲートが出来ていることは解消されない(IEnumerable<Type>になる)ため、OfCreatableを呼び出す直前のクエリが並列クエリであったとしても、一旦並列性が解除されてしまう。
また、戻り値として返される列挙子もIEnumerable<Type>なので、ここでもゲートを作ってしまう。そして、AsParallelがハードコードされたことで、わざと非並列状態で実行させたくても出来ないという問題もある。
これらを解消するには、以下のようにすればよい。

public static class LinqExtensions
{
    // パブリックなデフォルトコンストラクタを持つ型を抽出する(非並列化)
    public static IEnumerable<Type> OfCreatable(this IEnumerable<Type> enumerable)
    {
        return
            from type in enumerable
            where
                (type.IsPublic == true) &&  // パブリックであり、
                (type.IsClass == true) &&   // クラスであり、
                (type.IsAbstract == false) &&   // 抽象クラスではなく
                (type.GetConstructor(Type.EmptyTypes) != null)  // パブリックなデフォルトコンストラクタがある
            select type;
    }

    // パブリックなデフォルトコンストラクタを持つ型を抽出する(並列化)
    public static ParallelQuery<Type> OfCreatable(this ParallelQuery<Type> parallelEnumerable)
    {
        return
            from type in parallelEnumerable
            where
                (type.IsPublic == true) &&  // パブリックであり、
                (type.IsClass == true) &&   // クラスであり、
                (type.IsAbstract == false) &&   // 抽象クラスではなく
                (type.GetConstructor(Type.EmptyTypes) != null)  // パブリックなデフォルトコンストラクタがある
            select type;
    }
}

要するに、引数(と戻り値)の列挙子の型が、ParallelQuery<T>となるようなオーバーロードを用意する。すると、中のLINQクエリの記述が全く同一であったとしても、それらの拡張メソッド(WhereやSelect等)は、Enumerable.WhereとParallelEnumerable.Whereのように呼び分けが行われる。結果として、並列バージョンではクエリ全体が並列化され、IEnumerable<T>のような通常の列挙子から呼び出される場合は、非並列クエリとなる。
これで目的を達したのだが、最後にこのメソッドを、非並列バージョンと並列バージョンのクラスに分ける。

// LINQ拡張メソッド群(非並列バージョン)
public static class LinqExtensions
{
    // パブリックなデフォルトコンストラクタを持つ型を抽出する
    public static IEnumerable<Type> OfCreatable(this IEnumerable<Type> enumerable)
    {
        return
            from type in enumerable
            where
                (type.IsPublic == true) &&  // パブリックであり、
                (type.IsClass == true) &&   // クラスであり、
                (type.IsAbstract == false) &&   // 抽象クラスではなく
                (type.GetConstructor(Type.EmptyTypes) != null)  // パブリックなデフォルトコンストラクタがある
            select type;
    }
}
// LINQ拡張メソッド群(並列バージョン)
public static class ParallelLinqExtensions
{
    // パブリックなデフォルトコンストラクタを持つ型を抽出する
    public static ParallelQuery<Type> OfCreatable(this ParallelQuery<Type> parallelEnumerable)
    {
        return
            from type in parallelEnumerable
            where
                (type.IsPublic == true) &&  // パブリックであり、
                (type.IsClass == true) &&   // クラスであり、
                (type.IsAbstract == false) &&   // 抽象クラスではなく
                (type.GetConstructor(Type.EmptyTypes) != null)  // パブリックなデフォルトコンストラクタがある
            select type;
    }
}

このように、非並列バージョンと並列バージョンの拡張メソッドを分けることで、丁度EnumerableクラスとParallelEnumerableクラスが分けられているのと同じ構造となる。

Advent LINQ (8): ElementAt

前回に続き、もう一つ別の例を考える。Enumerable.ElementAt()だ。このメソッドは、列挙子に対してインデックス値で指定された位置の要素を取得する。

public static class LinqExtensions
{
    public static T ElementAt<T>(this IEnumerable<T> enumerable, int index)
    {
        var i = 0;
        foreach (var value in enumerable)
        {
            if (i >= index)
            {
                return value;
            }
            i++;
        }
        throw new IndexOutOfRangeException();
    }
}

これもまた、列挙子を実際に列挙しなければ、目的の値を得ることが出来ない。Listや配列であれば、インデクサアクセスが可能なはずだ。そこで:

public static class LinqExtensions
{
    public static T ElementAt<T>(this IEnumerable<T> enumerable, int index)
    {
        // IListにキャスト出来れば
        var list = enumerable as IList;
        if (list != null)
        {
            // 直接要素を得る(非ジェネリックなのでT型へキャストが必要)
            return (T)list[index];
        }

        var i = 0;
        foreach (var value in enumerable)
        {
            if (i <= index)
            {
                return value;
            }
            i++;
        }
        throw new IndexOutOfRangeException();
    }
}

IListを使えば、インデクサによるアクセスが可能だ。これにより、要素を列挙しなくても、任意の位置の値を直接引き出す事が出来る。更に、.NET 4.5からはIReadOnlyListもサポートされるようになったので、このインターフェイスへのキャストも試みると良いだろう。

Advent LINQ (7): Count

Enumerable.Count()メソッドの特徴を考えてみる。ただ要素数を数えるだけなら、以下のような実装で良い筈だ。

public static class LinqExtensions
{
    public static int Count<T>(this IEnumerable<T> enumerable)
    {
        var count = 0;
        foreach (var value in enumerable)
        {
            count++;
        }
        return count;
    }
}

当たり前だが、これでは要素を全て列挙しなければ個数が分からない。例えば:

// 100000000個の値が入ったリスト
var values = Enumerable.Range(0, 100000000).ToList();

// 有意に時間がかかる
var count1 = LinqExtensions.Count(values);

// こちらは一瞬
var count2 = Enumerable.Count(values);

何故、Enumerable.Count()は速いのだろうか。それは、列挙子の実行時の型を見て最適化を行っているからだ。ICollectionインターフェイスを実装しているクラスであれば、Countプロパティを参照するだけで個数が識別出来る。この方法を利用するには、以下のようにキャストで判定する。

public static class LinqExtensions
{
    public static int Count<T>(this IEnumerable<T> enumerable)
    {
        // 列挙子がICollectionを実装していれば
        var collection = enumerable as ICollection;
        if (collection != null)
        {
            // 直接Countプロパティを参照する
            return collection.Count;
        }

        var count = 0;
        foreach (var value in enumerable)
        {
            count++;
        }
        return count;
    }
}

列挙子として配列を使用する場合、配列の長さを調べるにはLengthプロパティを参照する。しかし、配列は暗黙にICollectionインターフェイスを実装しているため、わざわざ配列かどうかを確認しなくても、上記コードがそのまま使える。

Advent LINQ (6): Match

Regexクラスを使うと正規表現を使って文字列のキャプチャが出来る。多少なりとも簡単に連続判定できるようにしてみる。

public static class LinqExtensions
{
    public static IEnumerable<Match> Match(
        this IEnumerable<string> sentences,
        string pattern,
        RegexOptions options = RegexOptions.Compiled | RegexOptions.Multiline)
    {
        var regex = new Regex(pattern, options);
        foreach (var sentence in sentences)
        {
            foreach (Match match in regex.Matches(sentence))
            {
                yield return match;
            }
        }
    }
}

これで、引数に正規表現パターンを指定するだけで、連続する文字列に処理が可能となった。

// 文字列中に存在するIPv4アドレスを抽出する
var sampleDatas = new[] { "IP:133.0.0.0", "IP:133.255.255.255 primary", "[192.50.0.0]", "IPn192.50.255.255n" };
foreach (var match in
    sampleDatas.Match(@"(?<1>d+)(?:.(?<1>d+)){3}"))
{
    Console.WriteLine(match);
}

上記の例では、ハードコードされた文字列を扱っているが、Advent LINQ (2)で示したTextReader.AsEnumerableと組み合わせれば、LINQクエリ一文でファイルからの正規表現検索が実現する。壮大な時計仕掛けをやってみよう。

// 指定されたフォルダ配下のテキストファイル群からIPv4アドレスを抽出する(並列実行)
foreach (var match in
    from path in Extensions.FilesAsEnumerable(@"C:project", "*.txt").AsParallel()
    from match in File.OpenText(path).AsEnumerable().Match(@"(?<1>d+)(?:.(?<1>d+)){3}")
    select match)
{
    Console.WriteLine(match);
}

MatchはIEnumerable<string>を受け取るようになっているので、列挙子ではなく単一の文字列を受けるには、1要素の配列を作る必要がある。この部分が分かりにくいのであれば、Match(this string sentence, …) のような、単一の文字列だけを受け取るようなメソッドに変更し、明示的にselect句で射影するようにしてもよい。ただ、その場合は、正規表現をコンパイルするメリットが失われるかもしれない。
参考: .NET Frameworkがサポートする正規表現クラスを徹底活用する

Advent LINQ (5): Flatten

Advent LINQ (3)で、フォルダを探索しながらファイルを列挙するFilesAsEnumerableを作った。このような、木構造のシーケンスを探索するというシチュエーションは、色々ありそうだ。なので、このアルゴリズムを一般化する事を考える。

public static class LinqExtensions
{
    public static IEnumerable<U> Flatten<T, U>(
        this T node,
        Func<T, IEnumerable<T>> predictBySubNode,
        Func<T, IEnumerable<U>> predictByNode)
    {
        var bySubNode =
            from subNode in predictBySubNode(node)
            from childNode in Flatten(subNode, predictBySubNode, predictByNode)
            select childNode;

        var byNode =
            from childNode in predictByNode(node)
            select childNode;

        return bySubNode.Concat(byNode);
    }
}

これを使ってファイルの探索を行うには、以下のように記述する。

var baseDirectory = new DirectoryInfo(@"C:project");
foreach (var file in baseDirectory.Flatten(
    directory => directory.GetDirectories(),
    directory => directory.GetFiles("*.cs")))
{
    Console.WriteLine(file.FullName);
}

XmlDocumentから、テキストノードを抜き出してみる。

var document = new XmlDocument();
document.Load(@"C:projectdata.xml");
foreach (var text in document.DocumentElement.Flatten(
    element => element.SelectNodes("*").Cast<XmlElement>(),
    element => element.SelectNodes("text()").Cast<XmlText>()))
{
    Console.WriteLine(text.Value);
}

もちろん、XDocumentにも応用可能。

Advent LINQ (4): Buffering

列挙子を非同期で実行して、可能なら結果をキューに蓄積したい場合がある。列挙子の要素生成速度が十分に早ければ、並列実行出来ることになる。
並列実行コレクションに、丁度この目的に使えるBlockingCollectionクラスがある。

public static class LinqExtensions
{
    public static IEnumerable<T> Buffering<T>(this IEnumerable<T> enumerable, int queueCount = 10)
    {
        var queue = new BlockingCollection<T>(queueCount);
        Task.Factory.StartNew(() =>
            {
                try
                {
                    foreach (var value in enumerable)
                    {
                        queue.Add(value);
                    }
                }
                finally
                {
                    queue.CompleteAdding();
                }
            });

        return queue.GetConsumingEnumerable();
    }
}

使うときは、非同期化したい列挙子の直後に指定するだけだ。

var r = new Random();
foreach (var value in
    Enumerable.Range(0, 1000000).
    Select(index => r.Next()).
    Buffering(1000))
{
    Console.WriteLine(value);
}

これで、乱数の生成は最大1000個まで非同期で実行されてバッファリングされる。コンシューマー側(foreach)の処理が遅く、乱数の生成が早ければ、効率よく動作する。

Advent LINQ (3): FilesAsEnumerable

Directory.GetFilesが配列を返すので、列挙子にしてみる。特にSearchOption.AllDirectoriesが指定されると、処理が返って来るまでにかなり時間がかかることがある。
フォルダーは再帰探索する必要があるので、実装は少し捻る必要がある。

public static class LinqExtensions
{
    public static IEnumerable<string> FilesAsEnumerable(string path, string patterns)
    {
        foreach (var directoryPath in
            Directory.GetDirectories(path, "*", SearchOption.TopDirectoryOnly))
        {
            foreach (var filePath in
                FilesAsEnumerable(directoryPath, patterns))
            {
                yield return filePath;
            }
        }

        foreach (var filePath in
            Directory.GetFiles(path, patterns, SearchOption.TopDirectoryOnly))
        {
            yield return filePath;
        }
    }
}

これでもいいのだが、foreachだらけで見通しが悪い。全てクエリに置き換える。

public static class LinqExtensions
{
    public static IEnumerable<string> FilesAsEnumerable(string path, string patterns)
    {
        var byDirectory =
            from directoryPath in Directory.GetDirectories(path, "*", SearchOption.TopDirectoryOnly)
            from filePath in FilesAsEnumerable(directoryPath, patterns)
            select filePath;

        var byFile =
            from filePath in Directory.GetFiles(path, patterns, SearchOption.TopDirectoryOnly)
            select filePath;

        return byDirectory.Concat(byFile);
    }
}

これでファイルの列挙は以下のように記述できる。

foreach (var path in LinqExtensions.FilesAsEnumerable(@"C:project", "*.cs"))
{
    Console.WriteLine(path);
}

ファイルの逐次探索が可能になったので、大量のファイルをパイプライン処理できるようになった。
なお、このコードは.NET 4.0以降では、Directory.EnumerateFilesとほぼ同じ動作となる。

Advent LINQ (2): TextReader.AsEnumerable

TextReaderで読み取れる行を、列挙子に変えてみる。

public static class LinqExtensions
{
    public static IEnumerable<string> AsEnumerable(this TextReader tr)
    {
        try
        {
            while (true)
            {
                var line = tr.ReadLine();
                if (line == null)
                {
                    break;
                }
                yield return line;
            }
        }
        finally
        {
            tr.Dispose();
        }
    }
}

TextReaderは全て読み取った時点でDisposeを呼び出している。こうする事で、

foreach (var line in File.OpenText("VeryLongTextFile.txt").AsEnumerable())
{
    Console.WriteLine(line);
}

という使い方をしても、列挙が終わればリーダーがクローズされるようになる。
一旦列挙子になってしまえば、

// フォルダ内のすべてのテキストファイルの、先頭・終端の空白を削除し、
// 空行や#で始まる行を除外して、ソートして表示
foreach (var line in
    from path in
        Directory.GetFiles(".", "*.txt", SearchOption.AllDirectories).
        AsParallel()
    from line in
        File.OpenText(path).
        AsEnumerable()
    let trim = line.Trim()
    where (trim.Length >= 1) && (trim.StartsWith("#") == false)
    orderby trim
    select trim)
{
    Console.WriteLine(line);
}

こんなことも自在に行える。