Recursive Fibonacci with and without memoization with runtime metrics


/ Published in: Java
Save to your folder(s)

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


Copy this code and paste it in your HTML
  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


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.