Memoization

Memoization is the caching of a function result so a repeated call returns the stored answer. The function then computes each distinct input only once.

A repeated call computes once

The first call computes the square and stores it. The second call finds the stored answer and the counter stays at one.

var calls = 0
val cache = scala.collection.mutable.Map.empty[Int, Int]
def square(x: Int): Int =
  cache.getOrElseUpdate(x, {
    calls += 1
    x * x
  })
@main def main(): Unit =
  println(square(4))
  println(square(4))
  println(calls)

New inputs compute once each

Two distinct inputs each run the computation a single time. The repeated third call adds nothing to the counter.

var calls = 0
val cache = scala.collection.mutable.Map.empty[Int, Int]
def square(x: Int): Int =
  cache.getOrElseUpdate(x, {
    calls += 1
    x * x
  })
@main def main(): Unit =
  println(square(3))
  println(square(4))
  println(square(3))
  println(calls)

The cache holds two answers

After three calls the cache size is two, one entry per distinct input. A lookup then returns the stored square directly.

var calls = 0
val cache = scala.collection.mutable.Map.empty[Int, Int]
def square(x: Int): Int =
  cache.getOrElseUpdate(x, {
    calls += 1
    x * x
  })
@main def main(): Unit =
  println(square(3))
  println(square(4))
  println(square(3))
  println(cache.size)
  println(cache(4))

Example

var calls = 0
val cache = scala.collection.mutable.Map.empty[Int, Int]
def fib(n: Int): Int =
  cache.getOrElseUpdate(n, {
    calls += 1
    if n <= 1 then n else fib(n - 1) + fib(n - 2)
  })
@main def main(): Unit =
  println(fib(6))
  println(calls)
  println(fib(6))
  println(calls)

Key points

Cache: A cache is a store that keeps answers already computed, keyed by their inputs.
GetOrElseUpdate: GetOrElseUpdate returns the stored answer for a key or computes and stores it when the key is missing.
Call counter: A call counter is a number that rises only when the real computation runs.
Repeated call: A repeated call with the same input should hit the cache and skip the computation.
Distinct input: A new input misses the cache and runs the computation once.

In this example, fib stores each result in the cache as it computes it. The first call for six computes seven distinct values and prints eight. The second call finds six already stored, so the counter does not move.

Note

Scala mutable maps offer getOrElseUpdate directly, so no separate check and store steps are needed.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Scastie

var calls = 0
val cache = scala.collection.mutable.Map.empty[Int, Int]
def fib(n: Int): Int =
  cache.getOrElseUpdate(n, {
    calls += 1
    if n <= 1 then n else fib(n - 1) + fib(n - 2)
  })
@main def main(): Unit =
  println(fib(6))
  println(calls)
  println(fib(6))
  println(calls)

Exercise

After square(3), square(4) and square(3) again, what is the call counter?

0 1 2 3