This is quite common technique to speed up recursive algorithms (Usually you will use maps for this).

Groovy support memoization through it's

**.memoize()**method.

The first invocation is doing actual work and and subsequent invocation is pulling result from cache.

If you run this program, you will see something like this as output:

Test without memoization:

Adding 1 and 3 took 1540 msec with result 4.

Adding 1 and 3 took 1500 msec with result 4.

Adding 1 and 3 took 1501 msec with result 4.

Adding 1 and 3 took 1500 msec with result 4.

Adding 1 and 3 took 1500 msec with result 4.

Test with memoization:

Adding 1 and 3 took 1500 msec with result 4.

Adding 1 and 3 took 0 msec with result 4.

Adding 1 and 3 took 0 msec with result 4.

Adding 1 and 3 took 1 msec with result 4.

Adding 1 and 3 took 0 msec with result 4.

Test without memoization:

Adding 1 and 3 took 1540 msec with result 4.

Adding 1 and 3 took 1500 msec with result 4.

Adding 1 and 3 took 1501 msec with result 4.

Adding 1 and 3 took 1500 msec with result 4.

Adding 1 and 3 took 1500 msec with result 4.

Test with memoization:

Adding 1 and 3 took 1500 msec with result 4.

Adding 1 and 3 took 0 msec with result 4.

Adding 1 and 3 took 0 msec with result 4.

Adding 1 and 3 took 1 msec with result 4.

Adding 1 and 3 took 0 msec with result 4.

As you can see there is quite a difference between two test. It goes without saying that your closures should return same result for same parameters.

addTwoNumbers = {int a, b -> //simulate some lengthy calculation Thread.sleep(1500) a + b } println("Test without memoization:") def testItWithoutMemoization(a, b) { long start = System.currentTimeMillis() long result = addTwoNumbers(a, b) println("Adding $a and $b took " + "${System.currentTimeMillis() - start} " + "msec with result $result.") } testItWithoutMemoization(1, 3) testItWithoutMemoization(1, 3) testItWithoutMemoization(1, 3) testItWithoutMemoization(1, 3) testItWithoutMemoization(1, 3) addTwoNumbersWithMem = addTwoNumbers.memoize() println("Test with memoization:") def testItWithMemoization(a, b) { long start = System.currentTimeMillis() long result = addTwoNumbersWithMem(a, b) println("Adding $a and $b took " + "${System.currentTimeMillis() - start} " + "msec with result $result.") } testItWithMemoization(1, 3) testItWithMemoization(1, 3) testItWithMemoization(1, 3) testItWithMemoization(1, 3) testItWithMemoization(1, 3)

## No comments:

## Post a Comment