C++ memoization - Fibonacci function - map verus vector container execution time

Question

I'm trying to learn memoization in C++ and have implemented two Fibonacci functions using map and vector. I've submitted them to the Coursera data structures course. The vector implementation fails due to taking too much time and the map passes OK. As both implement memoization could anybody suggest why one fails and the other passes?

#include <iostream>
#include <map>
#include <iterator>
#include <vector>

using namespace std;

int fibonacci_fast_vector(int n)
{
    vector <int> cache;

    if(n<=1) {
        return n;
    }
    else if ((unsigned)n >= cache.size()) {
            cache.resize(n+1);
        }

    if(cache[n] != 0) {
        return cache[n];
    }

    // otherwise
    int ret=fibonacci_fast_vector(n-1)+fibonacci_fast_vector(n-2);
    cache[n]=ret;
    return ret;
}


int fibonacci_fast_map(int n)
{
    static map<int,int>memo;

    if(n<=1)
        return n;

    if(memo.count(n)>0) { /*if it is in the map return the element*/
        return memo[n];
    }

    // otherwise
    int ret=fibonacci_fast_map(n-1)+fibonacci_fast_map(n-2);
    memo[n]=ret;
    return ret;
}

int main() {
    int n = 0;
    std::cin >> n;

    std::cout << fibonacci_fast_map(n) << '\n';
    std::cout << fibonacci_fast_vector(n) << '\n';
    return 0;
}

Answer 1

I guess the problem is that your vector is not static. Put a static keyword or declare it in the global scope. This will reduce the huge performance time because you avoid many news and deletes. Also you can create with some initial size vector if you know the probable size for the same performance reason.