Pythonでメモ化の実装|関数やクラス、デコレーターを使った方法を解説

スポンサーリンク

この記事では、非常に人気のある最適化技術の1つで、主にコンピュータプログラムの高速化に使用されるPythonのMemoizationについて説明します。

スポンサーリンク

Pythonのメモ化とは?

コンピュータプログラミングの世界では、メモ化またはPythonのメモ化は、主にコンピュータプログラムを高速化するために使用される、特殊な最適化技術です。

実行時間の長い関数呼び出しの結果をメモリに保存し、保存された値やキャッシュされた値が必要なときにそれを使用することで、コンピュータプログラムの実行時間を効果的に短縮します。

特定の関数やメソッドが同じ入力に対して何度も実行される必要がないのは、結果がすでにキャッシュ/保存されたデータとして利用可能だからです。

キャッシュと似ている。

入力パラメータに基づいた関数の戻り値をキャッシュすることです。

Pythonでは、関数やクラスベースのデコレータを使って、プログラムにメモ化の技術を実装することができます

なぜなら、入力が大きくなると、同じ入力値に対する関数呼び出しの回数が増えるので、このプログラムは非常に遅くなるからです。

関数ベースのデコレータを用いたPythonのメモ化

メモライゼーションが実際にどのように機能するかを理解したい人にとって、Pythonでメモライゼーションを実装する最も良い方法かつ最も複雑な方法です。

このメモ化手法の実装方法では、関数呼び出しの戻り値をキャッシュ/保存するために、Pythonで独自のデコレータ関数を定義します。

では、これを実装するためのPythonコードの書き方を見てみましょう。

# Memoization using function-based decorators
 
def memoize(f):
    cache = {}
    def foo(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    return foo
 
@memoize
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
 
# Driver code
fibonacci(20)

結果は以下の通りです。

6765

クラスベースのデコレータを用いたメモ化

メモライゼーションが実際にどのように機能するかを理解したい初心者のために、Pythonでメモライゼーションを実装する2番目に良い方法であり、複雑な方法です。

この方法では、関数呼び出しの戻り値をキャッシュ/保存するために、独自のデコレータクラスを定義します。

これを実装するためのPythonのコードを書いてみましょう。

# Memoization using class-based decorators
 
class classMemoize:
    def __init__(self, f):
        self.f = f
        self.cache = {}
    def __call__(self, *x):
        if x not in self.cache:
            self.cache[x] = self.f(*x)
        return self.cache[x]
 
@classMemoize
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
 
# Driver code
fibonacci(50)

結果は以下の通りです。

12586269025

組み込みのデコレーター関数を使ったメモ化

Python でメモ化技術を実装する最もシンプルで簡単な方法の一つです。

この方法では、独自のデコレーター関数やクラスを定義せず、 lru_cache()cache() といった組み込み関数を使用して、関数呼び出しの中間結果をキャッシュ/保存します。

これらの lru_cache()cache() 関数は、Python の標準ライブラリである funtools ライブラリで定義されており、通常の Python インストール時に付属しています。

lru_cache(maxsize=None, typed=False)関数は、maxsizetypedといったパラメータを通して、いくつかのカスタマイズ機能を提供します。

パラメータmaxsizeは、LRU 機能を有効にするかどうかを None か整数値で指定します。

また、パラメータtyped` は、異なるタイプのデータを別々にキャッシュするかどうかを決定します。

整数値はPythonプログラムの実行中に維持されるキャッシュのサイズを制限し、None値はLRU機能を無効にして、キャッシュが無制限に増加できるようにします。

cache()関数は Python 3.9 リリース以降で利用可能で、funtoolsライブラリのlru_cache(maxsize=None)` 関数と同等の機能を持ちます。

# Memoization using built-in function
 
import functools
 
@functools.cache
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
 
# Driver code
fibonacci(100)

結果は以下の通りです。

354224848179261915075

まとめ

この記事では、関数とクラスベースのデコレータを使った Python のメモ化技術の使い方を学びました。

このチュートリアルで説明したことをよく理解し、あなたのPythonプログラムでこのメモ化技術を使い、実装し、速度を向上させる準備ができていることを願っています。

タイトルとURLをコピーしました