Python代码不理解

Question

题目描述

原来在计算斐波那契数时，效率太低，现在，我们将在其中存储斐波那契数。
当计算斐波那契数时，我们首先在缓存中查找它，如果它不在那里，
我们计算它并将它放入缓存，否则我们返回缓存的数。

看不懂memoized(f)

相关代码

def memoized(f):
    cache = {}
    def wrapped(k):
        v = cache.get(k)
        if v is None:
            v = cache[k] = f(k)
        return v
    return wrapped

@memoized
def fibonacci(n):
    if n in [0, 1]:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Answer 1

搜索了解一下python闭包跟装饰器。

memoized是一个装饰器，也就是闭包，它实现的功能是调用fibonacci函数之前，先检查自己的缓存中有没有现成的值，有就直接返回省去重复计算，没有就计算一次并缓存。

另外说一句，你这个斐波那契优化方法不是最佳的，因为你只缓存了你访问到的数值。比如你先求了第1000个斐波那契数，然后第一次求第800个的时候还是要一路递归计算。

其实第n个斐波那契数依赖于第n-1和n-2个斐波那契数，在计算任一斐波那契数的时候，应该把它前面的斐波那契数列按顺序都缓存好，这样以后取n以内的任意斐波那契数都不用计算了。