Fib.java, Java - rextester

Language: Layout:

/*
  Code illustrating a lecture on memoization
  given by Clément Aubert.
  Cf. https://lacl.fr/~caubert/LR/
  02/02/2017
  Code inspired from
  https://stackoverflow.com/questions/14921294/memoization-of-dynamic-programming
  http://www.javabrahman.com/gen-java-programs/recursive-fibonacci-in-java-with-memoization/
  Cf. also
  https://github.com/sebhoss/memoization.java
  https://dzone.com/articles/java-8-automatic-memoization
*/

import java.util.ArrayList;
import java.util.HashMap;

class Rextester{

// Straightforward implementation:
    public static int fib(int n) {
	if (n <= 1) {
	    return n;
	}
	return fib(n - 1) + fib(n - 2);
    }

// Using array:
    static int[] memoArray;
    public static int fibArray(int n) {
	memoArray = new int[n];
	return fibArrayHelper(n);
    }
    private static int fibArrayHelper(int n) {
	if (n <= 1) {
	    return n;
	} else {
	    if (memoArray[n - 2] != 0) {
		return memoArray[n - 2];
	    }
	    memoArray[n - 2] = fibArrayHelper(n - 2) + fibArrayHelper(n - 1);
	    return memoArray[n - 2];
	}
    }

// Using ArrayList:
    static ArrayList < Integer > memoArrayList = new ArrayList < Integer > ();

public static int fibArrayList(int n) {
	return fibArrayListHelper(n);
    }

private static int fibArrayListHelper(int n) {
	if (n <= 1) {
	    return n;
	} else {
	    if (n - 2 < memoArrayList.size())
		return memoArrayList.get(n - 2);
	    else {
		memoArrayList.add(fibArrayListHelper(n - 2) + fibArrayListHelper(n - 1));
		return memoArrayList.get(n - 2);
	    }
	}
    }

// Using HashMap:
    static HashMap < Integer, Integer > memoHash = new HashMap < Integer, Integer > ();

static public int fibHashMap(int n) {
	if (n <= 1)
	    return n;
	if (memoHash.get(n) == null) {
	    memoHash.put(n - 2, fibHashMap(n - 1) + fibHashMap(n - 2));
	}
	return memoHash.get(n - 2);
    }

public static void main(String args[]) {
	long preTime, postTime;
	int x = 35;

preTime = System.nanoTime();
	System.out.printf("%17s: %d", "fib(" + x + ")", fib(x));
	postTime = System.nanoTime();
	System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);

preTime = System.nanoTime();
	System.out.printf("%17s: %d", "fibArray(" + x + ")", fibArray(x));
	postTime = System.nanoTime();
	System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);

preTime = System.nanoTime();
	System.out.printf("%17s: %d", "fibArrayList(" + x + ")", fibArrayList(x));
	postTime = System.nanoTime();
	System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);

preTime = System.nanoTime();
	System.out.printf("%17s: %d", "fibHashMap(" + x + ")", fibHashMap(x));
	postTime = System.nanoTime();
	System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);
    }
}

[ + ] Show input
Compilation time: 0.62 sec, absolute running time: 0.24 sec, cpu time: 0.12 sec, memory peak: 19 Mb, absolute service time: 0,86 sec