python - 当参数保持不变时，最小化 coSTLy 函数调用的次数(python)

Question

假设有一个函数 coSTLy_function_a(x) 使得:

1. 执行时间非常昂贵；
2. 只要输入相同的 x，它就会返回相同的输出；和
3. 除了返回输出外，它不执行“其他任务”。

在这些情况下，我们可以将结果存储在一个临时变量中，然后使用该变量进行这些计算，而不是连续两次使用相同的 x 调用该函数。

现在假设下面的例子中有一些函数(f(x)、g(x) 和 h(x) ) 调用 coSTLy_function_a(x)，并且其中一些函数可以相互调用(在下面的示例中，g(x) 和 h(x) 都调用 f(x))。在这种情况下，使用上面提到的简单方法仍然会导致使用相同的 x 重复调用 coSTLy_function_a(x)(参见下面的 OkayVersion) .我确实找到了一种最小化调用次数的方法，但它很“丑陋”(参见下面的 FastVersion)。有没有更好的方法来做到这一点？

#Dummy functions representing extremely slow code.
#The goal is to call these costly functions as rarely as possible.
def costly_function_a(x):
    print("costly_function_a has been called.")
    return x #Dummy operation.
def costly_function_b(x):
    print("costly_function_b has been called.")
    return 5.*x #Dummy operation.

#Simplest (but slowest) implementation.
class SlowVersion:
    def __init__(self,a,b):
        self.a = a
        self.b = b
    def f(self,x): #Dummy operation.
        return self.a(x) + 2.*self.a(x)**2
    def g(self,x): #Dummy operation.
        return self.f(x) + 0.7*self.a(x) + .1*x
    def h(self,x): #Dummy operation.
        return self.f(x) + 0.5*self.a(x) + self.b(x) + 3.*self.b(x)**2

#Equivalent to SlowVersion, but call the costly functions less often.
class OkayVersion:
    def __init__(self,a,b):
        self.a = a
        self.b = b
    def f(self,x): #Same result as SlowVersion.f(x)
        a_at_x = self.a(x)
        return a_at_x + 2.*a_at_x**2
    def g(self,x): #Same result as SlowVersion.g(x)
        return self.f(x) + 0.7*self.a(x) + .1*x
    def h(self,x): #Same result as SlowVersion.h(x)
        a_at_x = self.a(x)
        b_at_x = self.b(x)
        return self.f(x) + 0.5*a_at_x + b_at_x + 3.*b_at_x**2

#Equivalent to SlowVersion, but calls the costly functions even less often.
#Is this the simplest way to do it? I am aware that this code is highly
#redundant. One could simplify it by defining some factory functions...
class FastVersion:
    def __init__(self,a,b):
        self.a = a
        self.b = b
    def f(self, x, _at_x=None): #Same result as SlowVersion.f(x)
        if _at_x is None:
            _at_x = dict()
        if 'a' not in _at_x:
            _at_x['a'] = self.a(x)
        return _at_x['a'] + 2.*_at_x['a']**2
    def g(self, x, _at_x=None): #Same result as SlowVersion.g(x)
        if _at_x is None:
            _at_x = dict()
        if 'a' not in _at_x:
            _at_x['a'] = self.a(x)
        return self.f(x,_at_x) + 0.7*_at_x['a'] + .1*x
    def h(self,x,_at_x=None): #Same result as SlowVersion.h(x)
        if _at_x is None:
            _at_x = dict()
        if 'a' not in _at_x:
            _at_x['a'] = self.a(x)
        if 'b' not in _at_x:
            _at_x['b'] = self.b(x)
        return self.f(x,_at_x) + 0.5*_at_x['a'] + _at_x['b'] + 3.*_at_x['b']**2

if __name__ == '__main__':

    slow = SlowVersion(costly_function_a,costly_function_b)
    print("Using slow version.")
    print("f(2.) = " + str(slow.f(2.)))
    print("g(2.) = " + str(slow.g(2.)))
    print("h(2.) = " + str(slow.h(2.)) + "\n")

    okay = OkayVersion(costly_function_a,costly_function_b)
    print("Using okay version.")
    print("f(2.) = " + str(okay.f(2.)))
    print("g(2.) = " + str(okay.g(2.)))
    print("h(2.) = " + str(okay.h(2.)) + "\n")

    fast = FastVersion(costly_function_a,costly_function_b)
    print("Using fast version 'casually'.")
    print("f(2.) = " + str(fast.f(2.)))
    print("g(2.) = " + str(fast.g(2.)))
    print("h(2.) = " + str(fast.h(2.)) + "\n")

    print("Using fast version 'optimally'.")
    _at_x = dict()
    print("f(2.) = " + str(fast.f(2.,_at_x)))
    print("g(2.) = " + str(fast.g(2.,_at_x)))
    print("h(2.) = " + str(fast.h(2.,_at_x)))
    #Of course, one must "clean up" _at_x before using a different x...

这段代码的输出是:

Using slow version.
costly_function_a has been called.
costly_function_a has been called.
f(2.) = 10.0
costly_function_a has been called.
costly_function_a has been called.
costly_function_a has been called.
g(2.) = 11.6
costly_function_a has been called.
costly_function_a has been called.
costly_function_a has been called.
costly_function_b has been called.
costly_function_b has been called.
h(2.) = 321.0

Using okay version.
costly_function_a has been called.
f(2.) = 10.0
costly_function_a has been called.
costly_function_a has been called.
g(2.) = 11.6
costly_function_a has been called.
costly_function_b has been called.
costly_function_a has been called.
h(2.) = 321.0

Using fast version 'casually'.
costly_function_a has been called.
f(2.) = 10.0
costly_function_a has been called.
g(2.) = 11.6
costly_function_a has been called.
costly_function_b has been called.
h(2.) = 321.0

Using fast version 'optimally'.
costly_function_a has been called.
f(2.) = 10.0
g(2.) = 11.6
costly_function_b has been called.
h(2.) = 321.0

请注意，我不想“存储”过去使用的所有 x 值的结果(因为这需要太多内存)。此外，我不希望函数返回 (f,g,h) 形式的元组，因为在某些情况下我只想要 f (所以有无需评估 coSTLy_function_b)。

Answer 1

你要找的是LRU缓存；仅缓存最近使用的项目，限制内存使用以平衡调用成本与内存需求。

当您使用不同的 x 值调用昂贵的函数时，最多会缓存多个返回值(每个唯一的 x 值)，最近最少的已用缓存结果在缓存已满时丢弃。

从 Python 3.2 开始，标准库带有装饰器实现:@functools.lru_cache() :

from functools import lru_cache

@lru_cache(16)  # cache 16 different `x` return values
def costly_function_a(x):
    print("costly_function_a has been called.")
    return x #Dummy operation.

@lru_cache(32)  # cache 32 different `x` return values
def costly_function_b(x):
    print("costly_function_b has been called.")
    return 5.*x #Dummy operation.

A backport is available对于早期版本，或选择其他可用的库之一，这些库可以处理 PyPI 上可用的 LRU 缓存。

如果你只需要缓存一个最近的项目，创建你自己的装饰器:

from functools import wraps

def cache_most_recent(func):
    cache = [None, None]
    @wraps(func)
    def wrapper(*args, **kw):
        if (args, kw) == cache[0]:
            return cache[1]
        cache[0] = args, kw
        cache[1] = func(*args, **kw)
        return cache[1]
    return wrapper

@cache_most_recent
def costly_function_a(x):
    print("costly_function_a has been called.")
    return x #Dummy operation.

@cache_most_recent
def costly_function_b(x):
    print("costly_function_b has been called.")
    return 5.*x #Dummy operation.

这个更简单的装饰器比功能更强大的 functools.lru_cache() 开销更少。