Hi Guys! I would like to share with you a very interesting concept of groovy that I learnt in the Grails Conference I attended last week. The concept is “Memoization in Groovy”. I didn’t hear about Memoization before. I found it quite interesting. So, I tried some Memoization examples on groovyConsole and thought of sharing it with you.

What is Memoization ?

Memoization is a technique that is used to store the results of function calls and returning the cached result when the same inputs occurs. It results in faster processing.

Let us see an example:

def func1 = { Integer x ->
    println "Value is $x"
}.memoize()

func1(3)
func1(4)
func1(3)
func1(4)

Output:

Value is 3
Value is 4

In the above example we defined a closure and assign it to func1. Now we call the the closure 4 times but we can see in the output that the body is executed only 2 times. Why ? Its because of using “.memoize()”. We passed 2 duplicate values 3 and 4. The first time we call func1(3) and func1(4) its result is stored in the cache. Next time when we again pass 3 and 4, the body is not executed at all. Instead a cached result of that function is returned.

How it can be useful ?

It can be very useful for recursive calculations like calculating factorial, fibonacci using recursion.

The example below will make it clear:

Non-Memoized version


fib =  { f ->
   println "Fibonacci for number: $f"
   if (f <= 1) {
       return f
   }
   fib(f - 1) + fib(f - 2)
}

fib(5)

Output:

Fibonacci for 5
Fibonacci for 4
Fibonacci for 3
Fibonacci for 2
Fibonacci for 1
Fibonacci for 0
Fibonacci for 1
Fibonacci for 2
Fibonacci for 1
Fibonacci for 0
Fibonacci for 3
Fibonacci for 2
Fibonacci for 1
Fibonacci for 0
Fibonacci for 1

Memoization in Groovy

We can see many duplicate calls for values like 1,2,3 etc. in the above example.

Now lets try a memoized version:

fib =  { f ->
   println "Fibonacci for number: $f"
   if (f <= 1) {
       return f
   }
   fib(f - 1) + fib(f - 2)
}.memoize()

fib(5)

Output:

Fibonacci for number: 5
Fibonacci for number: 4
Fibonacci for number: 3
Fibonacci for number: 2
Fibonacci for number: 1
Fibonacci for number: 0

Memoization in Groovy

We can now see in the above example that there is not even a single duplicate call which really saves a lot of time.

If you try fib(45) or fib(50) without memoization it will take more than 30 seconds to give the output.

So, that was all about memoization., I hope the concept is clear to you 🙂

Thanks