Python中的高效备忘录法

Question

我有一个任务需要解决，目前最重要的部分是让脚本尽可能高效。我要优化的一个元素是某个函数中的记忆化（memoization）。

所以我的问题是：以下这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会先在局部作用域中查找变量，然后在全局作用域中查找，跳过非局部作用域（在这个例子中是函数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中另一个相当常见的记忆化示例——记忆化对象作为函数本身的一个属性进行存储。

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装饰器），但我很难相信这比上面列出的方案更高效。如果我错了，请纠正我。

提前谢谢你们。

Answer 1

为了帮助那些在寻找Python中实现缓存功能的人，我推荐使用fastcache。

这个工具可以在Python 2和3上使用，比上面提到的任何方法都要快，而且它还提供了限制缓存大小的选项，这样就不会不小心让缓存变得太大：

from fastcache import clru_cache

@clru_cache(maxsize=128, typed=False)
def foo(cat_1, cat_2, cat_3):
    return cat_1 + cat_2 + cat_3

安装fastcache非常简单，可以使用pip：

pip install fastcache

或者使用conda：

conda install fastcache

Answer 2

不同的变量访问方式已经被测试和比较过，具体可以查看这个链接： http://code.activestate.com/recipes/577834-compare-speeds-of-different-kinds-of-access-to-var。这里有个简单的总结：本地访问的速度最快，其次是非本地访问（嵌套作用域），然后是全局访问（模块作用域），最后是访问内置函数。

你的解决方案#2（使用本地访问）应该是最快的。解决方案#3的速度较慢，因为它需要进行点查找（这需要查字典）。解决方案#1使用的是非本地访问（嵌套作用域），它使用的是单元变量（比查字典快，但比本地访问慢）。

另外要注意，KeyError这个异常类是全局查找，可以通过本地化来加速。你可以完全替换掉try/except，直接用 memo.get(n, sentinel)。而且即使这样，也可以通过使用绑定方法来进一步加速。当然，最简单的提速方法可能就是试试 pypy :-)

总之，有很多方法可以优化这段代码。只要确保这样做是值得的。