Advanced Search

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.

Expand | Embed | Plain Text

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.