CodingGyan

Memoize a Function (Count the Real Calls)

hard Generics, Lambdas and Streams

Problem

Write a function memoize(f) that returns a new function. The new function remembers the results, and calls f only for an argument it has not seen before. Use it to compute the Fibonacci number F(n) (F(0) = 0, F(1) = 1) with recursion, where the recursive calls also go through the memoized function. Print result: F(n) and calls: the number of times the real Fibonacci code ran.

Constraints

  • 0 <= n <= 70

Examples

Input

10

Output

result: 55
calls: 11

Solutions

Best approachTime O(n)Space O(n)

A memoizing wrapper is a function that takes a function and returns a function: a higher-order function. The calls count shows the effect: F(10) needs only 11 real calls (one for each value from 0 to 10) instead of 177. The recursion must call the wrapper, not the original function, or the cache is never used.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Memoized Fibonacci.
 * Input   : One integer n.
 * Output  : Two lines.
 * Approach: A caching wrapper.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: memoize takes a function and returns a new function with a cache (a map from the argument to the result).
        static java.util.function.LongUnaryOperator memoize(java.util.function.LongUnaryOperator function, java.util.Map<Long, Long> cache) {
            return argument -> {
                Long saved = cache.get(argument);
                if (saved != null) {
                    return saved;
                }
                long result = function.applyAsLong(argument);
                cache.put(argument, result);
                return result;
            };
        }

        // Step 2: The counter of real calls, and the memoized Fibonacci function. The function must call itself through the memoized version.
        static int calls = 0;
        static java.util.function.LongUnaryOperator fibonacci;

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(long n) {
        calls = 0;
        java.util.Map<Long, Long> cache = new java.util.HashMap<>();

        // Step 3: The real Fibonacci code counts each time it runs. Its recursive calls use the memoized function.
        fibonacci = memoize(k -> {
            calls++;
            return k < 2 ? k : fibonacci.applyAsLong(k - 1) + fibonacci.applyAsLong(k - 2);
        }, cache);

        long result = fibonacci.applyAsLong(n);
        return new String[] {"result: " + result, "calls: " + calls};
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(String.join("\n", solve(n)));
    }
}
Hints (1)
  1. What happens if the Fibonacci code calls itself directly?

Try these next