Closure クラスの API を使ってみる (7) ：メモ化 memoize()

今回はクロージャのメモ化 (memoize)。　カリー化、トランポリン同様、メモ化も関数型言語では大抵実装されている機能ですね。　メモ化すると「キャッシュするバージョンのクロージャ」が生成されます。

参考

メモ化関連メソッド

Closure クラスに定義されているメモ化関連のメソッドには以下のようなものがあります：

    Closure<V> memoize()
    Closure<V> memoizeAtMost(int maxCacheSize)
    Closure<V> memoizeAtLeast(int protectedCacheSize)
    Closure<V> memoizeBetween(int protectedCacheSize, int maxCacheSize)

返される Closure オブジェクトがメモ化された Closure オブジェクト
memoizeAtMost() はキャッシュサイズの最大値を指定
memoizeAtLeast() は GC から保護されるキャッシュサイズを指定
memoizeBetween() は両方を指定

です。

サンプル・コード

サンプルは memoize() と memoizeAtMost() のみで。

まずはスケルトンコード

r = new Random(1L).&nextInt

10.times{
    // 適当に整数を作って、5つの乱数を持つ行を10行表示
    def n = (it % 5)*10 + 10
    printRandomList(n)
}

def printRandomList(int n){
    // r を使って (0..<n) の間の乱数を5つ表示
    print "$n :"; 5.times{ print(' '+r(n)) }; println()
}

実行すると以下のような出力が得られます（コンマの右の整数は実行毎に変わります）：

10 : 5 8 7 3 4
20 : 4 14 6 18 8
30 : 19 13 7 3 12
40 : 34 32 22 36 29
50 : 26 32 10 49 24
10 : 9 8 3 7 2
20 : 5 14 0 6 3
30 : 15 9 0 15 14
40 : 15 20 37 17 37
50 : 42 20 38 0 7

左の数字未満（0以上）の整数がランダムに5つ右に表示されます。

memoize() メソッドによるメモ化

では、メモ化したクロージャの使用例。　コードとしては単に r 変数をメモ化したものに変えただけです：

r = new Random(1L).&nextInt
r = r.memoize()    // メモ化

10.times{
    def n = (it % 5)*10 + 10
    printRandomList(n)
}

def printRandomList(int n){
    print "$n :"; 5.times{ print(' '+r(n)) }; println()
}

これを実行すると以下のようになります：

10 : 5 5 5 5 5
20 : 8 8 8 8 8
30 : 7 7 7 7 7
40 : 33 33 33 33 33
50 : 4 4 4 4 4
10 : 5 5 5 5 5
20 : 8 8 8 8 8
30 : 7 7 7 7 7
40 : 33 33 33 33 33
50 : 4 4 4 4 4

「メモ化」は引数に対して計算結果をキャッシュするんですよね。　上記の例では、「10」を引数にすれば常に「5」が返されています。　1行目、6行目（「10 : 」で始まる行）ではすべて「5」が表示されてますね。　引数が別の、例えば「20」とかの場合は「5」ではなく「8」になっています。

memoizeAtMost() メソッドその1

次は memoizeAtMost() メソッドの使用例。

r = new Random(1L).&nextInt
r = r.memoizeAtMost(5)    // キャッシュ最大値5

10.times{
    def n = (it % 5)*10 + 10
    printRandomList(n)
}

def printRandomList(int n){
    print "$n :"; 5.times{ print(' '+r(n)) }; println()
}

実行すると

10 : 5 5 5 5 5
20 : 8 8 8 8 8
30 : 7 7 7 7 7
40 : 33 33 33 33 33
50 : 4 4 4 4 4
10 : 5 5 5 5 5
20 : 8 8 8 8 8
30 : 7 7 7 7 7
40 : 33 33 33 33 33
50 : 4 4 4 4 4

今の場合は memoize() の場合と変わりませんね。

memoizeAtMost() メソッドその2

次は同じ memoizeAtMost() を、引数を変えて呼んでみます：

r = new Random(1L).&nextInt
r = r.memoizeAtMost(3)    // キャッシュ最大値3

10.times{
    def n = (it % 5)*10 + 10
    printRandomList(n)
}

def printRandomList(int n){
    print "$n :"; 5.times{ print(' '+r(n)) }; println()
}

実行結果は以下の通り（各行の // 以降は追加）：

10 : 5 5 5 5 5         // 実行後のキャッシュ [10:5]
20 : 8 8 8 8 8         // [10:5, 20:8]
30 : 7 7 7 7 7         // [10:5, 20:8, 30:7]
40 : 33 33 33 33 33    // [20:8, 30:7, 40:33]
50 : 4 4 4 4 4          // [30:7, 40:33, 50:4]
10 : 4 4 4 4 4         // [40:33, 50:4, 10:4]
20 : 14 14 14 14 14
30 : 16 16 16 16 16
40 : 18 18 18 18 18
50 : 48 48 48 48 48

今度の結果はさっきのとちょっと違ってきてます。　同じ行の間では同じ整数が表示されますが（1行目の「10」の場合は「5」とか）、別の行では別の整数が表示されています（6行目の「10」では「4」）。　これはキャッシュの最大値を3に設定しているので、同じ引数の呼び出しでも2度目（「10」の場合6行目）ではキャッシュが廃棄されているからですね。

コード書いてて思ったんですが、キャッシュのテストとか書くときって乱数使うと良さそう。