如何在Python中创建一个有界记忆化装饰器？

Question

显然，在Python中，快速搜索可以得到数百万种memoization装饰器的实现和风味。然而，我对一种我无法找到的风味感兴趣。我希望它能够使存储值的缓存具有固定容量。当添加新元素时，如果达到容量，则删除最旧的值并用最新的值替换它。

我的担忧是，如果我使用memoization来存储大量元素，那么程序将因为缺乏内存而崩溃。(我不知道这种担忧在实践中是否合理。)如果缓存的大小是固定的，那么内存错误就不是一个问题了。而且，我处理的许多问题会随着程序的执行而改变，因此最初缓存的值看起来会与后来缓存的值非常不同(并且很少再次出现)。这就是为什么我希望最老的东西被最新的东西替换。

我发现了OrderedDict类和一个示例，展示了如何对其进行子类化以指定最大大小。我想使用它作为我的缓存，而不是普通的dict。问题是，我需要memoize装饰器接受一个名为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)

编辑：根据Ben的建议，我创建了以下装饰器，我相信它按照我想象的方式工作。对于我来说，能够使用这些被修饰过的函数与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

- agarrett

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是一个装饰器工厂。

因此，为了统一这两个功能，您需要编写一些丑陋的代码。我可能会这样做：memoize看起来像这样：

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

这样，如果您希望传递参数，您总是将它们作为关键字参数传递，将应该是位置参数的func留空，如果您只想使用默认值，它就会神奇地直接作为装饰器工作。这意味着@memoize(200)将导致错误；您可以通过执行一些类型检查来避免这种情况，并查看func是否可调用，在实践中应该效果很好，但并不真正符合“Pythonic”风格。

另一种选择是拥有两个不同的装饰器，例如memoize和bounded_memoize。无界的memoize可以通过仅将maxlen设置为None而具有微不足道的实现，因此在实现或维护方面都不会浪费任何成本。

通常，我尽量避免操纵函数以实现两个只有间接联系的功能集，特别是当它们具有如此不同的签名时。但在这种情况下，装饰器的使用是自然的（要求使用@memoize()可能会非常容易出错，即使从理论上讲，它更加一致），而且您可能会实现一次并多次使用它，因此在使用点上的可读性可能是更重要的问题。

- Ben

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

- srgerg

---

不完全正确。在我的问题中，我要求的是一些可以在有或没有参数的情况下等效工作的东西。我不认为这个可以做到。 - agarrett

Answer 3

来自http://www.python.org/dev/peps/pep-0318/

当前语法还允许装饰器声明调用返回装饰器的函数：

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

这相当于：

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

此外，我不确定是否要使用OrderedDict，而是会使用环形缓冲区，它们非常容易实现。

- fileoffset