C#でメモ化を実装してみた

C#でデコレーター風味でメモ化を実装してみました。
デコレーターをC#で実装しようとやっていた際に思いついたのでここに置いておきます。

メモ化とは

重い計算をする際によく用いられます。
同じ引数だと同様の結果を返すような場合、二回目も三回目も同様に計算を行うのは処理時間の都合上非常に無駄です。
なので、引数と戻り値のリストを作成しておいてリストにある引数が渡された場合計算をせずにリストから結果を渡すというものです。

実装方法

Dictionaryで計算結果を保持して引数が存在するかの比較を行います。
今回は以下のように実装しました。
計算を行うメソッドはこのように記述しました。

public long Decorate_square (long x) {
    return x * x;
}

今回は簡単に二乗を行うメソッドです。
そして実行を代行するメソッドはこちらです。

public long square (long sx2) {
    Func<long, long> f = Decorate_square;
    Decorator.memo<long, long> memo = new Decorator.memo<long, long> ();
    return memo.Invoke (data, f, sx2);
}

Funcでメソッドを変数にいれてメモ化のメソッドの型を指定してメモ化のメソッド経由で実行します。
そして、メモ化を行うメソッドはこのように実装しました。

using System;
using System.Collections.Generic;
using System.Reflection;
public class Decorator {
    public Dictionary<object,object> data = new System.Collections.Generic.Dictionary<object,object>();
    public class memo<arg01, ans> {
        public ans Invoke (Dictionary<object,object> data, Func<arg01, ans> f, object x) {
            if (data.ContainsKey((arg01)x)) {
                Console.WriteLine ("-O-");
                return (ans) data[(arg01)x];
            } else {
                Console.WriteLine ("-X-");
                ans res = (ans) (object) f ((arg01) x);
                data[(arg01)x] = res;
                return res;
            }
        }
    }
}

これらを書くのは面倒では。。。

はい、その通りです。
そこでRoslynのVisualStudio拡張機能の修正機能です。
私の別の記事で書きましたがこれはソースコード自体を自動で書き換えることができます。
なので、[memo]などと記述した際に自動でデコレーターメソッドを記述できるようになると非常に良いです。

全コード

generic.cs

using System;
using System.Collections.Generic;
using System.Reflection;

public class deco2 : Decorator {
    public long square (long sx2) {
        Func<long, long> f = Decorate_square;
        Decorator.memo<long, long> memo = new Decorator.memo<long, long> ();
        return memo.Invoke (data, f, sx2);
    }

    public long Decorate_square (long x) {
        return x * x;
    }
}

memo_decorator.cs

using System;
using System.Collections.Generic;
using System.Reflection;

public class Decorator {
    public Dictionary<object,object> data = new System.Collections.Generic.Dictionary<object,object>();
    public class memo<arg01, ans> {
        public ans Invoke (Dictionary<object,object> data, Func<arg01, ans> f, object x) {
            if (data.ContainsKey((arg01)x)) {
                Console.WriteLine ("-O-");
                return (ans) data[(arg01)x];
            } else {
                Console.WriteLine ("-X-");
                ans res = (ans) (object) f ((arg01) x);
                data[(arg01)x] = res;
                return res;
            }
        }
    }
}

以下は実行部分です

Program.cs

namespace twice_arg_memo {
    class Program {
        static void Main (string[] args) {
            deco2 d = new deco2 ();
            Console.WriteLine (d.square (2));
            Console.WriteLine (d.square (2));
            Console.WriteLine (d.square (3));
            Console.WriteLine (d.square (4));
            Environment.Exit (0);
        }
    }
}