python 漸化式

Question

漸化式を用いて数字を出力したいのですが自分で考えたコードだといちいち答えを出すのに何回も計算しなければなりません。
（例）get_total_xに5を入れるとしたら1/2.*get_total_x(n-1)+1に代入され
get_total_x(5-1)となりget_total_x(4)も計算しなければなりません。その次は3,2,1と計算されていきます。
その場合計算結果としては合っているのですが計算が遅くなってしまうのでスムーズに
一つ前の計算結果を用いて答えを出力したいのですがどのように変更したらよいのでしょうか。

def get_total_x(n):
if n == 0:
return 0
else:
return 1/2.*get_total_x(n-1)+1

def get_total_y(n):
if n == 0:
return 0
else:
return 1/3.*get_total_y(n-1)+2

def get_total_z(n):
if n == 0:
return 0
else:
return 1/4.*get_total_z(n-1)+3

for i in range(0,50):
print(str(get_total_x(i))+","+str(get_total_y(i))+","+str(get_total_z(i)))

Answer 1

まず、提示コードでは計算時間≒get_total_xの呼び出し回数はn+1回で、漸化式を利用している以上、これより減らすことはできません。
しかしたとえばreturn 1/4.*get_total_x(n-1) + 1/4*get_total_x(n-1) + 1と書いた場合は、nが大きくなるにつれ計算時間は急速に増えます。
実際にまずn=20でやってみてください。さらにn=50だと計算終わらないと思います。

計算時間を抑えるには、一般的にはメモ化という手法をとります。
これは、計算済みの結果をどこかにメモしておき、すでに計算済みならメモしたものを返すことにより同じ計算をしないようにする手法です。

今回の例だと以下のようなコードになります。

def get_total_x(n,memo):

    # すでに計算済み
    if n in memo:
        return memo[n]

    ret = 0
    if n == 0:
        ret = 0
    else:
        ret = 1/4.*get_total_x(n-1,memo)+1/4.*get_total_x(n-1,memo)+1

    memo[n] = ret # メモに記録
    return ret

memo = {} # メモとして辞書を利用
print(get_total_x(50,memo)) # 1.9999999999999982

ちなみにこのメモ化を自動でやってくれるのがLouiS0616さんの回答にあるfunctools.lru_cacheです。

Answer 2

Python3.2以降であれば、functools.lru_cacheが使えます。
Python2.7のサポートは2020年に終了されますので、乗り換えを強く推奨します。

どうしても古いバージョンを使いたいなら、サードパーティライブラリを利用すると楽です。
StackOverflow - memoization library for python 2.7
GitHub - repoze/repoze.lru

コードの書き方について

teratailには、コードを見やすく表示する機能があります。
質問編集画面を開き、コードを選択した状態で<code>ボタンを押してください。

特にPythonの場合、インデントが崩れるとコードの意味が変わってしまいます。

Answer 3

... 一つ前の計算結果を用いて答えを出力したい ...

メソッドに prev として、一つ前の計算結果を指定できるように書き換えてみました。
さらに get_total_x, get_total_y, get_total_z を別関数でなく、
一つの関数 get_total にまとめてみました。

xyz.py

def get_total(n, k, prev):
    if n == 0:
        return 0
    if prev == None:
        prev = get_total(n - 1, k, None)
    return 1.0 / (k + 1) * prev + k


p1 = None
p2 = None
p3 = None
for i in range(0, 10):
    p1 = get_total(i, 1, p1)
    p2 = get_total(i, 2, p2)
    p3 = get_total(i, 3, p3)
    print(str(i), ": ", p1, ",", p2, ",", p3)

実行例
前半は質問文にあるコードを 0..10 までループにして実行してます。
後半は上のコードを実行してます。
出力書式は異なってなすが、数値は同じになっています。

Comments

[basketballpyth]

どのように実行されていくか前半のコードの詳しい解説お願いしてもよろしいでしょうか？

Answer 4

（例）get_total_xに5を入れるとしたら1/2.*get_total_x(n-1)+1に代入され

get_total_x(5-1)となりget_total_x(4)も計算しなければなりません。その次は3,2,1と計算されていきます。

漸化式ってそういうものですよね？

一つ前の計算結果を用いて答えを出力したいのですがどのように変更したらよいのでしょうか。

何番目はこの式で求まるという式を導いて、それに当てはめればよいでしょう。
等差数列とか等比数列とかそんな感じですね。