我的斐波那契代码与显式Memoization实现的性能差异原因探究

简单递归生成斐波那契数存在大量重复计算，我用记忆化（Memoization）技术优化，但同样基于字典缓存，我的代码在N较大时性能差距明显，以下是具体对比和原因分析：

我的实现 #

代码 #

import timeit

my_dict = {}

def fibonacci(n):
    """ To print the fibonacci series efficiently """
    if n == 1:
        x = 0
        my_dict[n] = x
        return x

    elif n == 2:
        fibonacci(1)
        x = 1
        my_dict[n] = x
        return x

    elif n == 3:
        fibonacci(2)
        x = 1
        my_dict[n] = x
        return x

    elif n > 3:
        fibonacci(n-1)
        x = my_dict[n-2] + my_dict[n-1]
        my_dict[n] = x
        return x

number = int(input("Enter N: "))

t = timeit.timeit(lambda: fibonacci(number), number=10)

fib = fibonacci(number)

print(f"Number: {fib}\n Time: {t:.32f}")

运行输出 #

$ python 06_fibo_dict.py
Enter N: 100
Number: 218922995834555169026
Time: 0.00059320009313523769378662109375

$ python 06_fibo_dict.py
Enter N: 200
Number: 173402521172797813159685037284371942044301
Time: 0.00105599989183247089385986328125

网上的实现 #

代码 #

import timeit

def fibonacci(n, cache={}):
    if n in cache:
        return cache[n]

    if n == 1:
        result = 0

    elif n == 2:
        result = 1

    else:
        result = fibonacci(n-1) + fibonacci(n-2)

    cache[n] = result
    return result

number = int(input("Enter N: "))

t = timeit.timeit(lambda: fibonacci(number), number=10)

fib = fibonacci(number)

print(f"Number: {fib}\n Time: {t:.32f}")

运行输出 #

$ python 07_fibo_memo.py
Enter N: 100
Number: 218922995834555169026
Time: 0.00000469991937279701232910156250

$ python 07_fibo_memo.py
Enter N: 200
Number: 173402521172797813159685037284371942044301
Time: 0.00000709993764758110046386718750

性能差距的核心原因 #

1. 缓存检查时机错误 #

网上的代码第一时间就检查缓存，如果目标n已经在缓存里，直接返回结果，完全跳过后续的分支判断和递归逻辑；而你的代码没有做前置缓存检查，哪怕缓存里已经有n的结果，每次调用还是会走一遍n1、n2等分支判断，甚至触发不必要的递归，平白增加了大量无意义的操作。

2. 冗余的递归调用 #

你的代码逻辑存在强制递归触发：比如计算n=2时会调用fibonacci(1)，n=3时调用fibonacci(2)，n>3时调用fibonacci(n-1)——哪怕这些值已经在缓存里，你还是会触发递归调用，而递归本身就有函数调用的开销。网上的代码只在需要计算新值时才递归，且递归过程中会自动利用缓存避免重复计算，没有多余的递归触发。

3. 多次运行时的缓存利用效率 #

用timeit运行10次时，网上的代码第一次计算完后，后续9次调用直接从缓存取结果，几乎不耗时；而你的代码每次调用都会触发从n到1的递归遍历（哪怕缓存存在），相当于每次都要重新走一遍流程，这也是时间差距巨大的关键原因。

4. 全局变量的额外开销 #

你的缓存是全局字典my_dict，全局变量的访问速度比函数默认参数里的局部字典稍慢，虽然这不是主要因素，但也会带来微小的性能损耗。

内容的提问来源于stack exchange，提问作者N00B_141