Victor is a ruby developer at Nulogy. He has worked a lot with Java and Ruby platforms. Being a big fan of domain specific languages he likes to blog about implementing them using Groovy, Ruby or Clojure. Victor is a DZone MVB and is not an employee of DZone and has posted 40 posts at DZone. You can read more from them at their website. View Full User Profile

Cool Stuff in Groovy 1.8: Memoization

05.19.2011
| 8013 views |
  • submit to reddit

Groovy 1.8 has been released recently. It’s really amazing how much the team achieved in this release. Though my favorites are new AST transformations, enhanced DSL support and embedded GPars there are a few very nice methods that were added to closures.

Look at this chunk of code:

def fib = null
fib = {
    it <= 1 ? it : (fib(it - 1) + fib(it - 2))
}

long b = System.currentTimeMillis()
fib(35G)
long a = System.currentTimeMillis()

println “${(a-b) / 1000} seconds” // about 8 seconds on my machine

It takes so long as we have to calculate the same values again and again. It would be much faster if we stored already calculated values in memory. This technique is called memoization. Groovy 1.8 adds memoize method that does exactly that.

def fib = null
fib = {
    it <= 1 ? it : (fib(it - 1) + fib(it - 2))
}.memoize()

long b = System.currentTimeMillis()
fib(35G)
long a = System.currentTimeMillis()
println “${(a-b) / 1000} seconds” // about 0.08 seconds on my machine

You can apply memoize to every closure that doesn’t have side effects. You may say that this method is just a minor enhancement. Yes, you’d be right, but, in my view, such small features are what makes working with Groovy so enjoyable.

 

From http://victorsavkin.com/post/5174604204/cool-stuff-in-groovy-1-8-memoization

Published at DZone with permission of Victor Savkin, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Tags:

Comments

Václav Pech replied on Mon, 2011/09/19 - 11:20pm

Using the memoizeAtMost() function you could also limit the total amount of memory consumed during the calculation - see a small example motivated by your code. You can go as low as two remembered numbers (provided you re-order the recursive calls, three numbers otherwise). This turns an exponentially complex algorithm into a very efficient one - both with CPU and memory.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.