Monday, May 8, 2023

[Solved] How to Implement Fibonacci Series with Memoization in Java 8? ConcurrentHashMap Caching Example

Hello guys, if you are wondering how to solve the Fibonacci series problem with memorization in Java then you have come to the right place. In the past, I have shared recursive and iterative Fibonacci series solution and in this article, I am going to show you how you can improve your solution using a technique called memorization which uses a cache to store the intermediate results. This is a very useful technique to solve Dynamic Programming problems like the Knapsack problem. The good thing about Java is that it provides rich libraries which have classes like ConcurrentHashMap which can be used as a cache to store these intermediary results instead of re-computing them. This can drastically reduce the time to calculate the Nth Fibonacci number.

If you are doing programming for some time or just started with programming there is a good chance that you heard about the Fibonacci series. It's one of the basic programming exercises which many of us used to learn Programming. 

One of the main problems with the Fibonacci series is that in order to calculate the Nth Fibonacci number you need to calculate N-1 and N-2 Fibonacci number and if you are printing the full series then there is a good chance that you are doing it repeatedly. For example, to print a series of 100 Fibonacci numbers, you have to regulate the 5th Fibonacci number 95 times. 

This is ok if you have to just print 100 Fibonacci number and you may not notice a difference but if you have to print 1 million numbers then this becomes a big problem and it may take hours to print the series but if you use the cache, you can drastically cut down the execution time. 

There is a good chance that you already know how to solve this problem but in this article, I'll show you an easy way to implement a local cache using the ConcurrentHashMap and lambda expressions of Java 8.  

Since Java 8 Map now has a new way for atomically calculating a new value in case a key is absent, you don't need to do a null check and then insert the value, perfect for a cache.  In order to solve the Fibonacci series using Memoization, well build a cache of previously calculated Fibonacci numbers. The most straightforward technique is to memorize all values in a cache. 

In order to build the cache, we'll use the newly added computeIfAbsetnt() method from the Map interface to calculate a new value only if we don’t already have a value for a given key. Given that this method is guaranteed to execute atomically, and since we’re using a ConcurrentHashMap, this cache is even thread-safe. 

By the way, if you are new to Java or not familiar with new features introduced in Java, like enhancement in Map and other Collection API as well as Stream and Lambda Expression then I highly recommend you to join a comprehensive Java course like The Complete Java Masterclass by Tim Buchalaka on Udemy. This 80+ hour course is one of the best courses to learn Java online. 





How to Print Fibonacci Series with Memoization in Java 8 Example

Here is our sample Java program to implement the Fibonacci series in Java 8. As I said, It uses enhancements made in Java 8 to improve the performance of the Fibonacci number generator, I mean computeIfAbsent() method added on Map class. 

Since the next number in the Fibonacci series is the sum of the previous two numbers, the performance of the Fibonacci number generator can be drastically improved by caching the already calculated Fibonacci numbers.

As I said, this technique is known as Memoization and it can be used to solve many dynamic programming-based problems. For example, you can use this technique to calculate factorial of large numbers which is otherwise taking huge memory and time. 

Btw, if you want to learn more about Dynamic Programming and how to identify if a problem can be solved using Dynamic Programming, I suggest you go through a course like Grokking Dynamic Programming Pattern on Educative. This can greatly improve your Dynamic Programming skill which is quite important for coding interviews. 

Fibonacci Series with Memoization in Java 8 using ConcurrentHashMap as Cache [Example]


Anyway, here is our complete Java program which shows how you cause ComputeIfAbsent and ConcurrentHashMap to solve the Fibonacci problem in Java with Memoization. 
package test;

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

/**
* Java ConcurrentHashMap computeIfAbsent Example to solve 
* Fibonacci series with memoization.
*/
public class FibonacciSeriesWithMemoization{

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

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

    public static long fibonacci(int number) {
        if (number == 0) {
            return number;
        }

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

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

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

}

Output
run:
Calculating Fibonacci number without 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 Found in Cache, Calculate Fibonacci(5)
Not Found in Cache, Calculate Fibonacci(3)
Not Found in Cache, Calculate Fibonacci(2)
Not Found in Cache, Calculate Fibonacci(4)


That's all about how to generate the Fibonacci series in Java. You can easily print series in the console using System.out.println() function or you can store them in a List.  In this tutorial, you have learned how we can use Java 8 features to implement the Fibonacci series with memoization easily like how to use ConcurerntHashMap as cache and how to use computeIfAbsent() method to insert values into Map implementations like ConcurrentHashMap or simply HashMap.


Other Resources for Coding Interviews:
Thanks for reading this article so far. If you like this Fibonacci solution with memorization and my explanation then please share them with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you are preparing for coding interviews and need resources to practice Dynamic Programming problems then I suggest you check out Grokking Dynamic Programming Patterns for Coding Interviews on Educative. It's an excellent, interactive course to build your Dynamic programming skill and you can do this and many more interactive courses for coding interviews for just $14.9 per month. I highly recommend this to anyone preparing for coding interviews

By javin paul at May 08, 2023
Labels: coding , Coding Interview Question , Coding problems , Java 8 , programming

1 comment :

Anonymous said...

Interesting choice, CHM is really good for caching.

June 4, 2022 at 4:41 AM

Post a Comment

Subscribe to: Post Comments ( Atom )