Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement