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.

Validate css xhtml rdf

Unless otherwise specified the contents of this page are copyright © 2011 Sean Hunter and are released under a creative commons attribution 2.5 license.
Machine-readable metadata for this article can be found here.
Last modified: Wed Jun 1 14:33:07 2011.