PythonでBounded Memoization Decoratorを作成するにはどうすればよいですか？

Question

明らかに、クイック検索により、Pythonのメモ化デコレーターの100万の実装とフレーバーが得られます。しかし、私は私が見つけることができなかったフレーバーに興味があります。保存された値のキャッシュが固定容量になるようにしたいと思います。新しい要素が追加されると、容量に到達すると、最古の値が削除され、最新の値に置き換えられます。

私の懸念は、メモを使用して非常に多くの要素を保存すると、メモリが不足しているためにプログラムがクラッシュすることです。 （この懸念が実際にどれほど適切であるかはわかりません。）キャッシュが固定サイズの場合、メモリエラーは問題になりません。そして、プログラムが実行されると私が変更に取り組んでいる多くの問題が、初期のキャッシュ値が後のキャッシュ値とは非常に異なって見えるようにする（そして後で再発する可能性ははるかに低いでしょう）。だからこそ、最古のものを最新のものに置き換えたいのです。

私はそれを見つけました OrderedDict クラスと、最大サイズを指定するためにサブクラス化する方法を示す例。それを通常ではなくキャッシュとして使用したい dict. 。問題は、呼ばれるパラメーターを取得するには、メモのデコレーターが必要です。 maxlen それはデフォルトです None. 。もしそれが None, 、その後、キャッシュは無限であり、通常のように動作します。その他の値は、キャッシュのサイズとして使用されます。

次のように動作したい：

@memoize
def some_function(spam, eggs):
    # This would use the boundless cache.
    pass

と

@memoize(200)  # or @memoize(maxlen=200)
def some_function(spam, eggs):
    # This would use the bounded cache of size 200.
    pass

以下は私がこれまでに持っているコードですが、パラメーターを「裸」とパラメーターの両方で動作させる間、パラメーターを装飾器に渡す方法がわかりません。

import collections
import functools

class BoundedOrderedDict(collections.OrderedDict):
    def __init__(self, *args, **kwds):
        self.maxlen = kwds.pop("maxlen", None)
        collections.OrderedDict.__init__(self, *args, **kwds)
        self._checklen()

    def __setitem__(self, key, value):
        collections.OrderedDict.__setitem__(self, key, value)
        self._checklen()

    def _checklen(self):
        if self.maxlen is not None:
            while len(self) > self.maxlen:
                self.popitem(last=False)

def memoize(function):
    cache = BoundedOrderedDict()  # I want this to take maxlen as an argument
    @functools.wraps(function)
    def memo_target(*args):
        lookup_value = args
        if lookup_value not in cache:
            cache[lookup_value] = function(*args)
        return cache[lookup_value]
    return memo_target

@memoize
def fib(n):
    if n < 2: return 1
    return fib(n-1) + fib(n-2)

if __name__ == '__main__':
    x = fib(50)
    print(x)

編集: ：ベンの提案を使用して、次のデコレーターを作成しました。これは、想像した方法で機能すると思います。これらの装飾された機能を使用することができることは私にとって重要です multiprocessing, 、それは過去に問題でした。しかし、このコードの迅速なテストは、仕事をスレッドのプールに耕作する場合でも、正しく機能するように見えました。

def memoize(func=None, maxlen=None):
    if func:
        cache = BoundedOrderedDict(maxlen=maxlen)
        @functools.wraps(func)
        def memo_target(*args):
            lookup_value = args
            if lookup_value not in cache:
                cache[lookup_value] = func(*args)
            return cache[lookup_value]
        return memo_target
    else:
        def memoize_factory(func):
            return memoize(func, maxlen=maxlen)
        return memoize_factory

Answer 1

@memoize
def some_function(spam, eggs):
    # This would use the boundless cache.
    pass

ここ memoize 単一の関数引数で呼び出され、関数を返す関数として使用されます。 memoize デコレーターです。

@memoize(200)  # or @memoize(maxlen=200)
def some_function(spam, eggs):
    # This would use the bounded cache of size 200.
    pass

ここ memoize 単一の整数引数で呼び出され、関数を返す関数として使用されます。また、返された関数は、単一の関数引数で呼び出され、関数を返すデコレーターとして使用されます。 memoize aです デコレーター工場.

したがって、これら2つを統一するには、醜いコードを書く必要があります。私がおそらくそれをする方法は持っていることです memoize こんな風に見える：

def memoize(func=None, maxlen=None):
    if func:
        # act as decorator
    else:
        # act as decorator factory

パラメーターを渡す場合は、このようにしてください いつも キーワード引数としてそれらを渡し、去ります func （これは位置パラメーターである必要があります）設定されていません。すべてをデフォルトにしたい場合は、魔法のようにデコレーターとして直接機能します。これは意味します @memoize(200) エラーが発生します。代わりに、何らかのタイプチェックを行い、確認することでそれを避けることができます func 呼ばれますが、実際にはうまく機能するはずですが、実際にはあまり「Pythonic」ではありません。

別の方法は、2つの異なるデコレーターを持つことです。 memoize と bounded_memoize. 。バウンドされていない memoize 電話をかけるだけで些細な実装をすることができます bounded_memoize と maxlen に設定 None, 、そのため、実装やメンテナンスには何もかかりません。

通常、経験則として、機能をマングルして、2つの唯一の対応に関連する機能セットを実装することを避けようとします。 特に 彼らがそのような異なる署名を持っているとき。しかし、この場合、それはそれを作ります 使用する デコレーターの自然です（必要です @memoize() 理論的な観点からより一貫しているにもかかわらず、非常にエラーが発生しやすいでしょう）、おそらくこれを1回実装して何度も使用するので、使用時点での読みやすさはおそらくより重要な懸念です。

Answer 2

あなたは引数を取るデコレーターを書いて欲しいです（の最大長さ BoundedOrderedDict）そして、あなたの関数をでメモ化するデコレーターを返します BoundedOrderedDict 適切なサイズの：

def boundedMemoize(maxCacheLen):
    def memoize(function):
        cache = BoundedOrderedDict(maxlen = maxCacheLen)
        def memo_target(*args):
            lookup_value = args
            if lookup_value not in cache:
                cache[lookup_value] = function(*args)
            return cache[lookup_value]
        return memo_target
    return memoize

このように使用できます。

@boundedMemoize(100)
def fib(n):
    if n < 2: return 1
    return fib(n - 1) + fib(n - 2)

編集： おっと、質問の一部を逃した。デコレーターに対するMaxlen引数をオプションにしたい場合は、次のようなことをすることができます。

def boundedMemoize(arg):
    if callable(arg):
        cache = BoundedOrderedDict()
        @functools.wraps(arg)
        def memo_target(*args):
            lookup_value = args
            if lookup_value not in cache:
                cache[lookup_value] = arg(*args)
            return cache[lookup_value]
        return memo_target

    if isinstance(arg, int):
        def memoize(function):
            cache = BoundedOrderedDict(maxlen = arg)
            @functools.wraps(function)
            def memo_target(*args):
                lookup_value = args
                if lookup_value not in cache:
                    cache[lookup_value] = function(*args)
                return cache[lookup_value]
            return memo_target
        return memoize

Answer 3

から http://www.python.org/dev/peps/pep-0318/

現在の構文では、デコレーター宣言がデコレータを返す関数を呼び出すこともできます。

@decomaker(argA, argB, ...)
def func(arg1, arg2, ...):
    pass

これは次のとおりです。

func = decomaker(argA, argB, ...)(func)

また、このためにOrderedDictを使用するかどうかはわかりません。リングバッファーを使用します。実装が非常に簡単です。