我的程序即使有备忘录也不能运行那么快

Question

我在euler项目上尝试了一个问题，我需要找到所有斐波那契项的总和，小于400万。这花了我很长时间，但后来我发现我可以用回忆录来做，但似乎还需要很长时间。经过大量研究，我发现我可以使用一个名为lru_cache的内置模块。我的问题是：为什么它没有回忆录那么快

这是我的密码：

from functools import lru_cache


@lru_cache(maxsize=1000000)
def fibonacci_memo(input_value):
    global value
    fibonacci_cache = {}
    if input_value in fibonacci_cache:
        return fibonacci_cache[input_value]
    if input_value == 0:
        value = 1
    elif input_value == 1:
        value = 1
    elif input_value > 1:
        value = fibonacci_memo(input_value - 1) + fibonacci_memo(input_value - 2)
        fibonacci_cache[input_value] = value
    return value


def sumOfFib():
    SUM = 0
    for n in range(500):
        if fibonacci_memo(n) < 4000000:
            if fibonacci_memo(n) % 2 == 0:
                SUM += fibonacci_memo(n)
    return SUM


print(sumOfFib())

顺便说一下，代码是有效的。当我使用lru_缓存模块时，运行它不到一秒钟

Answer 1

为了完整起见，这里是@NotDijkstra的答案中描述的一般思想的实现，加上我拙劣的优化，包括用整数算法实现的“封闭形式”解决方案

我们可以看到，“智能”方法不仅比简单乘法快一个数量级，而且与Python大整数比简单乘法使用得更好这一事实（感谢@NotDijkstra）的伸缩性更好

import numpy as np
import operator as op
from simple_benchmark import BenchmarkBuilder, MultiArgument
B = BenchmarkBuilder()

def pow(b,e,mul=op.mul,unit=1):
    if e == 0:
        return unit
    res = b
    for bit in bin(e)[3:]:
        res = mul(res,res)
        if bit=="1":
            res = mul(res,b)
    return res

def mul_fib(a,b):
    return (a[0]*b[0]+5*a[1]*b[1])>>1 , (a[0]*b[1]+a[1]*b[0])>>1

def fib_closed(n):
    return pow((1,1),n+1,mul_fib)[1]

def fib_mat(n):
    return pow(np.array([[1,1],[1,0]],'O'),n,op.matmul)[0,0]

def fib_sequential(n):
    t1,t2 = 1,1
    for i in range(n-1):
        t1,t2 = t2,t1+t2
    return t2

def sum_fib_direct(n):
    t1,t2,res = 1,1,1
    for i in range(n):
        t1,t2,res = t2,t1+t2,res+t2
    return res
    
def sum_fib(n,method="closed"):
    if method == "direct":
        return sum_fib_direct(n)
    return globals()[f"fib_{method}"](n+2)-1

methods = "closed mat sequential direct".split()

def f(method):
    def f(n):
        return sum_fib(n,method)
    f.__name__ = method
    return f

for method in methods:
    B.add_function(method)(f(method))

B.add_arguments('N')(lambda:(2*(1<<k,) for k in range(23)))

r = B.run()
r.plot()

import matplotlib.pylab as P
P.savefig(fib.png)

Answer 2

另一个答案确实是计算斐波那契序列的正确方法，但你也应该知道为什么你的记忆不起作用。具体而言：

fibonacci_cache = {}

这一行位于函数内部意味着每次调用fibonacci_memo时都会清空缓存

Answer 3

你不应该计算斐波那契序列，甚至不应该用动态规划。由于斐波那契序列满足常系数、常阶的线性递推关系，因此它们的和序列也将满足线性递推关系

绝对不要缓存所有的值。这会给你不必要的内存消耗。当重复出现的顺序不变时，您只需记住重复出现顺序中的前几项即可

此外，还有一种方法可以将常阶循环转化为系统一阶循环。后者的解由矩阵的幂给出。这为n的大值提供了更快的算法。不过，每一步都会更加昂贵。因此，最好的方法将两者结合使用，第一种方法用于n的小值，第二种方法用于大输入

O（n）对求和使用递归

表示S_n=F_0+F_1+...+F_n第一个斐波那契数的和F_0,F_1,...,F_n

注意

• S_{n+1}-S_n=F_{n+1}
• S_{n+2}-S_{n+1}=F_{n+2}
• S_{n+3}-S_{n+2}=F_{n+3}

因为F_{n+3}=F_{n+2}+F_{n+1}我们得到了S_{n+3}-S_{n+2}=S_{n+2}-S_n。所以

S_{n+3}=2S_{n+2}-S_n

初始条件为S_0=F_0=1、S_1=F_0+F_1=1+1=2和S_2=S_1+F_2=2+2=4

您可以做的一件事是自下而上计算S_n，在每一步只记住前三项的值。您不需要记住S_k的所有值，从k=0到k=n。这将为您提供一个具有O(1)内存量的O(n)算法

---

O（ln（n））通过矩阵求幂

您还可以通过以下方式获得O(ln(n))算法：

调用X_n作为包含组件S_{n+2},S_{n+1},S_{n}的列向量

所以，上面的递推式给出了递推式

X_{n+1}=AX_n

其中A是矩阵

[
 [2,0,-1],
 [1,0,0],
 [0,1,0],
]

因此，X_n=A^nX_0。我们有{}。要乘以A^n，我们可以做exponentiation by squaring