メモ化（memoize）は、Project Eulerで何問かに1問必ず使う手法なので、絶対に覚えましょう。
Project EulerのProblem 151を考えます。意味が分かりにくい問題ですが、分かれば簡単です。まず最初にA1の紙が1枚封筒に入った状態を考えます。この状態を
(1, 0, 0, 0, 0)
と表します。各項は各サイズの紙の枚数です。次にA1の紙を1枚取り出して、切ってA2〜A5を1枚ずつ封筒に戻します。この状態は、
(0, 1, 1, 1, 1)
と表します。この状態からどの大きさの紙を取り出す確率も1/4です。例えばA3の紙を取り出して切ってA5の紙を使うと、
(0, 1, 0, 2, 2)
となります。このような状態の期待値に確率を掛けて足し合わせれば、期待値になります。最後に紙が無くなったときは(0, 0, 0, 0, 0)で、このときは封筒に1枚残っている状態がある回数の期待値は0です。簡単に再帰で期待値を求めることができます。
from itertools import izip, count
N = 5
def next(s, k):
return s[:k] + (s[k] - 1,) + tuple(n + 1 for n in s[k+1:])
def E(s):
num_papers = sum(s)
if num_papers == 0:
return 0.0
return (1 if num_papers == 1 else 0) \
+ sum(n * E(next(s, k)) / num_papers
for k, n in izip(count(), s) if n > 0)
print "%.6f" % (E((1,) + (0,) * (N - 1)) - 2)これでも十分に速いのですが、A5をA6にするともう答えがしばらく返ってこなくなります。どうすればいいのでしょうか。
例えばA2を取り出したあとA3を取り出したのと逆の順番のとは同じ状態になります。このように同じ状態が何度も出てくるのです。次のように何度同じ状態になるか調べてみましょう。
def add(dic, key): if key in dic: dic[key] += 1 else: dic[key] = 1 def E(s): add(counter, s); # count # ... counter = { } print "%.6f" % (E((1,) + (0,) * (N - 1)) - 2) for s, n in sorted(counter.iteritems(), key = lambda x: -x[1]): print s, n
こうすると、
(0, 0, 0, 0, 1) 40040 (0, 0, 0, 0, 0) 40040 (0, 0, 0, 0, 2) 28028 (0, 0, 0, 0, 3) 16016 (0, 0, 0, 1, 0) 12012 (0, 0, 0, 1, 1) 12012 (0, 0, 0, 1, 2) 8316 (0, 0, 0, 0, 4) 7700 ...
右の数が左の状態が現れた回数です。
E(s)はsが同じなら必ず同じ値を返します。なので、同じ計算を何度も繰り返し行っていることになります。ムダですね。こういうのは一度計算したらそれを記憶しておけばよいです。それがメモ化です。Pythonでは辞書を使って次のように書きます。
def E(s): if s in memo: return memo[s] # eを計算 memo[s] = e return e memo = { } print "%.6f" % (E((1,) + (0,) * (N - 1)) - 2)
関数に入ったら、まず辞書に計算結果が登録されていないか調べて、あればその値を使い、なければ計算してその結果を登録して返します。
このようにすることによって多くの場合圧倒的に高速化できます。再帰関数の引数が複数の場合はタプルにして辞書に登録すればよいでしょう。E(x, y)なら、(x, y)をキーにします。
