Discuss the implementation of memoization in Scala and provide an example.?

Memoization is a technique to optimize a function by caching the results of expensive function calls and returning the cached results when the same input occurs again. In Scala, you can implement memoization using various data structures, such as HashMap or TrieMap. In this answer, I’ll provide an implementation using the Scala ‘collection.mutable.HashMap.

Let’s consider a naive implementation of the Fibonacci function:

def fib(n: Int): BigInt = {
  if (n <= 1) BigInt(n)
  else fib(n - 1) + fib(n - 2)
}

This function has terrible performance for large numbers because it recomputes the same Fibonacci numbers multiple times. We will implement memoization to optimize this function.

Here’s an example of a memoized version of the Fibonacci function:

import scala.collection.mutable.HashMap

object MemoFib {
  val cache: HashMap[Int, BigInt] = HashMap(0 -> 0, 1 -> 1)

  def apply(n: Int): BigInt = {
    if (cache.contains(n)) {
      cache(n)
    } else {
      val result = apply(n - 1) + apply(n - 2)
      cache += (n -> result)
      result
    }
  }
}

def fibMemo(n: Int): BigInt = MemoFib(n)

In this case, we created an object called ‘MemoFib‘ that holds a mutable HashMap called ‘cache‘. The cache stores the Fibonacci numbers we’ve seen so far. The initial values include 0 and 1, which correspond to the base cases of the Fibonacci function.

The ‘MemoFib.apply‘ method checks if the cache already contains the result for the given input ‘n‘. If it does, we simply return the cached result, thus avoiding redundancy in the computation. If it doesn’t, we compute the result, store it in the cache, and return it.

We also defined a wrapper function ‘fibMemo‘ that uses the ‘MemoFib‘ object to compute Fibonacci numbers.

Now let’s test the performance of the ‘fib‘ and ‘fibMemo‘ functions:

import java.time.Instant

val testNum = 100

val startTime1 = Instant.now()
val res1 = fib(testNum)
val endTime1 = Instant.now()

val startTime2 = Instant.now()
val res2 = fibMemo(testNum)
val endTime2 = Instant.now()

println(s"fib    ($testNum) = $res1, Time: ${endTime1.toEpochMilli - startTime1.toEpochMilli}ms")
println(s"fibMemo($testNum) = $res2, Time: ${endTime2.toEpochMilli - startTime2.toEpochMilli}ms")

The output will show that the memoized version is significantly faster than the naive implementation.

Although this implementation offers a significant performance boost for memoizable functions, it does not come without memory overhead. The HashMap will continue to store results indefinitely, and depending on the size and complexity of the problem space, this can lead to excessive memory usage. Alternatively, you could consider using a fixed-size cache (such as ‘LinkedHashMap‘) or a cache with an eviction policy (e.g., LRU cache).