我有一些任务要解决,目前最重要的部分是尽可能地使脚本时间效率更高。我试图优化的元素之一是在一个函数中的备忘录。
所以我的问题是:以下3-4种方法中哪种是Python实现备忘录最有效/最快的方法?
我只提供了示例代码 - 如果其中一种方法更有效,但不适用于我提到的情况,请分享您所知道的内容。
解决方案1-使用来自外部作用域的可变变量
这个解决方案通常被展示为备忘录的示例,但我不确定它有多有效。我听说使用全局变量(在这种情况下是来自外部而不是全局作用域的变量)效率较低。
def main():
memo = {}
def power_div(n):
try:
return memo[n]
except (KeyError):
memo[n] = (n ** 2) % 4 # example expression, should not matter
return memo[n]
# extensive usage of power_div() here
解决方案2 - 使用默认的可变参数
我在某个地方发现过使用默认的可变参数将变量从外部作用域传递到内部函数,当Python首先在局部作用域中搜索变量,然后在全局作用域中搜索变量,跳过非局部作用域(在本例中是函数内的作用域)时,这种方式被使用过。因为默认参数仅在定义函数时初始化,并且仅在内部函数中可访问,所以可能更有效率?
def main():
def power_div(n, memo={}):
try:
return memo[n]
except (KeyError):
memo[n] = (n ** 2) % 4 # example expression, should not matter
return memo[n]
# extensive usage of power_div() here
或者下面这个版本(实际上是解决方案1和2的组合)更有效呢?
def main():
memo = {}
def power_div(n, memo=memo):
try:
return memo[n]
except (KeyError):
memo[n] = (n ** 2) % 4 # example expression, should not matter
return memo[n]
# extensive usage of power_div() here
解决方案3 - 函数属性
这是Python中另一种常见的记忆化例子 - 记忆化对象作为函数本身的一个属性被存储。
def main():
def power_div(n):
memo = power_div.memo
try:
return memo[n]
except (KeyError):
memo[n] = (n ** 2) % 4 # example expression, should not matter
return memo[n]
# extensive usage of power_div() here
总结
我对上述四种记忆化解决方案非常感兴趣。重要的是,使用记忆化的函数必须在另一个函数中。
我知道还有其他记忆化解决方案(如Memoize
装饰器),但很难相信这比上面列出的更有效。如果我错了,请纠正我。
提前致谢。
timeit
模块提供了一种非常好的测试方式来测试这类事情。 - Ambertimeit
,因为1)我可能会错过其他更有效的解决方案;2)我的结果可能会因我使用备忘录的方式而出现偏差。我正在尝试找到使用备忘录的最快方法来学习并让人们知道,而不一定是修复这一段代码(这样的问题将过于局限)。 - Tadeckget()
方法比捕获KeyError
更快。但也有可能加速只会影响“缓存未命中”的分支,这种情况下可能不值得。不过最好还是对两种方式进行计时比较一下。 - Daniel Prydenget()
,但是由于如果没有找到键就需要计算某些东西,所以看起来会像这样:memo.get(n, (n ** 2) % 4)
。在这种情况下,这样做没有太多意义,因为(n ** 2) % 4
将在每次调用函数时执行(因此记忆化将无效)。 - Tadeck