Now let's try to revise the implementation to the for loop calculation and see their performance again.

Java

public long fib(long n) { long result = 0; long[] prevResult = new long[]{0, 1}; for (int i = 2; i <= n; i++) { result = prevResult[0] + prevResult[1]; prevResult[0] = prevResult[1]; prevResult[1] = result; } return result; }Groovy

def long fib(long n) { def result = 0 def prevResult = [0L, 1L] for (int i = 2; i <= n; i++) { result = prevResult[0] + prevResult[1] prevResult[0] = prevResult[1] prevResult[1] = result } return result }Scala

def fib(n: Long): Long = { var result = 0L val prevResult = Array(0L, 1L) for (i <- 2L to n) { result = prevResult(0) + prevResult(1) prevResult(0) = prevResult(1) prevResult(1) = result } return result }

Results:

n | implementation | result | Java | Groovy | Scala |
---|---|---|---|---|---|

10 | for-loop | 55 | 0 (ms) | 1 (ms) | 0 (ms) |

10 | recursive | 55 | 0 (ms) | 8 (ms) | 13 (ms) |

30 | for-loop | 832040 | 0 (ms) | 1 (ms) | 0 (ms) |

30 | recursive | 832040 | 14 (ms) | 59 (ms) | 14 (ms) |

50 | for-loop | 12586269025 | 0 (ms) | 0 (ms) | 1 (ms) |

50 | recursive | 12586269025 | 153909 (ms) | 285553 (ms) | 156361 (ms) |

100 | for-loop | 3736710778780434371 | 0 (ms) | 1 (ms) | 2 (ms) |

500 | for-loop | 2171430676560690477 | 0 (ms) | 7 (ms) | 9 (ms) |

I highlighted the previous test results to compare this ones.

No suprise, the for-loop boost the performance for all of them.

While n=50, Java and Scala took about 150sec and Groovy took about 285sec in the previous recursive tests. With the for-loop implementation, they all took less than 1ms. Even while running the for-loop with n=100 and n=500, the calculation time was still amazingly fast.

This can be explained by the time complexity where the recursive implementation is O(2^n) and the for-loop one is just O(n). This also demonstrates why using the right algorithm is so important.

An interesting observation was that while the calculation is taking very short time, Groovy was actually faster than Scala by a little bit. I am not sure why but it should be save to ignore the 1/2ms difference.

Base on all the results, Java was always the fastest and Scala outperformed Groovy while taking long calculation. When Groovy2 and/or JDK7 is out in Mac, I will probably do the test again and see if Groovy will catch up with the performance.