即使使用记忆，我的程序也不能运行那么快

Question

我在欧拉项目上尝试了一个问题，我需要找到 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_cache 模块时运行它只需要不到一秒的时间。

Answer 1

您不应该计算斐波那契数列，即使是动态规划也不应该。既然斐波那契数列满足常系数常阶的线性递推关系，那么它们的和数列也是。

绝对不要缓存所有值。这会给你带来不必要的内存消耗。当递归顺序不变时，你只需要记住与递归顺序一样多的前面的术语。

此外，还有一种方法可以将常量阶的递归转化为一阶的系统递归。后者的解由矩阵的幂给出。对于 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。我们有 X_0。要乘以 A^n 我们可以做 exponentiation by squaring.

Answer 2

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

fibonacci_cache = {}

此行位于函数内部意味着每次调用 fibonacci_memo 时您都在清空缓存。

Answer 3

我不确定你是怎么花近一秒钟的时间的。这是没有幻想的记忆版本：

class fibs(object):
    def __init__(self):
        self.thefibs = {0:0, 1:1}

    def __call__(self, n):
        if n not in self.thefibs:
            self.thefibs[n] = self(n-1)+self(n-2)
        return self.thefibs[n]

dog = fibs()

sum([dog(i) for i in range(40) if dog(i) < 4000000])

Answer 4

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

我们可以看到，“智能”方法不仅快一个数量级，而且似乎更符合事实（感谢@NotDijkstra），即 Python 大整数使用比简单乘法更好.

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)

即使使用记忆，我的程序也不能运行那么快

My program can't run that fast even with memoization

python

fibonacci