関数のメモ化

cache について説明するまえに、関数のメモ化について説明します。例えば、次のような再帰関数を考えてみましょう。

def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

print(fib(5), fib(6), fib(7))  # 5, 8, 13

この関数で fib(20) を呼ぶと、fib(19) + fib(18) と再帰し、さらに fib(19) は fib(18) + fib(17) と再帰するため、fib(18) は少なくとも2回呼ばれることがわかります。同様に fib(11) は34回¹呼ばれ、その全てでfib(11) を計算するためのさらなる再帰が行われます。

しかし、fib 関数は引数のみによって返り値が定まるため、一度 fib(11) が 89 であることがわかれば再計算する必要はありません。このように、計算済みの結果を保持することを関数のメモ化といいます。

メモ化の実装例は次の通りです。

fib_memo = {}
def fib(n):
    if n in fib_memo:
        return fib_memo[n]
    if n <= 0:
        return 0
    if n == 1:
        return 1
    fib_n = fib(n-1) + fib(n-2)
    fib_memo[n] = fib_n
    return fib_n

print(fib(5), fib(6), fib(7))  # 5, 8, 13

functools.cache を用いたメモ化

関数のメモ化は自分で実装することができますが、functools モジュールの cache を使うことでより簡単に実装することができます。

from functools import cache

@cache
def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

print(fib(5), fib(6), fib(7))  # 5, 8, 13

cmp_to_key

3.06 いろいろなソート でも既に説明しましたがおさらいしましょう。

sort メソッド及び sorted 関数にはキー関数を与えることができ、キー関数が返す値の順にソートすることができます。

A = [-3, 1, 4, 2, -5]

print(sorted(A))  # [-5, -3, 1, 2, 4]
print(sorted(A, key=abs))  # [1, 2, -3, 4, -5]

この方法は直感的には「各要素に点数をつけて、その点数の順に並べる」といえます。

一方、「2つの要素を比較して、どちらを前にするか判定する」を繰り返すことでもソートを行うことができます²。キー関数と違い、比較関数を受け取ってその順にソートする機能は sort, sorted にはありませんが、cmp_to_key でラップすることで、キー関数と同様に渡すことができるようになります。

実装例

def compare_by_abs(x, y):
    # 絶対値が小さい方を前とするソートのための比較関数
    # |x| と |y| を比較し
    # |x| の方が小さければ負の値
    # |y| の方が小さければ正の値
    # |x| と |y| が等しければ 0 を返す
    if abs(x) < abs(y):
        return -1
    if abs(x) > abs(y):
        return 1
    return 0

from functools import cmp_to_key

A = [-3, 1, 4, 2, -5]

print(sorted(A))  # [-5, -3, 1, 2, 4]
print(sorted(A, key=cmp_to_key(compare_by_abs)))  # [1, 2, -3, 4, -5]

この例では単に key=abs としても同様の結果を得ることができるためありがたみは薄いですが、3.06 節により実践的な例があるため、そちらを再度確認してください。

問題

リンク先の問題を解いてください。

EX23.再帰関数1

前のページ | 次のページ