Python 3: Deep Dive (Part 1 - Functional): メモ化とパラメータ化デコレータ (セクション7-6/11)
メモ化は、以前に計算した値をキャッシュすることで再計算を避け、効率的にするテクニックです。
関数デコレータを使ってメモ化を実装することで、再帰的な関数のパフォーマンスを大幅に向上させることができます。
`functools`の`lru_cache`デコレータを使うと、キャッシュのサイズ管理や効率的なメモ化が可能になります。
Pythonのスコープ、クロージャ、およびデコレータを探求する中で、コードの効率を大幅に最適化できる重要なポイントに到達しました。Python 3: Deep Dive (Part 1 - Functional) の第7章のレッスン110から112では、メモ化のためのデコレータの適用とパラメータ化デコレータの作成について詳しく説明しています。この記事では、これらの高度な概念を紹介し、Pythonコードの効率と柔軟性をどのように向上させるかを実例を交えながら解説します。
メモ化の理解
メモ化（Memoization）は、以前に計算した結果をキャッシュ（保存）することで、関数の実行を高速化する技法です。関数が同じ引数で再び呼び出された場合、再計算する代わりにキャッシュされた結果を返します。これは特にフィボナッチ数列のような再帰的な関数において、同じ計算が繰り返される場合に有用です。
再帰的フィボナッチの非効率性
次のフィボナッチ数列の再帰的実装を考えてみましょう：
def fib(n):
print(f"Calculating fib({n})")
if n < 3:
return 1
else:
return fib(n - 1) + fib(n - 2)`fib(6)` を呼び出すと、同じフィボナッチ数が何度も計算されます：
Calculating fib(6)
Calculating fib(5)
Calculating fib(4)
Calculating fib(3)
Calculating fib(2)
Calculating fib(1)
Calculating fib(2)
Calculating fib(3)
Calculating fib(2)
Calculating fib(1)
Calculating fib(4)
Calculating fib(3)
Calculating fib(2)
Calculating fib(1)
Calculating fib(2)この冗長な計算は時間計算量を指数関数的に増加させ、大きな入力に対して非効率的になります。
クラスを使用したメモ化の実装
これを最適化するために、計算済みのフィボナッチ数をキャッシュするクラスを使います：
class Fib:
def __init__(self):
self.cache = {1: 1, 2: 1}
def fib(self, n):
if n not in self.cache:
print(f"Calculating fib({n})")
self.cache[n] = self.fib(n - 1) + self.fib(n - 2)
return self.cache[n]使用例:
f = Fib()
print(f.fib(6))出力:
Calculating fib(6)
Calculating fib(5)
Calculating fib(4)
Calculating fib(3)
8`self.cache` に計算結果を保存することで、冗長な計算を回避します。
クロージャを使ったメモ化
クロージャを使用することで、キャッシュを関数内部に閉じ込めることができます：
def fib():
cache = {1: 1, 2: 1}
def calc_fib(n):
if n not in cache:
print(f"Calculating fib({n})")
cache[n] = calc_fib(n - 1) + calc_fib(n - 2)
return cache[n]
return calc_fib使用例:
f = fib()
print(f(6))出力:
Calculating fib(6)
Calculating fib(5)
Calculating fib(4)
Calculating fib(3)
8`cache` 辞書は `fib` 関数内に閉じ込められ、内部関数 `calc_fib` がそれを使って計算結果を保存および取得します。
メモ化デコレータの作成
メモ化を一般化するためのデコレータを作成します：
from functools import wraps
def memoize(fn):
cache = dict()
@wraps(fn)
def inner(*args):
if args not in cache:
cache[args] = fn(*args)
return cache[args]
return innerデコレータの適用:
@memoize
def fib(n):
print(f"Calculating fib({n})")
if n < 3:
return 1
else:
return fib(n - 1) + fib(n - 2)使用例:
print(fib(6))出力:
Calculating fib(6)
Calculating fib(5)
Calculating fib(4)
Calculating fib(3)
Calculating fib(2)
Calculating fib(1)
8デコレータ `memoize` によって、引数に基づく結果がキャッシュされます。このデコレータは、ハッシュ可能な引数を持つ任意の関数に適用可能です。
単純なメモ化デコレータの制限
メモ化デコレータは効率を向上させますが、いくつかの欠点があります：
無制限のキャッシュサイズ: キャッシュは無制限に増加し、メモリを大量に消費する可能性があります。
キーワード引数の対応不可: このデコレータは位置引数のみを扱います。
ハッシュ可能な引数に限定: 引数は辞書のキーとして使用できるハッシュ可能なものでなければなりません。
functools.lru_cacheの活用
これらの制限を克服するために、Pythonには組み込みのメモ化ツールである `functools.lru_cache` デコレータが用意されています。
LRUキャッシュの理解
LRU（Least Recently Used）キャッシュは、キャッシュが最大サイズに達したときに最も長い間使われていない項目を削除します。これにより、メモリ使用量を管理しつつメモ化の利点を享受できます。
関数の最適化へのlru_cacheの適用
まず、メモ化なしの非効率なフィボナッチ関数を見てみましょう：
def fib_no_memo(n):
if n < 3:
return 1
else:
return fib_no_memo(n - 1) + fib_no_memo(n - 2)関数のタイミング計測:
from time import perf_counter
start = perf_counter()
result = fib_no_memo(35)
elapsed = perf_counter() - start
print(f"result={result}, elapsed: {elapsed:.6f
}s")出力:
result=9227465, elapsed: 0.548423s次に、`lru_cache` を使用してみましょう：
from functools import lru_cache
@lru_cache(maxsize=128)
def fib_memo(n):
if n < 3:
return 1
else:
return fib_memo(n - 1) + fib_memo(n - 2)メモ化された関数のタイミング計測:
start = perf_counter()
result = fib_memo(35)
elapsed = perf_counter() - start
print(f"result={result}, elapsed: {elapsed:.6f}s")出力:
result=9227465, elapsed: 0.000002s説明:
劇的な高速化: メモ化されたバージョンは非常に高速です。
キャッシュサイズの制御: `maxsize` パラメータにより、キャッシュを128エントリに制限します。
自動キャッシュ管理: `lru_cache` はキャッシュとキャッシュ無効化を効率的に処理します。
パラメータ化デコレータ
デコレータパラメータの必要性
最初の `timed` デコレータにはハードコーディングされた繰り返し回数が含まれていました：
def timed(fn):
from time import perf_counter
def inner(*args, **kwargs):
total_elapsed = 0
for _ in range(10): # ハードコーディングされた値
start = perf_counter()
result = fn(*args, **kwargs)
total_elapsed += perf_counter() - start
avg_elapsed = total_elapsed / 10
print(f"Avg Run time: {avg_elapsed:.6f}s")
return result
return innerこれをより柔軟にするためには、繰り返し回数をパラメータ化する必要があります。
パラメータを持つデコレータの作成
デコレータをパラメータ化するためには、デコレータファクトリを使用します。これはデコレータを返す関数です：
def timed(reps=1):
def decorator(fn):
from time import perf_counter
from functools import wraps
@wraps(fn)
def inner(*args, **kwargs):
total_elapsed = 0
for _ in range(reps):
start = perf_counter()
result = fn(*args, **kwargs)
total_elapsed += perf_counter() - start
avg_elapsed = total_elapsed / reps
print(f"Avg Run time: {avg_elapsed:.6f}s over {reps} reps")
return result
return inner
return decorator説明:
デコレータファクトリ (`timed`): `reps` を引数として取り、実際のデコレータを返します。
デコレータ (`decorator`): デコレートされる関数 `fn` を受け取ります。
内部関数 (`inner`): `reps` 回の繰り返しでタイミングを計測します。
デコレータファクトリの理解
デコレータファクトリ自体はデコレータではなく、呼び出されるとデコレータを返します。これにより、デコレータにパラメータを渡すことが可能になります。
使用例:
@timed(reps=5)
def fib(n):
if n < 3:
return 1
else:
return fib(n - 1) + fib(n - 2)`fib(10)` を呼び出すと、関数は5回実行され、平均実行時間が出力されます。
timedデコレータの洗練
`timed` デコレータを改良して、任意の繰り返し回数を処理し、元の関数のメタデータを保持するようにしましょう：
def timed(reps=1):
def decorator(fn):
from time import perf_counter
from functools import wraps
@wraps(fn)
def inner(*args, **kwargs):
total_elapsed = 0
for _ in range(reps):
start = perf_counter()
result = fn(*args, **kwargs)
total_elapsed += perf_counter() - start
avg_elapsed = total_elapsed / reps
print(f"{fn.__name__} took {avg_elapsed:.6f}s over {reps} reps")
return result
return inner
return decoratorメタデータの保持:
`@wraps(fn)` を使用することで、デコレートされた関数は元の名前、ドキュメント文字列、およびアノテーションを保持します。
使用例:
@timed(reps=3)
def compute_fibonacci(n):
if n < 3:
return 1
else:
return compute_fibonacci(n - 1) + compute_fibonacci(n - 2)
compute_fibonacci(10)出力:
compute_fibonacci took 0.000005s over 3 reps全体のまとめ
メモ化とパラメータ化デコレータを組み合わせることで、非常に効率的かつ柔軟な関数を作成できます。
メモ化とタイミングの測定を組み合わせたフィボナッチ関数:
from functools import lru_cache
@lru_cache(maxsize=128)
@timed(reps=5)
def fib(n):
if n < 3:
return 1
else:
return fib(n - 1) + fib(n - 2)使用例:
print(fib(35))出力:
fib took 0.000002s over 5 reps
9227465説明:
デコレータの積み重ね: `lru_cache` は関数をメモ化し、`timed` は5回の繰り返しで平均実行時間を測定します。
順序の重要性: デコレータは下から上に適用されます。`timed` は `fib` をラップし、その後 `lru_cache` が結果をラップします。
結論
デコレータはPythonの強力な機能であり、コードの効率と可読性を大幅に向上させることができます。メモ化デコレータとパラメータ化デコレータの作成方法を理解することで、再帰的な関数を最適化し、タイミングやロギングのメカニズムに柔軟性を加えることができます。
重要なポイント:
メモ化:
冗長な計算を回避するために結果をキャッシュします。
クラス、クロージャ、またはデコレータを使用して実装可能です。
`functools.lru_cache` は組み込みの効率的なメモ化デコレータを提供します。
パラメータ化デコレータ:
デコレータに引数を受け取らせることで、柔軟性を向上させます。
デコレータファクトリを使用して実装します。
繰り返し回数などのタイミングやログに有用です。
デコレータの積み重ね:
複数のデコレータを関数に適用できます。
適用される順序によって動作が変わります。
これらの高度なデコレータ技術を活用することで、より効率的でメンテナンスしやすく、エレガントなPythonコードを作成することができます。
次回の投稿では、さらに高度なデコレータの応用や、Pythonプロジェクトでのクロスカッティングな関心事の管理方法について探求していきますので、お楽しみに！