CODEWITHSUNDEEP
javaalgorithmrecursiondynamic-programming
Abhishek
Abhishek

Reputation: 380

Fibonacci Sequence using Cache

I am trying to make use of a cache to improve the performance of my Fibonacci method. However, it is still taking a lot of time to compute even fibonacci(40).

import java.util.Scanner;
public class FibWithCache {

    public static void main(String args[]) {
        System.out.println("Enter Fibonacci index: ");
        Scanner sc = new Scanner(System.in);
        int index = sc.nextInt();
        sc.close();

        System.out.println(fibonacci(index));
    }

    private static long fibonacci(int index) {

        long result = 0;
        long[] fibCache = new long[200];

        if(index==0)
            return 0;
        else if(index == 1)
            return 1;
        else if(fibCache[index] != 0)
            return fibCache[index];
        else {
            result = fibonacci(index-1) + fibonacci(index-2);
            fibCache[index] = result;
            return result;
        }
    }
}

Why am I unable to benefit from the cache?

Upvotes: 3

Views: 2310

Answers (3)

Himanshu Kumar
Himanshu Kumar

Reputation: 29

public class FibonacciCache {

    private int[] cache = new int[1000];
    
    public FibonacciCache(){
        // n de 1 = 1;
        cache[1] = 1;
    }

    public int fibonacciDe(int n){
        if(cache[n] != 0){
            return cache[n];
        }
    
        // n de 0 = 0
        if(n <= 0){
            return 0;
        }
                        
        int result = fibonacciDe(n-1) + fibonacciDe(n-2);
        cache[n] = result;
        return result;
    }

Upvotes: 1

ifma
ifma

Reputation: 3818

There should only be one instance to fibCache (it has to be static).

Upvotes: 3

NPE
NPE

Reputation: 500357

Hint: The issue is that each recursive call to fibonacci() has its own cache. For every call you create an empty cache, store something in it, and immediately discard it.

What you want is one cache shared by all the calls.

I'll let you figure out how best to do it. :)

Upvotes: 12

Related Questions