Python中的有效备忘 [英] Efficient memoization in Python

问题描述

我有一些任务要解决，目前最重要的部分是使脚本尽可能地节省时间.我要优化的元素之一是其中一个功能中的记忆.

I have some task to solve and the most important part at the moment is to make the script as time-efficient as possible. One of the elements I am trying to optimize is memoization within one of the functions.

所以我的问题是:以下3-4种方法中，哪一种是在Python中实现备忘录的最有效/最快的方法?

我仅提供了代码作为示例-如果其中一种方法更有效，但在我提到的情况下效率不高，请分享您所知道的信息.

I have provided code only as an example - if one of the methods is more efficient, but not in the case I mentioned, please share what you know.

此解决方案通常作为示例备忘录显示，但是我不确定它的效率如何.我听说使用全局变量(在这种情况下，它是来自外部的变量，而不是全局范围的变量)效率较低.

This solution is often shown as the example memoization, but I am not sure how efficient it is. I have heard that using global variables (in this case it is variable from outer, not global scope) is less efficient.

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()中的范围).因为默认参数仅在定义函数时才初始化，并且只能在内部函数内部访问，所以这样可能更有效?

Solution 2 - using default, mutable argument

I have found somewhere that using default mutable arguments has been used in the past to pass variables from outer scope, when Python searched the variable first in the local scope, then in the global scope, skipping the nonlocal scope (in this case the scope within function main()). Because default argument is initialized only at the time function is defined and is accessible only inside the inner function, maybe it is thus more efficient?

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的组合)更有效?

Or maybe the following version (being in fact a combination of solutions 1&2) is more efficient?

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

Solution 3 - function's attribute

This is another quite common example of memoization in Python - the memoization object is stored as an attribute of the function itself.

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

摘要

我对您对以上四个记忆解决方案的意见非常感兴趣.同样重要的是，使用记忆的功能在另一个功能内.

Summary

I am very interested in your opinions about the four above solutions for memoization. It is important also, that the function that uses memoization is within another function.

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

I know that there are also other solutions for memoization (such as Memoize decorator), but it is hard for me to believe that this is more efficient solution than these listed above. Correct me if I am wrong.

谢谢.

推荐答案

已对不同类型的变量访问进行了计时，并在以下位置进行了比较:

The different styles of variable access have already been timed and compared at: http://code.activestate.com/recipes/577834-compare-speeds-of-different-kinds-of-access-to-var Here's a quick summary: local access beats nonlocal (nested scopes) which beat global access (module scope) which beats access to builtins.

您的解决方案2(具有本地访问权限)应该会获胜.解决方案#3具有慢点查找(需要字典查找).解决方案#1使用非本地(嵌套作用域)访问，该访问使用单元变量(比dict查询快，但比本地变量慢).

Your solution #2 (with local access) should win. Solution #3 has a slow-dotted lookup (which requires a dictionary lookup). Solution #1 uses nonlocal (nested scope) access which uses cell-variables (faster than a dict lookup but slower than locals).

还请注意， KeyError 异常类是全局查找，可以通过对其进行本地化来加速.您可以完全替换try/except并改用memo.get(n, sentinel).甚至可以通过使用bound方法来加快速度.当然，最简单的提速方法可能只是尝试 pypy :-)

Also note, the KeyError exception class is a global lookup and can be sped-up by localizing it. You could replace the try/except entirely and use a memo.get(n, sentinel) instead. And even that could be sped-up by using a bound method. Of course, your easiest speed boost may just come from trying out pypy :-)

简而言之，有许多方法可以调整此代码.只需确保它值得.

In short, there are many ways to tweak this code. Just make sure it's worth it.

这篇关于Python中的有效备忘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！