Recursive Fibonacci with and without memoization with runtime metrics

Revision: 58454

at July 16, 2012 13:08 by m1b

Initial Code

import java.util.Arrays;

public class FibonacciMemoize {
    private static abstract class Fibber {
       long opCount;
       void reset() {
           opCount = 0;
       }
       abstract int fib(final int source);
       abstract String name();
    }

    private static class FibberBrute extends Fibber {
        @Override public int fib(int n) {
            opCount++;
            return n < 2 ? n : fib(n - 1) + fib(n - 2);
        }

        @Override public String name() { return "brute"; }
    }

    private static class FibberMemo extends Fibber {
        private  int memo[] = new int[1024];

        @Override void reset() {
           super.reset();
            Arrays.fill(memo, 0);
        }

        @Override public int fib(int n) {
            opCount++;
            int retVal = n < 2 ? n : ( memo[n] == 0 ? fib(n - 1) + fib(n - 2) : memo[n]);
            memo[n] = retVal;
            return retVal;
        }

        @Override public String name() { return "memo"; }
    }

    public static void main(String[] args) {
       if(args.length < 1) throw new IllegalArgumentException("Give me a int, max fib to print");
       final int max = Integer.valueOf(args[0]);
       final Fibber[] fibbers = { new FibberBrute(), new FibberMemo()};
       for(int i = 0; i <= max; i++) {
            System.out.printf("%nfib(%d)=", i);
            int check = Integer.MIN_VALUE;
            for(final Fibber fibber: fibbers) {
                fibber.reset();
                final long start = System.currentTimeMillis();
                final int result = fibber.fib(i);
                final long end = System.currentTimeMillis();
                if(check == Integer.MIN_VALUE) {
                    check = result;
                    System.out.printf("%,d", result);
                }
                else if ( result != check) throw new RuntimeException("Fibber \"" + fibber.name()
                    + "\" returned result " + result + " while previous result was " + check + " for n=" + i);

                System.out.printf(" {%s: ops=%,d; ms=%,d}", fibber.name(), fibber.opCount, end - start);
            }
        }
    }
}

Initial URL

Initial Description

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

Initial Title

Recursive Fibonacci with and without memoization with runtime metrics

Initial Tags

Initial Language

Java

Choose a language for easy browsing: