この記事では、Pythonで辞書のキャッシュとメモリゼーションを利用する方法を詳細に解説します。具体的なコード例とその解説、応用例を含めています。
目次
辞書のキャッシュとは
辞書のキャッシュとは、Pythonで高速なデータアクセスを可能にするテクニックの一つです。辞書（`dict`）を使用して、一度計算した値や取得したデータを保存しておくことで、再計算や再取得の手間を省きます。
基本的な使い方
以下は、フィボナッチ数列を求めるシンプルな例です。
# 辞書にフィボナッチ数列の計算結果を保存
cache = {}
def fib(n):
# 既に計算されていればキャッシュから取得
if n in cache:
return cache[n]
if n < 2:
return n
# 計算
val = fib(n-1) + fib(n-2)
# キャッシュに保存
cache[n] = val
return val
メモリゼーションとは
メモリゼーションは、一度計算した関数の結果を保存しておき、同じ入力が再度来た場合には保存された結果を返す最適化手法です。Pythonの`functools`ライブラリには、`lru_cache`というメモリゼーションを簡単に実装できるデコレータが存在します。
基本的な使い方
from functools import lru_cache
@lru_cache(maxsize=None) # キャッシュサイズ無制限
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
応用例
応用例1: 最短経路問題
辞書のキャッシュを用いて、最短経路問題を解く例です。
# キャッシュ
cache = {}
def shortest_path(start, end, graph):
if start == end:
return 0
if start in cache:
return cache[start]
min_distance = float('inf')
for neighbor in graph[start]:
distance = graph[start][neighbor] + shortest_path(neighbor, end, graph)
min_distance = min(min_distance, distance)
cache[start] = min_distance
return min_distance
応用例2: APIリクエストの高速化
APIリクエストの結果をメモリゼーションして高速化する例です。
from functools import lru_cache
import requests
@lru_cache(maxsize=100) # キャッシュサイズは100
def fetch_data(url):
response = requests.get(url)
return response.json()
応用例3: 動的計画法における組み合わせの数
動的計画法を使って、`n`個の要素から`r`個を選ぶ組み合わせの数を求める例です。
cache = {}
def combination(n, r):
if r == 0 or r == n:
return 1
if (n, r) in cache:
return cache[(n, r)]
val = combination(n-1, r-1) + combination(n-1, r)
cache[(n, r)] = val
return val
まとめ
Pythonで辞書のキャッシュとメモリゼーションを利用することで、計算速度を大幅に向上させることが可能です。以上の応用例を参考に、自分自身の問題解決に活用してみてください。
コメント