为什么我的代码在查找斐波那契和时速度很慢？

Question

我正在为 project Euler Questions in this repo 写答案但我的解决方案存在一些性能问题

问题二： 斐波那契数列中的每个新项都是通过添加前两项生成的。从 1 和 2 开始，前 10 项将是： 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 考虑斐波那契数列中不超过四百万的项，求偶数项之和

我的解决方案是

func solution2()
{
    func fibonacci(number: Int) -> (Int)
    {
        if number <= 1
        {
            return number
        }
        else
        {
            return fibonacci(number - 1) + fibonacci(number - 2)
        }
    }

    var sum = 0

    print("calculating...")
    for index in 2..<50
    {
        print (index)
        if (fibonacci(index) % 2 == 0)
        {
            sum += fibonacci(index)
        }
    }

    print(sum)
}

我的问题是，为什么在第 42 次迭代后它变得非常慢，我想按问题所说的那样用 4000000 来做，有帮助吗？

解决方案 2

func solution2_fast()
{
    var phiOne : Double = (1.0 + sqrt(5.0)) / 2.0
    var phiTwo : Double = (1.0 - sqrt(5.0)) / 2.0

    func findFibonacciNumber (nthNumber : Double) -> Int64
    {
        let nthNumber : Double = (pow(phiOne, nthNumber) - (pow(phiTwo, nthNumber))) / sqrt(5.0)
        return Int64(nthNumber)
    }

    var sum : Int64 = 0

    print("calculating...")
    for index in 2..<4000000
    {
        print (index)
        let f = findFibonacciNumber(Double(index))
        if (f % 2 == 0)
        {
            sum += f
        }
    }

    print(sum)

}

Answer 1

第二个解决方案似乎更快（呃），尽管 Int64 不足以存储结果。 2..91 的斐波那契数之和为 7,527,100,471,027,205,936，但 Int64 中可存储的最大数字为 9,223,372,036,854,775,807。为此，您需要使用其他一些类型，例如 BigInteger

Answer 2

因为你用的是递归，在memory.If你第42次迭代的时候缓存了，可能你记忆里有那么多斐波那契函数，recursive.So不适合递归，您可以将结果存储在数组中，而不是 swift.

的原因

Answer 3

这是两种不同的答案

func solution2_recursive()
{
    func fibonacci(number: Int) -> (Int)
    {
        if number <= 1
        {
            return number
        }
        else
        {
            return fibonacci(number - 1) + fibonacci(number - 2)
        }
    }
    var sum = 0
    print("calculating...")
    for index in 2..<50
    {
        print (index)
        let f = fibonacci(index)

        if( f < 4000000)
        {
            if (f % 2 == 0)
            {
                sum += f
            }
        }
        else
        {
            print(sum)
            return
        }
    }
}

解决方案 2

func solution2()
{
    var phiOne : Double = (1.0 + sqrt(5.0)) / 2.0
    var phiTwo : Double = (1.0 - sqrt(5.0)) / 2.0

    func findFibonacciNumber (nthNumber : Double) -> Int64
    {
        let nthNumber : Double = (pow(phiOne, nthNumber) - (pow(phiTwo, nthNumber))) / sqrt(5.0)
        return Int64(nthNumber)
    }

    var sum : Int64 = 0

    print("calculating...")
    for index in 2..<50
    {
        let f = findFibonacciNumber(Double(index))
        if(f < 4000000)
        {
            if (f % 2 == 0)
            {
                sum += f
            }
        }
        else
        {
            print(sum)
            return
        }
    }
}

Answer 4

PE题最重要的是思考它在问什么。

这不是要求您生成所有小于 4000000 的斐波那契数 F(n)。它要求您生成所有小于 4000000 的偶数 F(n) 的总和。

考虑所有 F(n) 的总和，其中 F(n) < 10。

1 + 2 + 3 + 5 + 8

我可以通过计算 F(1)，然后是 F(2)，然后是 F(3)，依此类推...然后在将它们相加之前检查它们是否小于 10。

或者我可以存储两个变量...

F1 = 1
F2 = 2

总共...

Total = 3

现在我可以把它变成一个 while 循环并完全失去递归。事实上，我正在做的最复杂的事情是将两个数字加在一起...

我想到了这个...

func sumEvenFibonacci(lessThan limit: Int) -> Int {
    // store the first two Fibonacci numbers
    var n1 = 1
    var n2 = 2

    // and a cumulative total
    var total = 0

    // repeat until you hit the limit
    while n2 < limit {
        // if the current Fibonacci is even then add to total
        if n2 % 2 == 0 {
            total += n2
        }

        // move the stored Fibonacci numbers up by one.
        let temp = n2
        n2 = n2 + n1
        n1 = temp
    }

    return total
}

它在几分之一秒内运行。

sumEvenFibonacci(lessThan: 4000000)

找到正确答案。

事实上这... sumEvenFibonacci(lessThan: 1000000000000000000) 运行大约半秒。

为什么我的代码在查找斐波那契和时速度很慢？

why my code is slow when finding Fibonacci sum?

macos

xcode

fibonacci

ios

swift