The Uncarved Blog: Memoization in scala

Memoization in scala

A simple, yet effective optimization technique

I've been off work ill today, but reading was getting on my nerves, so I decided to do more work in scala, and wrote some objects to do easy Memoization. I thought I needed them to optimise something else that I was doing, then found a better way to do it without classical memoization (sigh).

The code was heavily based on something I found here (hat tip michid), with minor tweaks of my own. Here's how you use the memo classes anyway:

scala> import com.uncarved.helpers.Memoize
scala> val circArea =
  |       Memoize((r:Double)=>Math.Pi * Math.pow(r,2))
circArea: com.uncarved.helpers.Memoize.MemoizedFunction1[Double,Double] = <function>

scala>   val area = circArea(2)
area: Double = 12.566370614359172

So you can use something like a function and it seems to do the right thing. "But how", you may well ask, "do I know it's actually memoizing and this isn't all a big trick?". A fair and honest question. We need to add a function that has a side-effect so we can demonstrate that it is in fact doing the right thing.

We need a function that will print something to the terminal when the calculation is actually invoked. When it isn't, it will return the same result, but without any printing.

scala>   val cylVol = Memoize {            
 |       (r:Double, h:Double) =>
 |         val vol = Math.Pi * Math.pow(r,2) * h
 |         println("Radius: " + r + " Height: " + 
 |             h + " Volume: " + vol)
 |       vol                                                               
 |  }                                                         
cylVol: com.uncarved.helpers.Memoize.MemoizedFunction2[Double,Double,Double] = <function>

The first time we invoke our function it hits the print statement:

scala> cylVol(3,4.5)
Radius: 3.0 Height: 4.5 Volume: 127.23450247038662
res1: Double = 127.23450247038662

...but when we invoke the function again on identical arguments, the cached result is used, so we don't see the print.

scala> cylVol(3,4.5)
res2: Double = 127.23450247038662

If the arguments change, a fresh invocation is made.

scala> cylVol(3,4)  
Radius: 3.0 Height: 4.0 Volume: 113.09733552923255
res3: Double = 113.09733552923255

You can get the code and libs by using sbaz to update your uncarved-helpers package, or just via the tarball. For the curious, here's the full text of the scala code.