メモ化機構を切り離してみる

メモ化の概念的には、結局のところ、引数パターンに対する辞書があって、一度やった処理は記録して使いまわす。
前回のものから、メモ化部分を抽出するだけしてみると、

def tarai(x, y, z):
    if x <= y: return y
    return tarai(memorize(x - 1, y, z),
                 memorize(y - 1, z, x),
                 memorize(z - 1, x, y))

table = {}
def memorize(*args):
    global table
    if not args in table:
        table[args] = tarai(*args)
    return table[args]

で、汎用化しようとしたときに、memorize 中の tarai と、tarai 中の memorize が邪魔になるので、昔見た C# のコード(元ネタ第35回CLR/H) から、

class Program
{
    /* 多分こんなコードだった気がする */
    static void Main(string[] args)
    {
        memolized speed = memorize(new memolized(HeviyMethod));
        for (int i = 0; i < 20; i++)
            Console.WriteLine(speed(i));
        for (int i = 0; i < 20; i++)
            Console.WriteLine(speed(i));
    }

    delegate int memolized(int i);
    static memolized memorize(memolized target)
    {
        Dictionary<int,int> dic = new Dictionary<int,int>();
        return delegate(int i)
        {
            if (dic.ContainsKey(i))
                return dic[i];
            else
                return dic[i] = target(i);
        };
    }

    static int HeviyMethod(int s)
    {
        System.Threading.Thread.Sleep(1000);
        return s + 1;
    }
}

なるこれを参考に、して、実装してみる。
Python はクロージャがデフォだから、デリゲート宣言がいらないのはありがたい。

def tarai(x, y, z):
    if x <= y: return y
    return tarai(tarai(x - 1, y, z),
                 tarai(y - 1, z, x),
                 tarai(z - 1, x, y))

def memorize(function):
    dic = {}
    def func(*arg):
        if not args in dic:
            dic[args] = function(*args)
        return dic[args]
    return func

tarai = memorize(tarai)

もう一声、Pythonにはデコレータがあるので

def memorize(function):
    dic = {}
    def func(*arg):
        if not args in dic:
            dic[args] = function(*args)
        return dic[args]
    return func

@memorize
def tarai(x, y, z):
    if x <= y: return y
    return tarai(tarai(x - 1, y, z),
                 tarai(y - 1, z, x),
                 tarai(z - 1, x, y))

リベンジ完了。