Improve C++ Fibonacci series

问题:

I know that:

int fib(int n) 
{
    if (n == 0 || n == 1)
        return 1;

    return fib(n − 1)+ fib(n − 2);
}

when n=5，fib(5) evaluates as:

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Notice that each base element being used for several times, is there a way to use map to store the previous value and simply do fib(n − 1) + fib（n − 2)?

回答1:

In C++, the two solutions at your disposal that would save you time are the dynamic programming approach and the memoization approach.

Dynamic Programming

We just build a table from [1..n] and fill it in:

int fib(int n) 
{
    if (n <= 1)
        return n;

    std::vector<int> table(n + 1);
    table[0] = table[1] = 1;
    for (int i = 2; i <= n; ++i) {
        table[i] = table[i-1] + table[i-2];
    }    
    return table.back();
}

Memoization

Here, we implement fib as normal, but save off the intermediate steps:

int fib(int n) {
    static std::vector<int> table; // our cache
    if (n <= 1) {
        return n;
    }
    else if (n >= table.size()) {
        table.resize(n+1);
    }

    if (table[n] == 0) {
        // only recalc if we don't have a value
        table[n] = fib(n-1) + fib(n-2);
    }
    return table[n];
}

The more standard approach to memoization would involve a hash-table on the inputs - but in this case since we know that to compute fib(n) we also need fib(1) thru fib(n-1), a vector would be more efficient. Or do we?

Sublinear

We don't actually have to compute fib(1) thru fib(n-1) to get fib(n). We could do it directly:

int fib(int n) {
    const double sqrt5 = std::sqrt(5);
    const double phi = (1 + sqrt5) / 2;
    return (int)(std::pow(phi, n+1) / sqrt5 + 0.5);
}

Because math is cool.

回答2:

Yes. The primitive recursive solution takes a lot of time. The reason for this is that for each number calculated, it needs to calculate all the previous numbers more than once.

What makes it even worse is that with each fibonacci number you calculate in your list, you don't use the previous numbers you have knowledge of to speed up the computation – you compute each number "from scratch."

There are a few options to make this faster:

---

1. Create a list "from the bottom up"

The easiest way is to just create a list of fibonacci numbers up to the number you want. If you do that, you build "from the bottom up" or so to speak, and you can reuse previous numbers to create the next one. If you have a list of the fibonacci numbers [0, 1, 1, 2, 3], you can use the last two numbers in that list to create the next number.

This approach would look something like this:

>>> def fib_to(n):
...     fibs = [0, 1]
...     for i in range(2, n+1):
...         fibs.append(fibs[-1] + fibs[-2])
...     return fibs
...

Then you can get the first 20 fibonacci numbers by doing

>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

Or you can get the 17th fibonacci number from a list of the first 40 by doing

>>> fib_to(40)[17]
1597

---

2. Memoization (relatively advanced technique)

Another alternative to make it faster exists, but it is a little more complicated as well. Since your problem is that you re-compute values you have already computed, you can instead choose to save the values you have already computed in a dict, and try to get them from that before you recompute them. This is called memoization. It may look something like this:

>>> def fib(n, computed = {0: 0, 1: 1}):
...     if n not in computed:
...         computed[n] = fib(n-1, computed) + fib(n-2, computed)
...     return computed[n]

This allows you to compute big fibonacci numbers in a breeze:

>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675

This is in fact such a common technique that Python 3 includes a decorator to do this for you. I present to you, automatic memoization!

import functools

@functools.lru_cache(None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

This does pretty much the same thing as the previous function, but with all the computed stuff handled by the lru_cache decorator.

---

3. Just count up (a naïve iterative solution)

A third method, as suggested by Mitch, is to just count up without saving the intermediary values in a list. You could imagine doing

>>> def fib(n):
...     a, b = 0, 1
...     for _ in range(n):
...         a, b = b, a+b
...     return a

---

I don't recommend these last two methods if your goal is to create a list of fibonacci numbers. fib_to(100) is going to be a lot faster than [fib(n) for n in range(101)] because with the latter, you still get the problem of computing each number in the list from scratch.

Checkout this for different algorithms: http://www.nayuki.io/page/fast-fibonacci-algorithms

Credits: kqr

回答3:

Of course you can!

Very basic example in python:

cache = {}

def fib(n):
    if n <= 1:
        return n
    if n not in cache:
        cache[n] = fib(n-1) + fib(n-2)
    return cache[n]

回答4:

Efficient Fibonacci Series solution with dynamic programming.

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int fib[n];
    fib[0]=fib[1]=1;
    for(int i = 2;i<n;i++)
    {
        fib[i]=fib[i-1]+fib[i-2];
    }
    for(int i = 0;i<n;i++)
    {
        cout<<fib[i]<<" ";
    }
    return 0;
}
/*input and output
5
1 1 2 3 5
Process returned 0 (0x0)   execution time : 2.557 s
Press any key to continue.*/