Python中的高效memoization

Question

我有一些任务需要解决,目前最重要的部分是使脚本尽可能节省时间.我试图优化的一个要素是其中一个函数中的memoization.

所以我的问题是:以下3-4种方法中哪一种是在Python中实现memoization的最有效/最快的方法？

我只提供了代码作为示例 - 如果其中一种方法更有效,但在我提到的情况下,请分享您所知道的内容.

解决方案1 ​​ - 使用外部范围的可变变量

此解决方案通常显示为示例memoization,但我不确定它的效率如何.我听说使用全局变量(在这种情况下,它是从外部变量而不是全局变量)效率较低.

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首先在本地作用域中搜索变量,然后在全局作用域中,跳过非局部作用域(在本例中为范围内)功能main()).因为默认参数仅在定义函数时初始化,并且只能在内部函数内部访问,因此它可能更有效吗？

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中memoization的另一个非常常见的例子 - memoization对象存储为函数本身的属性.

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

摘要

我对您对上述四种备忘解决方案的看法非常感兴趣.同样重要的是,使用memoization的函数在另一个函数中.

我知道还有其他的记忆解决方案(例如Memoize装饰器),但我很难相信这是比上面列出的更有效的解决方案.如果我错了,请纠正我.

提前致谢.

Answer 1

不同风格的变量访问已经定时并进行了比较:http: //code.activestate.com/recipes/577834-compare-speeds-of-different-kinds-of-access-to-var 这里有一个快速摘要:本地访问胜过非本地(嵌套作用域),它击败了访问内置的全局访问(模块范围).

您的解决方案#2(具有本地访问权限)应该获胜.解决方案#3有一个慢点查找(需要字典查找).解决方案#1使用非局部(嵌套范围)访问,该访问使用单元格变量(比dict查找更快但比本地更慢).

另请注意,KeyError异常类是全局查找,可以通过本地化来加速.您可以完全替换try/except并使用memo.get(n, sentinel)替代.甚至可以通过使用绑定方法来加速.当然,你最简单的速度提升可能只是来自尝试pypy :-)

简而言之,有很多方法可以调整此代码.只要确保它是值得的.