メモ化により再帰を高速化する

概要

Groovyで再帰処理などを行うとき、メモ化すると高速になることがあります。
メモ化(Memoization)とはその名の通り、値をメモとして保存しておきメモが使えるときは計算せずにメモから値を取り出すことで不必要な計算を削減する手法です。
引数に対し出力が決まっている時(副作用がないとき)メモ化を行うことができます。
メモ化の原理については次を見てください。
そんなのどうでもいいからGroovyでメモ化使うにはどうすればいいか知りたいだけの人は下の方(Groovy標準でメモ化する)までジャンプしてください。

メモ化の原理

メモ化を自分で実装すると次のようになります。
例として2乗する処理をメモ化しています。
まず引数を2乗するクロージャsquareがあるとし、この処理を行うには1秒かかります。

def square = { n -> Thread.sleep(1000); n * n }

このクロージャをメモ化するためのmemoizeというクロージャを実装します。

def memoize = { f ->
    def memo = [:]
    def clos = { n ->
        if(memo[n] == null) memo[n] = f(n)
        memo[n]
    }
    return clos
}

これはfというクロージャを引数にとってclosというクロージャを返すクロージャです。
この中でやっている処理はmapを一つ定義して、クロージャが実行されたとき引数がmapの中にメモされていたらその値を返し、そうでなければ元のクロージャを実行するだけです。
memorizedされたsquareを作って、普通のsquareと比較してみました。

def memoized_square = memoize(square)

10.times{ println "$it : ${square(10)}" }
10.times{ println "$it : ${memoized_square(10)}" }

普通のsquareは一度実行されるたびに1秒止まるのですが、メモ化されたsquareは最初の1回は遅いままですが2度めから同じ値を引数にとった場合メモから参照されるのでほぼ瞬時に値が出力されます。
ただ、個々で一つ注意しなければいけないのはあくまでメモされた値だけ高速化されるので例えば引数が1~10まで変化しながら10回実行した時などは高速化されません。
同じ処理を使い回すような再帰処理で効果が発揮されることが多いです。ただし末尾再帰と違ってスタックがあふれる可能性は変わりません。
よく考えたら下のフィボナッチ数列のように何度も同じ値を参照するような場合だとスタックの使用率がかなり減るのでオーバーフローしにくくなります。

このようにメモ化をすれば便利になりますが毎回実装するのは大変ですよね。
しかしGroovyには標準でクロージャやメソッドをメモ化してくれる便利な機能があります。
それについて説明します。

Groovy標準でメモ化する

Groovy標準でメモ化する方法を説明します。
もう少し高度な処理として、定番のフィボナッチ数列を求めてみます。(再帰を使います)
まずは次のように普通に関数を定義します。

Integer fibonacci(Integer n){
    if(n==0)return 0
    if(n==1)return 1
    return fibonacci(n-1) + fibonacci(n-2)
}

def before = System.currentTimeMillis()

/* 1~30までのフィボナッチ数列を表示する */
(1..30).each{println fibonacci(it)}

def after = System.currentTimeMillis()

def time = (after-before)/1000.0
println "実行時間:${time}秒"

関数fibonacciは教科書通りのシンプルなものですね。(簡略化するため引数が負数の時の例外などは省いています)
しかしこの関数を実行すると、fibonacci(n-1)とfibonacci(n-2)でそれぞれnが1の時から再帰的にfibonacci関数が呼び出され指数的に時間がかかります。
私の環境では30まで計算するのに1秒以上かかり、40にすると途中から返事がなくなってしまいました。

そこでこの関数をメモ化します。
Groovyでメモ化する方法は2つあります。

Memoizedアノテーションをつけてメモ化する

メソッドにMemoizedアノテーションをつけることでメモ化することができます。
下のサンプルではGroovy Scriptとしてクラスを定義せずに直接関数を書いていますがクラスメソッドでも問題なくメモ化できます。
使用するためにはgroovy.transform.Memoizedをインポートします。

import groovy.transform.Memoized

@Memoized
Integer memoized_fibonacci(Integer n){
    if(n==0)return 0
    if(n==1)return 1
    return memoized_fibonacci(n-1) + memoized_fibonacci(n-2)
}

def before = System.currentTimeMillis()

/* 1~30までのフィボナッチ数列を表示する */
(1..30).each{println memoized_fibonacci(it)}

def after = System.currentTimeMillis()

def time = (after-before)/1000.0
println "実行時間:${time}秒"

クロージャをメモ化する

上記の例ではメソッドをメモ化しましたが、クロージャをメモ化するのはもっと簡単でmemoizeメソッドを呼べばメモ化されたクロージャが返ってきます。
次の例ではmemorized_fibonacciをクロージャとして定義しています。

def memoized_fibonacci
memoized_fibonacci = {Integer n ->
    if(n==0)return 0
    if(n==1)return 1
    return memoized_fibonacci(n-1) + memoized_fibonacci(n-2)
}.memoize()

def before = System.currentTimeMillis()

/* 1~30までのフィボナッチ数列を表示する */
(1..30).each{println memoized_fibonacci(it)}

def after = System.currentTimeMillis()

def time = (after-before)/1000.0
println "実行時間:${time}秒"

メソッドをこの方法でメモ化したい場合は、メソッドをクロージャに変換します。
例えばhogeオブジェクトにfugaメソッドがある場合次のように記述します。

def memoized_fuga = hoge.&fuga.memoize()

結果

メモ化した結果30まで数えるのに要した時間は0.02秒まで下がりました。
ものすごい差ですね。
この場合は結構特殊なケースですが、メモ化をうまく使えば無駄がなくなることがわかりました。

追記

余談ですけど最初memoize(メモイズ)のことをmemorize(メモライズ)だと間違っててそんなメソッドとかアノテーションないよって怒られたのでハマりました。