Posted By

m1b on 07/16/12

Tagged

Versions (?)

Last Edited at 07/16/12 01:08pm

Statistics

Viewed 457 times

Favorited by 0 user(s)

Related snippets

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.

Highlighted TextExpand

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);
            }
        }
    }
}

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.