为什么一种记忆化策略比另一种慢？

Question

这篇关于记忆化的文章引起了我的好奇心。我做了自己的基准测试。

1）可变默认字典：

%%timeit
def fibo(n, dic={}) :
    if n not in dic :
        if n in (0,1) :
            dic[n] = 1
        else :
            dic[n] = fibo(n-1)+fibo(n-2)
    return dic[ n ]
fibo(30)

输出：

100000 loops, best of 3: 18.3 µs per loop

2) 相同的思路，但遵循“宁可道歉不要求许可”的原则：

In [21]:

%%timeit
def fibo(n, dic={}) :
    try :
        return dic[n]
    except :
        if n in (0,1) :
            dic[n] = 1
        else :
            dic[n] = fibo(n-1)+fibo(n-2)
        return dic[ n ]
fibo(30)

输出：

10000 loops, best of 3: 46.8 µs per loop

我的问题

• 为什么2）与1）相比速度如此之慢？

编辑

正如评论中@kevin所建议的那样，我完全弄错了装饰器，因此我将其删除。剩下的仍然有效！（希望是这样）

- usual me

---

这是一个非常不寻常的装饰器。通常情况下，当你装饰一个函数时，在装饰器的某个地方，你会在完成一些工作后调用该函数。但是你的装饰器从未调用过 f。当你装饰 fibo 时，实际上是在做“丢弃此函数的定义，并用示例1中的函数替换它”的操作。 - Kevin

捕获异常（即堆栈跟踪）可能非常耗时：https://docs.python.org/2/faq/design.html#how-fast-are-exceptions - Dmitry Bychenko

@DmitryBychenko，我认为你应该将其发布为答案。 - Sylvain Leroux

“容易获得原谅比事先征得许可的原则”来自哪里？在编程环境中，这听起来相当不合理。 - BartoszKP

@BartoszKP 这是真的。大多数情况下，用户可能会给你正确的东西。这就是为什么最好假设他们给了你正确的东西，如果它是错误的，只需处理异常即可。这样可以避免 hasattr 或 if key in d: 的开销。此原则经常用于在尝试使用键/属性之前检查它们的存在，这更容易被原谅（有时候）。 - dano

Answer 1

抓取异常意味着堆栈跟踪，这可能非常昂贵：

https://docs.python.org/2/faq/design.html#how-fast-are-exceptions

在两种情况下，异常非常有效：

1. try ... finally
2. try ... except，前提是没有抛出异常

然而，当异常发生并被捕获时，所需的堆栈跟踪会增加很大的开销。

- Dmitry Bychenko

Answer 2

第一种方法总共进行了三个查找（n not in dic：、插入代码dic [n] =和返回dic [n]）。 在最坏情况下，第二种方法也进行了三次查找（检索尝试dic [n] =、插入dic [n] = 和返回dic [n]）， 此外还涉及异常处理。

如果一种方法执行与另一种方法相同的工作，并添加了一些东西，那显然它不可能更快，很可能会更慢。

考虑在场景中比较效率，当记忆化有更多机会被使用时-即多次运行函数以比较摊销复杂度。这样第二种方法的最坏情况发生的频率将会更少，从而你可以通过少进行一次查找来获得一些收益。

版本1：

def fibo(n, dic={}) :
    if n not in dic :
        if n in (0,1) :
            dic[n] = 1
        else :
            dic[n] = fibo(n-1)+fibo(n-2)
    return dic[ n ]

for i in range(10000):
    fibo(i)

版本2：

def fibo(n, dic={}) :
    try :
        return dic[n]
    except :
        if n in (0,1) :
            dic[n] = 1
        else :
            dic[n] = fibo(n-1)+fibo(n-2)
        return dic[ n ]

for i in range(10000):
    fibo(i)

测试如下：

C:\Users\Bartek\Documents\Python>python -m timeit -- "import version1"
1000000 次循环，最好的 3 次：每次 1.64 微秒

C:\Users\Bartek\Documents\Python>python -m timeit -- "import version2"
1000000 次循环，最好的 3 次：每次 1.6 微秒

当函数被更频繁地使用时，缓存会填充更多的值，从而降低异常的几率。

- BartoszKP