メモ化で処理を爆速化: Pythonのfunctools.lru_cacheについて解説

# basic_lru_cache.py
from functools import lru_cache
import time

@lru_cache(maxsize=128)  # キャッシュの上限を128件に設定
def slow_square(n: int) -> int:
    """重い処理を模したn*n"""
    time.sleep(0.5)  # 500msかかる重い計算の代わり
    return n * n

def main():
    start = time.perf_counter()
    print("1回目:", slow_square(12))
    t1 = time.perf_counter() - start

    start = time.perf_counter()
    print("2回目:", slow_square(12))  # 同じ引数なのでキャッシュを使用
    t2 = time.perf_counter() - start

    print(f"1回目の所要時間: {t1:.3f}s")
    print(f"2回目の所要時間: {t2:.6f}s (キャッシュ)")

if __name__ == "__main__":
    main()

# fib_lru_cache.py
from functools import lru_cache
import time

def fib_naive(n: int) -> int:
    """メモ化なしの再帰(指数時間)"""
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

@lru_cache(maxsize=None)  # 無制限キャッシュ(後述の注意も参照)
def fib_cached(n: int) -> int:
    """メモ化ありの再帰(線形時間)"""
    if n < 2:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

def timed(label, func, n):
    start = time.perf_counter()
    result = func(n)
    dt = time.perf_counter() - start
    print(f"{label}: fib({n}) = {result} / {dt:.3f}s")

if __name__ == "__main__":
    N = 35
    timed("naive", fib_naive, N)
    timed("cached", fib_cached, N)
    # ヒット率を確認
    print("cache_info:", fib_cached.cache_info())

# hashable_args.py
from functools import lru_cache

@lru_cache(None)
def sum_tuple(xs: tuple[int, ...]) -> int:
    """タプルを受け取り合計を計算(キャッシュ可能)"""
    return sum(xs)

def sum_list(xs: list[int]) -> int:
    """外側でタプル化してからキャッシュ関数へ委譲"""
    # list -> tuple に正規化
    return sum_tuple(tuple(xs))

@lru_cache(None)
def sum_dict_items(items: frozenset[tuple[str, int]]) -> int:
    """(キー, 値)の集合をfrozensetで受け取ると順不同でも同じキー扱いにできる"""
    return sum(value for _key, value in items)

def sum_dict(d: dict[str, int]) -> int:
    # dict -> frozenset(dict.items()) に正規化
    return sum_dict_items(frozenset(d.items()))

if __name__ == "__main__":
    print(sum_list([1, 2, 3]))
    print(sum_list([1, 2, 3]))  # キャッシュ
    print(sum_dict({"a": 1, "b": 2}))
    print(sum_dict({"b": 2, "a": 1}))  # 順不同でも同じキー扱い

# maxsize_demo.py
from functools import lru_cache

@lru_cache(maxsize=2)  # 最新2件だけ保持
def compute(n: int) -> int:
    print(f"compute({n}) 実行")  # ミス時のみ表示される
    return n * 10

if __name__ == "__main__":
    compute(1)  # miss
    compute(2)  # miss
    compute(1)  # hit
    compute(3)  # miss -> 2がLRUとして追い出される可能性
    compute(2)  # miss (追い出されていれば再計算)

# typed_demo.py
from functools import lru_cache

@lru_cache(maxsize=None, typed=False)
def f_default(x):
    print("f_default 計算:", type(x).__name__)
    return 42

@lru_cache(maxsize=None, typed=True)
def f_typed(x):
    print("f_typed 計算:", type(x).__name__)
    return 42

if __name__ == "__main__":
    f_default(1)   # miss
    f_default(1.0) # hit(同一キー扱い)

    f_typed(1)     # miss
    f_typed(1.0)   # miss(型が違うので別キー)

# cache_info_demo.py
from functools import lru_cache

@lru_cache(maxsize=3)
def f(n):
    return n * n

if __name__ == "__main__":
    for x in [1, 2, 3, 1, 2, 4, 1]:
        f(x)
    print(f.cache_info())

# cache_clear_demo.py
from functools import lru_cache

calls = 0

@lru_cache(None)
def heavy(n):
    global calls
    calls += 1
    return n * 2

if __name__ == "__main__":
    heavy(10); heavy(10)  # 2回目はヒット
    print("before clear:", heavy.cache_info(), "calls:", calls)
    heavy.cache_clear()
    heavy(10)             # ミスして再計算
    print("after  clear:", heavy.cache_info(), "calls:", calls)

# normalize_set.py
from functools import lru_cache

@lru_cache(None)
def score(categories: frozenset[str]) -> int:
    # 順序に意味がない集合として扱う
    return sum(len(c) for c in categories)

def score_for_list(categories_list: list[str]) -> int:
    return score(frozenset(categories_list))

if __name__ == "__main__":
    print(score_for_list(["a", "bb"]))
    print(score_for_list(["bb", "a"]))  # キャッシュヒット(順序違いでも同じ)