Pasted

package com.genuinevm.puzzlers;
 
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
 
public class MemoFib {
 
    private static Optional<Long>[] memo1;
    private static Map<Integer, Long> memo2;
 
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        long time = System.nanoTime();
        memo1 = new Optional[1024];
        Arrays.fill(memo1, Optional.empty());
        for (int i = 0; i <= 200; i++) {
//          if (i >= memo.length)
//              memo = resizeArray(memo);
            fib1(i);
        }
        System.out.println("fib1 took " + (System.nanoTime() - time) + " nanoseconds.");
        time = System.nanoTime();
        memo2 = new HashMap<Integer, Long>(1024);
        for (int i = 0; i <= 200; i++) {
            fib2(i);
        }
        System.out.println("fib2 took " + (System.nanoTime() - time) + " nanoseconds.");
    }
 
    public static long fib1(int number) {
        if (number <= 1)
            return 1;
        if (!memo1[number].isPresent())
            memo1[number] = Optional.of(fib1(number - 1) + fib1(number - 2));
        return memo1[number].get();
    }
    
    public static long fib2(int number) {
        if (number <= 1)
            return 1;
        if (!memo2.containsKey(number))
            memo2.put(number, fib1(number - 1) + fib1(number - 2));
        return memo2.get(number);
    }
 
    // Wont be used in this example.
    @SuppressWarnings("rawtypes")
    private static Optional[] resizeArray(Optional[] opts) {
        Optional[] out = new Optional[opts.length * 2];
        Arrays.fill(out, Optional.empty());
        for (int i = 0; i < opts.length; i++)
            out[i] = opts[i];
        return out;
    }
}
 
// fib1 took 891176 nanoseconds.
// fib2 took 605662 nanoseconds.