Azure Table の検索条件を LINQ で指定する

Azure Storage の SDK (Windows Azure Storage) を利用して .NET のクライアントから Table のデータを取得する際に、
検索条件を指定しようとすると、通常の実装では次のようなコードになり少し複雑です。
この例では、フィルター条件を 2 つ指定しています。


var query = new TableQuery<Person>()
    .Where(TableQuery.CombineFilters(
        TableQuery.GenerateFilterCondition("PartitionKey", QueryComparisons.Equal, "2015"),
        TableOperators.And,
        TableQuery.GenerateFilterConditionForInt("Age", QueryComparisons.LessThan, 20)));

var result = PeopleTable.ExecuteQuery(query).ToArray();


ここで、Person  は TableEntity を継承したクラスで、PeopleTable は CloudTable 型のオブジェクトです。

結局、上記の Where メソッドに渡されるのは、

(PartitionKey eq ‘2015’) and (Age lt 20)

という文字列になります。
これなら string.Format メソッドでもよいのではないのかという気もしますが、
プログラミングのミスを防ぐためには、フィルターや射影などの検索条件は LINQ で指定したいところです。

検索条件を LINQ で指定する方法として TableServiceContext クラスを使う方法もあるようですが、
現在は Obsolete 属性が指定されており、非推奨となっています。

とはいえ、自力で IQueryable<T> を実装するのも骨が折れるので、
ここでは簡易的に、TableQuery<T> の拡張メソッドとして Select および Where メソッドを実装していきます。
ラムダ式で指定された検索条件を式ツリーとして受け取って解析し、動的にクエリを生成します。

このような TableHelper クラスを実装することで、Azure Table の検索条件を LINQ で指定できるようになります。
ただし、文字列の不等式については、String クラスの演算子として不等号が定義されていないため、

p.LastName >= "W"

と書くことができず、

p.LastName.CompareTo("W") >= 0

のようにせざるを得ませんでした。

 

作成したサンプル
ExpressionsConsole (GitHub)

バージョン情報
Windows Azure Storage 6.0.0

参照
Windows Azure Storage
Expression<TDelegate> クラス
TableQuery<TElement> Class

Windows Azure Storage Extensions
テーブル サービスに対する LINQ クエリの作成 (古い形式)
TableServiceContext Class (古い形式)

広告

エンティティを匿名型で手軽に実装する (1)

ここでは、次のようなものをエンティティ型と呼ぶことにします。

  • プロパティが定義されている
  • 各プロパティの値を指定してインスタンスを初期化する方法 (コンストラクターなど) が用意されている

通常、これを C# で実装すると次の図のようになり、少し手間がかかると思うことがあります。
Class1 はコンストラクターの実装が必要であり、Class2 はインスタンス生成時にプロパティ名を指定する必要があります。

エンティティ型の宣言

 

そこで今回は、匿名型を活用してこのようなエンティティ型を定義する方法を考えてみたいと思います。

実は匿名型は、プロパティは読取り専用で定義され、プロパティの数だけ引数を持つコンストラクターが 1 つだけ定義されます。
つまり、ちょうど上記の Class1 のような構造をしています。

このコンストラクターにアクセスできれば、任意のタイミングで匿名型のインスタンスを生成できるというわけです。
そこで、次のように EntityType クラスを実装してみました。

匿名型によりプロパティを宣言し、CreateEntity メソッドによりインスタンスを初期化できます。
CreateEntity メソッドの引数は params object[] のため IntelliSense は利きませんが、簡単に書けている気がします。
ただし匿名型のため、ローカル スコープを抜けられないという制限があります。

 

次に、これを CSV ファイルの読み込みに応用します。
CsvFile クラスで、読み込んだデータを指定された型に変換します。

(なお、ConvertHelper.cs は省略されています。完全なソースコードは ExpressionsConsole – GitHub にあります。)

このようにすると、CsvFile クラスを呼び出す側では IntelliSense が利き、LINQ to Objects でアクセスできます。

CsvFile (IntelliSense)

 

さて、インスタンスを生成するときに毎回 ConstructorInfo にアクセスするのは少しコストがかかるので、
次回は式ツリーを利用してパフォーマンスを改善したいと思います。

次回: エンティティを匿名型で手軽に実装する (2)

作成したサンプル
ExpressionsConsole (GitHub)

参照
匿名型 (C# プログラミング ガイド)

LINQ のクエリ パターン

Visual Studio で C# のプロジェクト (ここではコンソール アプリケーションにしています) を作成して、
次のようなクエリ式を書いてみます。

Program.cs


class Program
{
    static void Main(string[] args)
    {
        var result =
            from x in new Monad<int>()
            select x;
    }
}

public class Monad<T>
{
}


Monad<T> はとりあえず空のジェネリック クラスです。
この状態でビルドすると、

「ソース型 ○○ のクエリ パターンの実装が見つかりませんでした。’Select’ が見つかりません。」

というコンパイラ エラーになります。

コンパイラ エラー CS1936

 

このクエリ パターンとは LINQ 標準クエリ演算子のことで、具体的には Select, Where, OrderBy メソッドなどがあります。
標準クエリ演算子のクエリ式構文に対応が記載されており、
例えば C# で select 句が有効になるようにするには、
IEnumerable<T> でいうところの Enumerable.Select メソッドに相当するメソッドが実装されている必要があります。

 

というわけで、例として Maybe モナドとそのクエリ パターンを実装してみます。

Maybe.cs


public struct Maybe<T>
{
    public static readonly Maybe<T> None = new Maybe<T>();

    T _value;

    public T Value
    {
        get
        {
            if (!HasValue) throw new InvalidOperationException();
            return _value;
        }
    }

    public bool HasValue { get; private set; }

    public Maybe(T value)
        : this()
    {
        _value = value;
        HasValue = true;
    }

    public static explicit operator T(Maybe<T> value)
    {
        return value.Value;
    }

    public static implicit operator Maybe<T>(T value)
    {
        return new Maybe<T>(value);
    }

    public Maybe<TResult> Bind<TResult>(Func<T, Maybe<TResult>> func)
    {
        return HasValue
            ? func(_value)
            : Maybe<TResult>.None;
    }

    public override string ToString()
    {
        return HasValue
            ? _value.ToString()
            : "";
    }
}

public static class Maybe
{
    public static Maybe<T> ToMaybe<T>(this T value)
    {
        return value;
    }

    public static Maybe<TResult> Select<T, TResult>(this Maybe<T> maybe, Func<T, TResult> selector)
    {
        return maybe.HasValue
            ? selector((T)maybe)
            : Maybe<TResult>.None;
    }

    public static Maybe<TResult> SelectMany<T, U, TResult>(this Maybe<T> maybe, Func<T, Maybe<U>> selector, Func<T, U, TResult> resultSelector)
    {
        var selected = maybe.Bind(selector);
        return selected.HasValue
            ? resultSelector((T)maybe, (U)selected)
            : Maybe<TResult>.None;
    }

    public static Maybe<T> Where<T>(this Maybe<T> maybe, Func<T, bool> predicate)
    {
        return maybe.HasValue && predicate((T)maybe)
            ? maybe
            : Maybe<T>.None;
    }
}


Select メソッドのほか、

  • 複数の from 句に相当する SelectMany メソッド
  • where 句に相当する Where メソッド

を実装しています。
このようにクエリ パターンを実装しておくと、次のようにクエリ式を書くことができます。

Program.cs


class Program
{
    static void Main(string[] args)
    {
        var result1 = Add(1, 2); // 3
        var result2 = Add(2, 1); // None
        var result3 = Add(1, Maybe<int>.None); // None
    }

    static Maybe<int> Add(Maybe<int> x, Maybe<int> y)
    {
        return
            from _x in x
            from _y in y
            where _x < _y
            select _x + _y;
    }
}


 

このようにして、IEnumerable<T> インターフェイス以外でもクエリ式を利用することができます。
ちなみに、IObservable<T> インターフェイスのクエリ式については、
Reactive Extensionsの概要と利用方法にコード例が載っています。

 

作成したサンプル
MonadConsole (GitHub)

参照
コンパイラ エラー CS1936
標準クエリ演算子の概要
select 句 (C# リファレンス)
Query Expression Pattern で Maybe monad を書く
モナドの驚異

F# で素数を求める

以前に LINQ で素数を求める (C#) という記事を書きましたが、
その中にある GetPrimeNumbers 関数を F# で書いてみると、次のようになります。

 

Program.fs


open System
open System.Collections.Generic
open System.Diagnostics

module Seq2 =
    let do2 action source =
        seq {
            for x in source do
                action(x)
                yield x
        }

let getPrimeNumbers minValue maxValue =
    (
        new List<int64>(),
        Math.Max(minValue, 2L),
        Math.Max(maxValue, 0L),
        if maxValue >= 0L then (maxValue |> float |> Math.Sqrt |> int64) else 0L
    )
    |> Seq.singleton
    |> Seq.collect (fun (primes, min, max, root_max) ->
        (seq { 2L .. Math.Min(root_max, min  1L) }, seq { min .. max })
        ||> Seq.append
        |> Seq.map (fun i -> (primes, i, i |> float |> Math.Sqrt |> int64)))
    |> Seq.filter (fun (primes, i, root_i) ->
        primes
        |> Seq.takeWhile (fun p -> p <= root_i)
        |> Seq.forall (fun p -> i % p <> 0L))
    |> Seq2.do2 (fun (primes, i, _) -> primes.Add(i))
    |> Seq.map (fun (_, i, _) -> i)
    |> Seq.skipWhile (fun i -> i < minValue)

[<EntryPoint>]
let main argv = 
    let stopwatch = Stopwatch.StartNew()
    let result = (1000000000000L, 1000000001000L) ||> getPrimeNumbers |> Seq.toArray
    stopwatch.Stop()

    result |> Seq.iter (printfn "%A")
    stopwatch.Elapsed.TotalSeconds |> printfn "%A seconds"
    0


 

プログラムを実行します。

実行結果

結果は、C# よりも遅くなりました。
F# は構文糖衣が多く、コンパイル時にクラスに置き換わるものがあるため、
実行時に生成されるオブジェクトが多くなるのが原因であると予想されます。

 

作成したサンプル
PrimeNumbersConsoleF (GitHub)

バージョン情報
.NET Framework 4.5

参照
エラトステネスの篩 – Wikipedia
シーケンス (F#) (MSDN)
LINQ で素数を求める (C#)

カテゴリー: プログラミング言語. タグ: , . 1 Comment »

LINQ で素数を求める (C#)

素数を求める .NET (C#) のプログラムを、LINQ to Objects を利用して作成します。

素数を「自分自身より小さいすべての素数で割り切れない数」と解釈すれば、次のように実装できます。
引数に求める素数の範囲の最小値と最大値を指定できる関数として作成しています。

Program.cs


using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace PrimeNumbersConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            var stopwatch = Stopwatch.StartNew();
            var result = GetPrimeNumbers_Alpha(1000, 1100).ToArray();
            stopwatch.Stop();

            Array.ForEach(result, Console.WriteLine);
            Console.WriteLine("{0} seconds", stopwatch.Elapsed.TotalSeconds);
        }

        static readonly Func<long, long, IEnumerable<long>> GetPrimeNumbers_Alpha = (minValue, maxValue) =>
            new[] { new List<long>() }
                .SelectMany(primes => Enumerable2.Range2(2, maxValue)
                    .Select(i => new { primes, i }))
                .Where(_ => _.primes
                    .All(p => _.i % p != 0))
                .Do(_ => _.primes.Add(_.i))
                .Select(_ => _.i)
                .SkipWhile(i => i < minValue);
    }

    public static class Enumerable2
    {
        public static IEnumerable<long> Range2(long minValue, long maxValue)
        {
            for (var i = minValue; i <= maxValue; i++)
            {
                yield return i;
            }
        }

        public static IEnumerable<TSource> Do<TSource>(this IEnumerable<TSource> source, Action<TSource> action)
        {
            if (source == null) throw new ArgumentNullException("source");
            if (action == null) throw new ArgumentNullException("action");

            foreach (var item in source)
            {
                action(item);
                yield return item;
            }
        }
    }
}


素数を小さい順にキャッシュしておくための List<long> オブジェクトを最初に用意し、
それを各イテレーションで参照できるようにしています。
また、実装を概念的にシンプルにするため、拡張メソッドを自作しています (Range2, Do メソッド)。

 

さて、これを少し工夫すると、実行速度を大きく改善できます。

  • ある数が割り切れるとき、その約数の対は、一方が平方根以下の約数、他方が平方根以上の約数となるので、
    平方根以下の素数で割り切れるかどうかだけを調べれば十分である。
  • これに伴い、maxValue の平方根以下の素数だけをキャッシュさせておけば十分である。

これらの考慮を反映させると次のようになります。


static void Main(string[] args)
{
    var stopwatch = Stopwatch.StartNew();
    var result = GetPrimeNumbers(1000000000000, 1000000001000).ToArray();
    stopwatch.Stop();

    Array.ForEach(result, Console.WriteLine);
    Console.WriteLine("{0} seconds", stopwatch.Elapsed.TotalSeconds);
}

static readonly Func<long, long, IEnumerable<long>> GetPrimeNumbers = (minValue, maxValue) =>
    new[]
    {
        new
        {
            primes = new List<long>(),
            min = Math.Max(minValue, 2),
            max = Math.Max(maxValue, 0),
            root_max = maxValue >= 0 ? (long)Math.Sqrt(maxValue) : 0,
        }
    }
        .SelectMany(_ => Enumerable2.Range2(2, Math.Min(_.root_max, _.min  1))
            .Concat(Enumerable2.Range2(_.min, _.max))
            .Select(i => new { _.primes, i, root_i = (long)Math.Sqrt(i) }))
        .Where(_ => _.primes
            .TakeWhile(p => p <= _.root_i)
            .All(p => _.i % p != 0))
        .Do(_ => _.primes.Add(_.i))
        .Select(_ => _.i)
        .SkipWhile(i => i < minValue);


 

この実装であれば、1 兆前後の素数でも、最近のタブレット PC で 1 秒以内で求められます。

実行結果

 

ちなみに、素数の定義通りに実装するのであれば、次のようなシンプルな実装で済みます。


static readonly Func<long, long, IEnumerable<long>> GetPrimeNumbers_Org = (minValue, maxValue) =>
    Enumerable2.Range2(Math.Max(minValue, 2), maxValue).Where(i =>
        Enumerable2.Range2(2, i  1).All(j => i % j != 0));


 

F# 版も書きました: F# で素数を求める

 

作成したサンプル
PrimeNumbersConsole (GitHub)

バージョン情報
.NET Framework 4.5

参照
エラトステネスの篩 – Wikipedia
F# で素数を求める

カテゴリー: .NET Framework. タグ: . 2 Comments »

カリー化の LINQ への応用 (C#)

カリー化の実用について考えてみたいと思います。

まずは、C# でカリー化を表す関数を、拡張メソッドを使って以下のように実装していきます。
カリー化のほか、非カリー化および部分適用のための関数も実装しておきます。
引数の数ごとにメソッドを定義しなければなりませんが、ここではとりあえず T3 までにしておきます。


public static class FunctionHelper
{
    // カリー化
    public static Func<T1, Func<T2, TResult>> Curry<T1, T2, TResult>(this Func<T1, T2, TResult> func)
    {
        return p1 => p2 => func(p1, p2);
    }

    public static Func<T1, Func<T2, T3, TResult>> Curry<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func)
    {
        return p1 => (p2, p3) => func(p1, p2, p3);
    }

    // 非カリー化
    public static Func<T1, T2, TResult> Uncurry<T1, T2, TResult>(this Func<T1, Func<T2, TResult>> func)
    {
        return (p1, p2) => func(p1)(p2);
    }

    public static Func<T1, T2, T3, TResult> Uncurry<T1, T2, T3, TResult>(this Func<T1, Func<T2, T3, TResult>> func)
    {
        return (p1, p2, p3) => func(p1)(p2, p3);
    }

    // 部分適用
    public static Func<T2, TResult> Partial<T1, T2, TResult>(this Func<T1, T2, TResult> func, T1 arg1)
    {
        return func.Curry()(arg1);
    }

    public static Func<T2, T3, TResult> Partial<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func, T1 arg1)
    {
        return func.Curry()(arg1);
    }
}


 

さて、次のようなコレクション操作をしたいと思います。

  • 奇数の二乗を先頭から 10 個取得する
  • 処理結果は文字列として比較したときの順序で並べる
  • 処理結果は整数の配列型とする

期待結果は [1, 121, 169, 225, 25, 289, 361, 49, 81, 9] という配列ですが、LINQ to Objects で次のように書けます。


static void Main()
{
    var result = Enumerable.Range(1, int.MaxValue)
        .Where(i => i % 2 == 1)
        .Select(i => i * i)
        .Take(10)
        .OrderBy(Convert.ToString)
        .ToArray();
}


 

もしこの他に、「偶数」「3 で割り切れる」のようなロジックをどこかで実装しなければならないとしたらどうでしょう。

今回はラムダ式で書けてしまう程度の単純な例なのであまり利点が感じられないようにも見えますが、
関数自体をパラメーター化することで関心事を分離できます。
つまり、関数の本質に相当する部分 (上の例では、「余りが等しい」のみを表す部分) をグローバルに用意しておき、
パラメーターを与えることで具体的に必要な関数を作成する方法が考えられます。

部分適用関数 (Partial メソッド) を利用すれば、次のように実装できます。


/// <summary>指定された剰余を持つかどうかを判定します。</summary>
static readonly Func<int, int, int, bool> Mod = (remainder, divider, value) => value % divider == remainder;
/// <summary>累乗を求めます。</summary>
static readonly Func<int, int, int> Power = (index, value) => (int)Math.Pow(value, index);

static void Main()
{
    var result = Enumerable.Range(1, int.MaxValue)
        .Where(Mod.Partial(1).Partial(2))
        .Select(Power.Partial(2))
        .Take(10)
        .OrderBy(Convert.ToString)
        .ToArray();
}


このように、LINQ to Objects のメソッドの引数に渡す関数を作成する手段として、カリー化を応用できます。

バージョン情報
C# 3.0 以降
.NET Framework 3.5 以降

参照
カリー化 – Wikipedia
C#でカリー化
C#でカリー化と部分適用