14.Implement-a-general-memoization-function.md

14. Implement a general memoization function - memo()

Problem

https://bigfrontend.dev/problem/implement-general-memoization-function

Problem Description

Memoization is a common technique to boost performance. If you use React, you definitely have used React.memo before.

Memoization is also commonly used in algorithm problem, when you have a recursion solution, in most cases, you can improve it by memoization, and then you might be able to get a Dynamic Programming approach.

So could you implement a general memo() function, which cache the result once called, so when same arguments are passed in, the result will be returned right away.

const func = (arg1, arg2) => {
  return arg1 + arg2;
};

const memoed = memo(func);

memoed(1, 2);
// 3, func is called

memoed(1, 2);
// 3 is returned right away without calling func

memoed(1, 3);
// 4, new arguments, so func is called

The parameters are arbitrary, so memo should accept an extra resolver parameter, which is used to generate the cache key, like what _.memoize() does.

const memoed = memo(func, () => 'samekey');

memoed(1, 2);
// 3, func is called, 3 is cache with key 'samekey'

memoed(1, 2);
// 3, since key is the same, 3 is returned without calling func

memoed(1, 3);
// 3, since key is the same, 3 is returned without calling func

Default cache key could be just Array.from(arguments).join('_')

note

It is a trade-off of space for time, so if you use this in an interview, please do analyze how much space it might cost

Solution

/**
 * @param {Function} func
 * @param {(args:[]) => string }  [resolver] - cache key generator
 */
function memo(func, resolver) {
  const cache = new Map();

  return function (...args) {
    const key = resolver ? resolver(...args) : args.join('_');
    if (cache.has(key)) {
      return cache.get(key);
    }

    const result = func.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

Explanation

let's break down the memo function:

1. Function Definition: The memo function takes two arguments: func, which is the function you want to memoize, and resolver, which is an optional function used to generate the cache key.

2. Cache Creation: Inside the memo function, a new Map object is created to serve as the cache. This cache will store the results of func for different arguments.

3. Return Function: The memo function returns a new function that takes any number of arguments (...args). This function is a closure that has access to func, resolver, and cache.

4. Cache Key Generation: Inside the returned function, a cache key is generated. If a resolver function was provided, it's used to generate the key. Otherwise, the arguments are joined with an underscore to create the key.

5. Cache Check: The function checks if the cache has a value for the generated key. If it does, this value is returned immediately, skipping the execution of func.

6. Function Execution and Caching: If the cache does not have a value for the key, func is called with the arguments, and the result is stored in the cache with the key. The result is then returned.

This memo function is a general-purpose memoization function. It can be used to memoize any function to improve performance by caching the results of expensive function calls. The optional resolver function allows for custom cache key generation, which can be useful when the arguments are complex objects or when you want to treat different arguments as equivalent.

Real World Examples

Caching is a crucial technique in JavaScript development, enhancing performance and efficiency by storing frequently accessed data. Here are several real-world examples of caching in JavaScript:

1. HTTP Caching with Service Workers:

   • Example: Progressive Web Apps (PWAs)
   • Explanation: Service workers intercept network requests and serve responses from a cache, reducing the need for repeated network requests. This is common in PWAs to allow offline access and improve load times.

2. Browser Caching:

   • Example: Static assets like images, CSS, and JavaScript files
   • Explanation: Browsers cache these files to avoid re-downloading them on subsequent visits. Developers use HTTP headers (e.g., Cache-Control, ETag) to control this caching behavior.

3. In-memory Caching:

   • Example: Storing API responses
   • Explanation: JavaScript applications, particularly those running in Node.js, may cache API responses in memory to reduce the number of calls to an external API. This is particularly useful for rate-limited or resource-intensive APIs.

4. LocalStorage/SessionStorage:

   • Example: User preferences and session data
   • Explanation: Web applications store user settings, preferences, or session-specific data in localStorage or sessionStorage, enabling quick access and persistence across sessions.

5. Memoization:

   • Example: Caching results of expensive function calls
   • Explanation: Functions that perform costly calculations cache their results for given inputs, avoiding repeated calculations. This is a common optimization technique in data-intensive applications.

6. Content Delivery Networks (CDNs):

   • Example: Serving static resources
   • Explanation: CDNs cache copies of static assets in multiple geographic locations, reducing latency and improving load times for users by serving content from the nearest server.

7. Component-level Caching in Frameworks:

   • Example: React’s useMemo and useCallback hooks
   • Explanation: These hooks cache computations and callbacks, respectively, to avoid unnecessary re-renders and recalculations in React applications.

8. Cache-first Strategies in Data Fetching Libraries:

   • Example: Apollo Client for GraphQL
   • Explanation: Apollo Client can cache GraphQL query results and serve them from the cache on subsequent requests, reducing the need for repeated network requests.

9. IndexedDB:

   • Example: Large-scale data storage
   • Explanation: Web applications use IndexedDB for storing large amounts of structured data, which can be retrieved and manipulated asynchronously.

10. Lazy Loading and Caching Images:

    • Example: Image galleries or infinite scrolling pages
    • Explanation: Images are loaded as they enter the viewport and cached for subsequent views, reducing initial load times and bandwidth usage.

Each of these examples demonstrates how caching can significantly improve performance and user experience in JavaScript applications by reducing redundant operations and optimizing resource use.