How do you use memoization to speed up your algorithms?

2 How does memoization work?

Memoization works by using a data structure, such as a hash table, an array, or a map, to store the input-output pairs of a function. The data structure acts as a lookup table that can be accessed by the function whenever it needs to return a value for a given input. The function checks if the input is already in the data structure, and if so, returns the corresponding output. If not, it computes the output, stores it in the data structure, and returns it. The data structure can be either local or global, depending on the scope and lifetime of the function and its inputs.

3 How to implement memoization in Python?

Python has a built-in decorator called @lru_cache that can memoize any function with hashable inputs. The decorator wraps the function with a Least Recently Used (LRU) cache that can store up to a specified number of input-output pairs. The cache evicts the least recently used pair when it reaches its maximum size. To use the decorator, you simply need to import it from the functools module and apply it to your function definition. For example, here is how you can memoize a recursive function that calculates the nth Fibonacci number:

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
  if n < 2:
    return n
  else:
    return fib(n-1) + fib(n-2)        

4 How to implement memoization in JavaScript?

JavaScript does not have a built-in memoization feature, but you can create your own memoization function that takes another function as an argument and returns a memoized version of it. The memoization function can use a closure to create a private cache object that stores the input-output pairs of the original function. The memoized function can then check if the input is already in the cache, and if so, return the cached output. If not, it can call the original function, store the output in the cache, and return it. For example, here is how you can memoize a recursive function that calculates the factorial of a number:

function memoize(fn) {
  const cache = {};
  return function (n) {
    if (n in cache) {
      return cache[n];
    } else {
      const result = fn(n);
      cache[n] = result;
      return result;
    }
  };
}
function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
const memoizedFactorial = memoize(factorial);        

5 How to implement memoization in Java?

Java does not have a built-in memoization feature, but you can use a HashMap or a ConcurrentHashMap to store the input-output pairs of a function. The HashMap or the ConcurrentHashMap can act as a cache that can be accessed by the function whenever it needs to return a value for a given input. The function can check if the input is already in the map, and if so, return the corresponding output. If not, it can compute the output, store it in the map, and return it. The choice of the map depends on whether the function is thread-safe or not. For example, here is how you can memoize a recursive function that calculates the nth Fibonacci number:

import java.util.HashMap;
import java.util.concurrent.ConcurrentHashMap;
public class Memoization {
  // Using HashMap for a non-thread-safe function
  private static HashMap<Integer, Integer> fibCache = new HashMap<>();
  public static int fib(int n) {
    if (n < 2) {
      return n;
    } else {
      if (fibCache.containsKey(n)) {
        return fibCache.get(n);
      } else {
        int result = fib(n - 1) + fib(n - 2);
        fibCache.put(n, result);
        return result;
      }
    }
  }
  // Using ConcurrentHashMap for a thread-safe function
  private static ConcurrentHashMap<Integer, Integer> factCache = new ConcurrentHashMap<>();
  public static int fact(int n) {
    if (n == 0) {
      return 1;
    } else {
      if (factCache.containsKey(n)) {
        return factCache.get(n);
      } else {
        int result = n * fact(n - 1);
        factCache.put(n, result);
        return result;
      }
    }
  }
}