[Solved] Find out how to Implement Fibonacci Collection with Memoization in Java 8? ConcurrentHashMap Caching Instance

Hiya guys, if you’re questioning clear up the Fibonacci collection downside with memorization in Java then you have got come to the correct place. Up to now, I’ve shared recursive and iterative Fibonacci collection resolution and on this article, I’m going to point out you how one can enhance your resolution utilizing a method known as memorization which makes use of a cache to retailer the intermediate outcomes. It is a very helpful method to resolve Dynamic Programming issues just like the Knapsack downside. The advantage of Java is that it offers wealthy libraries which have lessons like ConcurrentHashMap which can be utilized as a cache to retailer these middleman outcomes as an alternative of re-computing them. This will drastically scale back the time to calculate the Nth Fibonacci quantity.

One of many major issues with the Fibonacci collection is that with the intention to calculate the Nth Fibonacci quantity you have to calculate N-1 and N-2 Fibonacci quantity and if you’re printing the complete collection then there’s a good probability that you’re doing it repeatedly. For instance, to print a collection of 100 Fibonacci numbers, it’s a must to regulate the fifth Fibonacci quantity 95 instances. 

There’s a good probability that you simply already know clear up this downside however on this article, I will present you a simple option to implement a neighborhood cache utilizing the ConcurrentHashMap and lambda expressions of Java 8.  

Since Java 8 Map now has a brand new means for atomically calculating a brand new worth in case a key’s absent, you need not do a null test after which insert the worth, excellent for a cache.  In an effort to clear up the Fibonacci collection utilizing Memoization, nicely construct a cache of beforehand calculated Fibonacci numbers. Probably the most simple method is to memorize all values in a cache. 

In an effort to construct the cache, we’ll use the newly added computeIfAbsetnt() methodology from the Map interface to calculate a brand new worth provided that we don’t have already got a price for a given key. On condition that this methodology is assured to execute atomically, and since we’re utilizing a ConcurrentHashMap, this cache is even thread-safe. 

By the way in which, if you’re new to Java or not acquainted with new options launched in Java, like enhancement in Map and different Assortment API in addition to Stream and Lambda Expression then I extremely advocate you to affix a complete Java course like The Full Java Masterclass by Tim Buchalaka on Udemy. This 80+ hour course is among the finest programs to be taught Java on-line. 

Find out how to Print Fibonacci Collection with Memoization in Java 8 Instance

Right here is our pattern Java program to implement the Fibonacci collection in Java 8. As I stated, It makes use of enhancements made in Java 8 to enhance the efficiency of the Fibonacci quantity generator, I imply computeIfAbsent() methodology added on Map class. 

Because the subsequent quantity within the Fibonacci collection is the sum of the earlier two numbers, the efficiency of the Fibonacci quantity generator could be drastically improved by caching the already calculated Fibonacci numbers.

As I stated, this method is named Memoization and it may be used to resolve many dynamic programming-based issues. For instance, you need to use this method to calculate factorial of enormous numbers which is in any other case taking large reminiscence and time. 

Btw, if you wish to be taught extra about Dynamic Programming and determine if an issue could be solved utilizing Dynamic Programming, I recommend you undergo a course like Grokking Dynamic Programming Sample on Educative. This will tremendously enhance your Dynamic Programming ability which is kind of essential for coding interviews. 

Anyway, right here is our full Java program which reveals the way you trigger ComputeIfAbsent and ConcurrentHashMap to resolve the Fibonacci downside in Java with Memoization. 

package deal take a look at;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
* Java ConcurrentHashMap computeIfAbsent Instance to resolve 
* Fibonacci collection with memoization.
*/
public class FibonacciSeriesWithMemoization{

    static Map<Integer, Lengthy> cache = new ConcurrentHashMap&lt;&gt;();

    public static void major(String[] args) {
        System.out.println("Calculating Fibonacci quantity with out Memoization");
        fibonacci(5);
     
        System.out.println("Calculating Fibonacci with Memoization");
        fibonacciWithMemoization(5);
    }

    public static lengthy fibonacci(int quantity) {
        if (quantity == 0) {
            return quantity;
        }

        if (quantity == 1) {
            return 1;
        }

        System.out.println("Calculating Fibonacci(" + quantity + ")");
        return fibonacci(quantity - 2) + fibonacci(quantity - 1);
    }

   public static lengthy fibonacciWithMemoization(int quantity) {
        if (quantity == 0) {
            return quantity;
        }
        if (quantity == 1) {
            return 1;
        }
        return cache.computeIfAbsent(quantity, (n) -&gt; {
            System.out.println("Not Present in Cache, Calculate Fibonacci("
                                  + n + ")");
            return fibonacciWithMemoization(quantity - 2) 
                                 + fibonacciWithMemoization(quantity - 1);
        });
    }

}

Output
run:
Calculating Fibonacci quantity with out Memoization
Calculating Fibonacci(5)
Calculating Fibonacci(3)
Calculating Fibonacci(2)
Calculating Fibonacci(4)
Calculating Fibonacci(2)
Calculating Fibonacci(3)
Calculating Fibonacci(2)
Calculating Fibonacci with Memoization
Not Present in Cache, Calculate Fibonacci(5)
Not Present in Cache, Calculate Fibonacci(3)
Not Present in Cache, Calculate Fibonacci(2)
Not Present in Cache, Calculate Fibonacci(4)

That is all about generate the Fibonacci collection in Java. You possibly can simply print collection within the console utilizing System.out.println() operate or you may retailer them in a Record.  On this tutorial, you have got realized how we will use Java 8 options to implement the Fibonacci collection with memoization simply like use ConcurerntHashMap as cache and use computeIfAbsent() methodology to insert values into Map implementations like ConcurrentHashMap or just HashMap.