D言語の標準ライブラリを読む read!(std.functional, 2)

前回に引き続き、今回もPhobosのstd.functionalを読んでいきます。今回は、 std.functional.memoizeを読みます。

std.functional.memoizeはその名前の通り、任意の関数をメモ化することができます。まずはじめに、簡単な例を見て行きましょう。


import std.functional, std.stdio;

int factImpl(int i){
    "*".write();
    return i == 0 ? 1 : i * fact(i - 1);
}

alias memoize!factImpl fact;

void main(){
    10.fact().writeln(); // ***********3628800
    10.fact().writeln(); // 3628800
    11.fact().writeln(); // *39916800
}

関数factImplをメモ化して、関数factを生成しています。とても簡単に関数をメモ化できていますね。

それでは、memoizeのソースコードを見てみましょう。


template memoize(alias fun, uint maxSize = uint.max)
{
    ReturnType!fun memoize(ParameterTypeTuple!fun args)
    {
        // 中略
    }
}

外枠を見ると、memoizeはテンプレートで、引数としてfunとmaxSizeを取るようです。テンプレート内部でmemoizeという関数が定義されています。関数memoizeの引数型は、funの引数型のタプルで、返値型はfunの返値型になっています。 memoizeは、funと同じように使える関数ならなければならないので、返値型や引数型は当然こうなっています。

次に、関数memoizeの内部を見てみましょう。


static ReturnType!fun[Tuple!(typeof(args))] memo; // (1)
auto t = tuple(args);
auto p = t in memo;
if (p) return *p; // (2)
static if (maxSize != uint.max) // (3)
{
    if (memo.length >= maxSize) memo = null;
}
auto r = fun(args); 
memo[t] = r; // (4)
return r;

(1)で関数の結果を格納する連想配列、memoを宣言しています。 memoのキーの型は、引数のTupleになっています。これによって、一気に関数funの結果をmemoに保存することができます。Tuple便利ですね。ちなみに、memoはstaticなので、関数が終了してもmemoは残り続けます。

(2)あたりで、memoに渡された引数をキーとした値があるかどうかチェックし、あったらその値を返しています。

(3)では、memoの最大数を設定した場合の処理を行なっています。

(4)あたりで、funを実際に実行、その結果をmemoに保存し値を返しています。

このように、std.functional.memoizeは、staticな連想配列に値を保存しておくことによって、渡された関数をメモ化しています。とても面白いですね。