Python代码不理解

Question

题如下

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

为什么我的代码会超时，还有更好的办法吗（如果不用lru_cache的话）

def fibonacci(n):
    l = [0, 1]
    m = n
    while 1:
        if m > 0:
            l.append(sum(l[-2:]))
            m-=1
        if m == 0:
            break
    return l[n]

或者解释1下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

1. 简单介绍一下python计算程序运行时间的方法，引入time模块，在程序运行前后调用一次perf_counter()，两次时间相减就是程序运行的秒数
2. 这里fib2是你的代码，fib4是利用装饰器写的代码，fib3是我模拟fib2使用全局变量作为缓存写的代码
3. 这里以计算一次第300个斐波那契数，计算一次第350个数为例，比较fib2、3、4的运行时间，运行结果如下：

可以看到fib2的初次运行时间比fib3、4的运行时间快，但是fib3、4有缓存机制，在重复计算上几乎不耗费时间。
我猜测，该题的目的其实就是让你写fib3这样的代码（题目要求使用缓存），而题目的测试用例也会类似我这样的重复调用的测试方法来测试你代码的运行时间，纯猜测。
本来想讲一下fib4的语法，但一篇评论可能装不下，只能简单说两句，fib4的原理和fib3是一样的，只不过用了装饰器@的语法，让每次调用fib4时先调用@后面的方法，然后再在@里面调用fib4，而这个过程中写在@后面的函数里面的局部变量会一直存在（声明周期等于这个装饰函数，而不是像普通的局部变量用完就没了），所以就形成了类似全局变量一样的缓存机制，本质上和fib3的逻辑没有区别

import time

def fib2(n):
    l = [0, 1]
    m = n
    while 1:
        if m > 0:
            l.append(sum(l[-2:]))
            m-=1
        if m == 0:
            break
    return l[n]

global_cash = {0:0,1:1}
def fib3(n):
    v = global_cash.get(n)
    if v is None:
        v = global_cash[n] = fib3(n-1)+fib3(n-2)
    return v

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 fib4(n):
    if n in [0, 1]:
        return n
    return fib4(n - 1) + fib4(n - 2)


start =time.perf_counter()
fib2(300)
end = time.perf_counter()
print('fib2(300): Running time: %s Seconds'%(end-start))

start =time.perf_counter()
fib3(300)
end = time.perf_counter()
print('fib3(300): Running time: %s Seconds'%(end-start))

start =time.perf_counter()
fib4(300)
end = time.perf_counter()
print('fib4(300): Running time: %s Seconds'%(end-start))

start =time.perf_counter()
fib2(300)
end = time.perf_counter()
print('again:fib2(300): Running time: %s Seconds'%(end-start))

start =time.perf_counter()
fib3(300)
end = time.perf_counter()
print('again:fib3(300): Running time: %s Seconds'%(end-start))

start =time.perf_counter()
fib4(300)
end = time.perf_counter()
print('again:fib4(300): Running time: %s Seconds'%(end-start))