Posted By

m1b on 07/16/12


Tagged


Versions (?)

Recursive Fibonacci with and without memoization with runtime metrics


 / Published in: Java
 

Demonstrates just how bad the recursive Fibonacci performs without memoization and what difference memoization makes.

  1. import java.util.Arrays;
  2.  
  3. public class FibonacciMemoize {
  4. private static abstract class Fibber {
  5. long opCount;
  6. void reset() {
  7. opCount = 0;
  8. }
  9. abstract int fib(final int source);
  10. abstract String name();
  11. }
  12.  
  13. private static class FibberBrute extends Fibber {
  14. @Override public int fib(int n) {
  15. opCount++;
  16. return n < 2 ? n : fib(n - 1) + fib(n - 2);
  17. }
  18.  
  19. @Override public String name() { return "brute"; }
  20. }
  21.  
  22. private static class FibberMemo extends Fibber {
  23. private int memo[] = new int[1024];
  24.  
  25. @Override void reset() {
  26. super.reset();
  27. Arrays.fill(memo, 0);
  28. }
  29.  
  30. @Override public int fib(int n) {
  31. opCount++;
  32. int retVal = n < 2 ? n : ( memo[n] == 0 ? fib(n - 1) + fib(n - 2) : memo[n]);
  33. memo[n] = retVal;
  34. return retVal;
  35. }
  36.  
  37. @Override public String name() { return "memo"; }
  38. }
  39.  
  40. public static void main(String[] args) {
  41. if(args.length < 1) throw new IllegalArgumentException("Give me a int, max fib to print");
  42. final int max = Integer.valueOf(args[0]);
  43. final Fibber[] fibbers = { new FibberBrute(), new FibberMemo()};
  44. for(int i = 0; i <= max; i++) {
  45. System.out.printf("%nfib(%d)=", i);
  46. int check = Integer.MIN_VALUE;
  47. for(final Fibber fibber: fibbers) {
  48. fibber.reset();
  49. final long start = System.currentTimeMillis();
  50. final int result = fibber.fib(i);
  51. final long end = System.currentTimeMillis();
  52. if(check == Integer.MIN_VALUE) {
  53. check = result;
  54. System.out.printf("%,d", result);
  55. }
  56. else if ( result != check) throw new RuntimeException("Fibber \"" + fibber.name()
  57. + "\" returned result " + result + " while previous result was " + check + " for n=" + i);
  58.  
  59. System.out.printf(" {%s: ops=%,d; ms=%,d}", fibber.name(), fibber.opCount, end - start);
  60. }
  61. }
  62. }
  63. }

Report this snippet  

You need to login to post a comment.