Python 记忆化手动缓存

Question

我正在构建记忆化 Python 斐波那契函数的手动缓存版本，我注意到我没有将缓存作为递归调用中的参数传递。

但是，该函数仍然有效，因为它比非记忆版本快得多。

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

有人可以帮我理解为什么第一个版本有效，而 if/whether 第二个版本更正确吗？

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只执行了一次，默认变量只初始化了一次。在引用类型的情况下，这可能导致 bugs/unexpected 行为。一种解决方法是：

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

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

Python 记忆化手动缓存

Python Memoization Manual Caching

python

memoization