Python Memoization手动缓存

Question

我正在构建一个带记忆的Python Fibonacci函数的手动缓存版本，我注意到我没有在递归调用中将缓存作为参数传递。

然而，该函数仍然在某种意义上工作，它比非memoized版本快得多。

当我将缓存作为函数参数添加时，算法的速度更快，但不是很明显。

有没有人能帮我解释一下为什么第一个版本是有效的，以及第二个版本是否更正确？

import time


def fib_cache(n, cache={}):
    if n in cache:
        return cache[n]
    if n == 0 or n == 1:
        return n
    result = fib_cache(n - 1) + fib_cache(n - 2)
    cache[n] = result
    return result


def fib_cache2(n, cache={}):
    if n in cache:
        return cache[n]
    if n == 0 or n == 1:
        return n
    result = fib_cache2(n - 1, cache) + fib_cache2(n - 2, cache)
    cache[n] = result
    return result

start = time.perf_counter()
fib_cache(30)
end = time.perf_counter()
print("Version 1. Seconds taken: {:.5f}".format(end - start))

start = time.perf_counter()
fib_cache2(30)
end = time.perf_counter()
print("Version 2. Seconds taken: {:.5f}".format(end - start))

Answer 1

这是因为Python中的def只执行一次，并且默认变量只初始化一次。在引用类型的情况下，这可能会导致错误/意外行为。一种解决方法是：

def fib_cache3(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n == 0 or n == 1:
        return n
    result = fib_cache3(n - 1, cache) + fib_cache3(n - 2, cache)
    cache[n] = result
    return result

这个版本的优点是，它不依赖于引用类型的默认初始化，并且它允许在函数执行后进行垃圾回收。