假设有一个函数 coSTLy_function_a(x)
使得:
- 执行时间非常昂贵;
- 只要输入相同的
x
,它就会返回相同的输出;和 - 除了返回输出外,它不执行“其他任务”。
在这些情况下,我们可以将结果存储在一个临时变量中,然后使用该变量进行这些计算,而不是连续两次使用相同的 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
)。
最佳答案
你要找的是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()
开销更少。
关于python - 当参数保持不变时,最小化 coSTLy 函数调用的次数(python),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20435245/