CODEWITHSUNDEEP
javaalgorithmdynamic-programming
beastlyCoder
beastlyCoder

Reputation: 2401

Memozied Fibonacci not Running vs Regular Fibonacci Solution

So I am learning dynamic programming, and I am trying to test my memoized solution vs the normal fibonacci solution. When I put in a fairly large number like 43, my memoized solution takes forever to run, while the normal solution, runs after 5 - 6 seconds. Does this mean my memoized solution isn't actually storing the already seen results?

Here is my traditional solution:

public static int fibonacci(int i) 
{
    if(i == 0) 
    {
        return 0;
    }
    if(i <= 2) 
    {
        return 1;
    }
    return fibonacci(i - 1) + fibonacci(i - 2);
}

Memoized Solution:

public static int fibonacci(int n) 
{
    Map<Integer, Integer> memo = new HashMap<>();
    if(n == 0) 
    {
        return 0;
    }
    if(n <= 2)
    {
        return 1;
    }
    if(memo.containsKey(n))
    {
        return memo.get(n);
    }
    int result = fibonacci(n - 1) + fibonacci(n - 2);
    memo.put(n, result); 
    
    return result;
}

Main method:

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    scanner.close();
    System.out.println(fibonacci(n));
}

Any explanation as to why this is the case would be greatly appreciated :)

Upvotes: 0

Views: 61

Answers (1)

beastlyCoder
beastlyCoder

Reputation: 2401

Thanks to @shmosel I was able to figure out that during my 'memoized' solution, I was calling a new map everytime the method was called causing it to be extremely slow! I circumvented this by adding the map as an instance variable as follows: 

private static Map<Integer, Integer> memo = new HashMap<>();

public static int fibonacci(int n) 
{
    if(n == 0) 
    {
        return 0;
    }
    if(n <= 2)
    {
        return 1;
    }
    if(memo.containsKey(n))
    {
        return memo.get(n);
    }
    int result = fibonacci(n - 1) + fibonacci(n - 2);
    memo.put(n, result); 

    return result;
}

This has dramatically increased performance.

Upvotes: 4

Related Questions