435

Python を始めたばかりで、メモ化とは何か、どのように使用するのかわかりません。また、簡単な例がありますか？

4

13 に答える 13

393

メモ化とは、事実上、メソッド入力に基づいてメソッド呼び出しの結果を記憶（「メモ化」→「メモ」→記憶する）し、結果を再度計算するのではなく、記憶した結果を返すことを指します。これは、メソッド結果のキャッシュと考えることができます。詳細については、Cormen etal。のIntroductionToAlgorithms （3e）の定義について387ページを参照してください。

Pythonでメモ化を使用して階乗を計算する簡単な例は、次のようになります。

factorial_memo = {}
def factorial(k):
    if k < 2: return 1
    if k not in factorial_memo:
        factorial_memo[k] = k * factorial(k-1)
    return factorial_memo[k]

より複雑になり、メモ化プロセスをクラスにカプセル化できます。

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        #Warning: You may wish to do a deepcopy here if returning objects
        return self.memo[args]

それで：

def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

factorial = Memoize(factorial)

「デコレータ」と呼ばれる機能がPython2.4に追加されました。これにより、次のように記述して同じことを実行できます。

@Memoize
def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

Pythonデコレータライブラリには、ここに示すクラスmemoizedよりもわずかに堅牢な、と呼ばれる同様のデコレータがあります。Memoize

于 2010-01-01T15:05:05.797 に答える
287

functools.cacheデコレータ：

Python3.9は新しい関数をリリースしましたfunctools.cache。これは、メモ化である特定の引数のセットで呼び出された関数の結果をメモリにキャッシュします。使い方は簡単です：

import functools

@functools.cache
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

デコレータなしのこの関数は非常に遅いので、試しfib(36)てみてください。約10秒待つ必要があります。

cacheデコレータを追加すると、関数が特定の値に対して最近呼び出された場合、その値は再計算されず、キャッシュされた以前の結果が使用されます。この場合、コードがキャッシュの詳細で乱雑になることなく、速度が大幅に向上します。

functools.lru_cacheデコレータ：

古いバージョンのPythonをサポートする必要がある場合は、functools.lru_cachePython3.2以降で動作します。デフォルトでは、最近使用された128の呼び出しのみがキャッシュされますが、キャッシュが期限切れにならないことを示すようにをmaxsize設定できます。None

@functools.lru_cache(maxsize=None)
def fib(num):
    # etc
于 2013-02-06T14:43:14.730 に答える
61

他の答えは、それが何であるかを非常によくカバーしています。私はそれを繰り返していません。参考になりそうなポイントばかり。

通常、メモ化は、何か (高価な) を計算して値を返す任意の関数に適用できる操作です。このため、多くの場合、デコレータとして実装されます。実装は簡単で、次のようになります

memoised_function = memoise(actual_function)

またはデコレータとして表現

@memoise
def actual_function(arg1, arg2):
   #body
于 2010-01-02T14:55:06.710 に答える
22

これは非常に便利だと思います

from functools import wraps


def memoize(function):    
    memo = {}
        
    @wraps(function)
    def wrapper(*args):

        # add the new key to dict if it doesn't exist already  
        if args not in memo:
            memo[args] = function(*args)

        return memo[args]

    return wrapper
    
    
@memoize
def fibonacci(n):
    if n < 2: return n
    return fibonacci(n - 1) + fibonacci(n - 2)
    
fibonacci(25)
于 2016-11-17T12:58:19.017 に答える
19

メモ化とは、コストのかかる計算の結果を保持し、継続的に再計算するのではなく、キャッシュされた結果を返すことです。

次に例を示します。

def doSomeExpensiveCalculation(self, input):
    if input not in self.cache:
        <do expensive calculation>
        self.cache[input] = result
    return self.cache[input]

より完全な説明は、メモ化に関するウィキペディアのエントリにあります。

于 2010-01-01T15:05:56.793 に答える
17

hasattr手作りしたい人のために、ビルトイン機能を忘れないでください。そうすれば、mem キャッシュを関数定義内に保持できます (グローバルではなく)。

def fact(n):
    if not hasattr(fact, 'mem'):
        fact.mem = {1: 1}
    if not n in fact.mem:
        fact.mem[n] = n * fact(n - 1)
    return fact.mem[n]
于 2014-11-06T00:35:16.013 に答える
6

メモ化とは、基本的に、後の段階で同じ計算が必要になった場合に再帰ツリーをトラバースする必要性を減らすために、再帰アルゴリズムで実行された過去の操作の結果を保存することです。

http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/を参照してください

Pythonでのフィボナッチメモ化の例：

fibcache = {}
def fib(num):
    if num in fibcache:
        return fibcache[num]
    else:
        fibcache[num] = num if num < 2 else fib(num-1) + fib(num-2)
        return fibcache[num]
于 2012-12-13T17:45:55.607 に答える
5

メモ化とは、関数をデータ構造に変換することです。通常、変換を段階的かつ遅延的に実行する必要があります（特定のドメイン要素または「キー」の要求に応じて）。怠惰な関数型言語では、この怠惰な変換は自動的に行われる可能性があるため、（明示的な）副作用なしにメモ化を実装できます。

于 2011-08-09T23:49:51.157 に答える
4

これは、泣き言を言わずにリストまたは辞書型の引数で機能するソリューションです。

def memoize(fn):
    """returns a memoized version of any function that can be called
    with the same list of arguments.
    Usage: foo = memoize(foo)"""

    def handle_item(x):
        if isinstance(x, dict):
            return make_tuple(sorted(x.items()))
        elif hasattr(x, '__iter__'):
            return make_tuple(x)
        else:
            return x

    def make_tuple(L):
        return tuple(handle_item(x) for x in L)

    def foo(*args, **kwargs):
        items_cache = make_tuple(sorted(kwargs.items()))
        args_cache = make_tuple(args)
        if (args_cache, items_cache) not in foo.past_calls:
            foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs)
        return foo.past_calls[(args_cache, items_cache)]
    foo.past_calls = {}
    foo.__name__ = 'memoized_' + fn.__name__
    return foo

このアプローチは、独自のハッシュ関数を handle_item の特別なケースとして実装することで、任意のオブジェクトに自然に拡張できることに注意してください。たとえば、セットを入力引数として受け取る関数でこのアプローチを機能させるには、handle_item に次のように追加できます。

if is_instance(x, set):
    return make_tuple(sorted(list(x)))
于 2013-06-24T05:53:40.970 に答える
3

既に提供されている回答に追加したいだけですが、Python デコレータ ライブラリには、functools.lru_cache.

于 2014-08-18T15:56:38.927 に答える
3

キーワード引数が渡された順序に関係なく、位置引数とキーワード引数の両方で機能するソリューション ( inspect.getargspecを使用):

import inspect
import functools

def memoize(fn):
    cache = fn.cache = {}
    @functools.wraps(fn)
    def memoizer(*args, **kwargs):
        kwargs.update(dict(zip(inspect.getargspec(fn).args, args)))
        key = tuple(kwargs.get(k, None) for k in inspect.getargspec(fn).args)
        if key not in cache:
            cache[key] = fn(**kwargs)
        return cache[key]
    return memoizer

同様の質問: Python でのメモ化のための同等の varargs 関数呼び出しの識別

于 2014-01-30T14:26:02.220 に答える
2 
cache = {}
def fib(n):
    if n <= 1:
        return n
    else:
        if n not in cache:
            cache[n] = fib(n-1) + fib(n-2)
        return cache[n]
于 2013-01-06T15:02:23.350 に答える