如何在Python中创建有界的memoization装饰器？

Question

显然,快速搜索会在Python中产生一百万个memoization装饰器的实现和风格.但是,我感兴趣的是一种我无法找到的味道.我希望它能够使存储值的缓存具有固定容量.添加新元素时,如果达到容量,则删除最旧的值并替换为最新值.

我担心的是,如果我使用memoization来存储很多元素,那么程序会因为缺少内存而崩溃.(我不知道这种担忧在实践中有多好.)如果缓存的大小固定,那么内存错误就不是问题.我工作的许多问题随着程序的执行而发生变化,因此初始缓存的值看起来与以后的缓存值非常不同(以后不太可能再次发生).这就是为什么我希望最新的东西被最新的东西取代.

我找到了这个OrderedDict类和一个示例,展示了如何将其子类化以指定最大大小.我想将它用作我的缓存,而不是正常dict.问题是,我需要memoize装饰器来获取一个名为maxlendefaults 的参数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

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。只需调用set tomemoize即可实现无界的简单实现，因此在实现或维护方面不会花费您任何费用。bounded_memoizemaxlenNone

通常，根据经验，我会尽量避免修改函数来实现两个仅切线相关的功能集，特别是当它们具有如此不同的签名时。但在这种情况下，它确实使装饰器的使用@memoize()变得自然（要求会很容易出错，即使从理论角度来看它更一致），并且您可能会实现一次并使用它多次，所以使用时的可读性可能是更重要的问题。