2630. Memoize II

Problem Description

The problem requires us to enhance a given function fn by adding memoization to it. Memoization is an optimization technique used to increase the performance by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

The goal is to ensure that fn, once memoized, does not compute the result again for inputs it has already processed. Instead, it should return the previously computed result. It is important to note that inputs are considered identical when they are strictly equal to each other (===), meaning that the comparison must consider both value and type.

Intuition

To memoize a function, we need two main components: a cache to store previously computed values and a way to uniquely identify each set of inputs.

The provided solution creates a memoized version of the fn function. Here's the thought process behind it:

1. Define a cache mechanism. The solution uses two maps: idxMap and cache.

   • idxMap is used to assign a unique index for every distinct object.
   • cache is where the actual function outputs are stored, mapped by a unique key representing the function arguments.

2. Generate unique keys for function arguments. Since the arguments could be objects, and we need a primitive value as a key for caching, the approach abstracts every input using an index representation. It assigns a unique index to every unique object input and then creates a string from these indices, which represents the combination of arguments.

3. Wrap the original function fn with a new function that intercepts calls to fn. For every call:

   • Generate a unique key for the arguments provided.
   • Check if the result is already present in the cache. If it's there, return the cached result.
   • If the result is not cached, call fn with the original arguments, store the result in the cache, and then return the computed result.

This approach ensures that if the memoized function is called again with the same combination of arguments (based on strict equality), it does not recompute the result but instantly returns the cached result, thereby saving time on subsequent calls with identical inputs.

Solution Approach

The solution uses the following algorithms, data structures, and patterns:

1. Closures: The memoize function returns a new function that maintains a closure over the idxMap and cache. This allows the new function to have persistent private data (caches) that are accessible across multiple invocations.

2. Map Object: Two Map objects are used.

   • cache stores the results of the function calls with a unique string key for each set of parameters.
   • idxMap maps objects to unique indices. This is needed because we cannot use objects directly as keys in the cache Map.

3. Unique Key Generation: Each set of parameters needs to be uniquely identified to decide if the function output for those parameters is already cached. To achieve that uniqueness:

   • We assign a unique index to every distinct object encountered as a parameter via the getIdx function. For non-object parameters that can be directly compared by value (like numbers, strings, etc.), their "index" is effectively the value itself.
   • The unique key for the cache map is generated by concatenating the indices of the parameters with commas, ensuring a string that represents the parameters' combination.

4. Memoization Logic: When the returned function is called, a key is generated to represent the parameters. The function then does the following:

   • Checks cache to see if the key exists, indicating that the function has been called before with these parameters. If so, the cached value is returned, preventing the recalculation.
   • If the key does not exist in the cache, it calls fn with the given parameters, stores the result in cache using the generated key, and returns the result.

The algorithm is efficient because it avoids redundant computation by storing function results that have already been computed, using only the memory needed to store unique calls. The use of a Map object for caching provides constant-time retrieval, making the look-up process fast.

Here's a walkthrough of the implementation steps in code:

• Define the memoize function which takes the function fn as an argument.
• Inside memoize, initialize the idxMap and cache maps.
• Define the getIdx function, which assigns and retrieves a unique index for object parameters.
• Return a new function from memoize that wraps the original function fn.
• In the wrapped function, generate a key based on the parameters using getIdx.
• Check if the key exists in cache. If it does, return the stored value.
• If the key does not exist, compute the result using fn, store it in cache, and return it.

This memoize function can then be applied to any function fn to create a memoized version of it, thereby optimizing it for scenarios where the function is likely to be called multiple times with the same set of parameters.

Example Walkthrough

Let's walk through an example by applying the memoization technique to a simple function — a Fibonacci sequence generator. The Fibonacci function fib is well-known for its efficiency issues with recursive calls because it recalculates the same values multiple times.

Here's the fib function without memoization:

1function fib(n) {
2  if (n === 0 || n === 1) {
3    return n;
4  }
5  return fib(n - 1) + fib(n - 2);
6}

Now, let's apply the memoize function to fib to create a memoized version:

1const memoizeFib = memoize(fib);

Next, we'll see how memoization optimizes the function calls. Suppose we call memoizeFib(5):

1. The function checks if the result for 5 is in the cache. It's not, so it computes fib(5).
2. To compute fib(5), it needs fib(4) and fib(3). These calls go through the memoized function as well.
3. Recursive calls continue until it hits the base case for fib(0) and fib(1), which return 0 and 1, respectively. Each computed value gets stored in the cache.
4. It then combines cached results to return fib(5) without additional redundant calls.
5. The result is stored in the cache with the key '5'.

Now, if we call memoizeFib(5) again:

1. The function generates the key '5'.
2. It finds the key in the cache and returns the stored result immediately without recomputation.

Here are the specific steps the memoization follows for fib:

• When memoizeFib(5) is called for the first time, the cache is empty, so it calculates and stores the result for each unique call of fib (i.e., fib(5), fib(4), fib(3), fib(2), fib(1), and fib(0)).
• For the sake of example, assume that calculating fib(5) indirectly led to two calls to fib(3). The first call would compute and cache the result. The second call to fib(3) would immediately return the cached result.
• The memoization saves computation time by storing the result of each unique fib(n) so all subsequent calls for these n values will be returned instantly from the cache.

Applying the memoize function to fib drastically improves its performance, especially for large values of n, because the number of computations from an exponential to a linear growth in terms of the input.

This walkthrough illustrates the core idea of memoization and how it can be applied to optimize a computationally expensive recursive function.

Solution Implementation

Time and Space Complexity

The time complexity and space complexity of the code are as follows:

Time Complexity

For function memoize:

• The getIdx function has a time complexity of O(1) for each call due to the direct access of Maps.
• memoize generates a key by iterating over the input parameters and calling getIdx. If there are n parameters, this process has a time complexity of O(n) since it maps each parameter.
• Checking the cache and potentially executing the function fn with ...params depends on:
  • The number of unique parameter combinations passed (m), which would be the number of unique keys, and
  • The time complexity of the function fn itself (let's denote this as T(fn)).

Hence, the time complexity can vary depending on whether the data is present in the cache:

• First call with new parameters: O(n) + T(fn).
• Subsequent calls with the same parameters: O(n), since it will retrieve the result directly from the cache.

Space Complexity

• The idxMap map keeps growing as new unique objects are passed, which leads to space complexity of O(u), where u is the number of unique object parameters seen over all calls.
• Similarly, the cache map stores the results for each unique parameter combination. Thus, it has a space complexity of O(m), where m is the number of unique parameter combinations.

The overall space complexity is O(u + m).

In conclusion, the final overall time complexity is dependent on the specific use case, particularly the complexity of fn and the unique parameter combinations. The space complexity is a combination of unique objects encountered and unique stored results.