読者です 読者をやめる 読者になる 読者になる

動的計画法入門

動的計画法、いわゆるDPについて少し勉強したのでまとめました。ここではフィボナッチ数列を例に説明していきます。

愚直なフィボナッチ数列の実装

フィボナッチ数列は次のように定義されます。
F_0=0\\F_1=1\\F_{n+2}=F_{n}+F_{n+1}
これをそのままプログラムにするとこうなります。

def f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return f(n - 1) + f(n - 2)

print(f(6)) # 8

問題なく動きます。このコードでもnが小さい場合特に問題になりません。しかしnが大きくなるにつれて急激に処理に時間がかかるようになります。どのように計算されているのか出力してみましょう。次のようなコードで実験してみました。

def f(n, depth):
    print("{}{}".format(" " * depth, n))
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return f(n - 1, depth + 1) + f(n - 2, depth + 1)

f(6, 0)

出力結果。

6
 5
  4
   3
    2
     1
     0
    1
   2
    1
    0
  3
   2
    1
    0
   1
 4
  3
   2
    1
    0
   1
  2
   1
   0

f(6)からf(5)とf(4)が呼ばれ、f(5)からf(4)とf(3)が呼ばれ…と繰り返し、最終的にf(1)もしくはf(0)になるまで呼び出されていることがわかります。ここで注目して欲しいことは重複が複数あるところです。例えばf(2)は5回も呼ばれれています。このような部分的な計算結果を保存して計算量を減らすことをメモ化と呼び、メモ化は動的計画法の一種です。

計算結果を保存する

cacheという辞書を作って渡されたnがcacheに登録されているか調べ、登録されている場合は辞書の値を返し、登録されていない場合は計算するようにしました。

cache = {0:0, 1:1}
def f_cache(n):    
    global cache
    if n not in cache:
        cache[n] = f_cache(n - 1) + f_cache(n - 2)
    return cache[n]

print(f_cache(6)) # 8

fと同じ計算結果になりました。fと同じように計算の過程を出力して見ましょう。

cache = {0:0, 1:1}
def f_cache(n, depth):
    print("{}{}".format(" " * depth, n))
    global cache
    if n not in cache:
        cache[n] = f_cache(n - 1, depth + 1) + f_cache(n - 2, depth + 1)
    return cache[n]

f_cache(6, 0)

出力結果。

6
 5
  4
   3
    2
     1
     0
    1
   2
  3
 4

すっきりしました。一度計算したnはcacheを使用していることがわかります。

パフォーマンス

fとf_cacheにnを渡した際の、次のようなコードで処理時間を計測しました。

s=time.time()
print(f(n))
print(time.time() - s)
s=time.time()
print(f_cache(n))
print(time.time() - s)

n=25

75025
0.09860038757324219
75025
0.0

n=30

832040
1.1280641555786133
832040
0.0

n=35

9227465
12.561718463897705
9227465
0.0

メモ化をしていないfは爆発的に処理時間が増える一方、メモ化をしたf_cacheは一瞬で処理できていることがわかります。

まとめ

たいした処理でなくても愚直な実装の場合あっという間に計算不可能になってしまいます。気をつけたいですね。