Performance optimization of memoization

Performance Optimization with Memoization

Memoization is an optimization technique that caches function results to avoid redundant calculations. When the function is called again with the same arguments, it directly returns the cached result instead of recalculating. This pattern is particularly useful for computationally intensive or recursive functions, significantly improving performance.

Implementation Principle of Memoization

The core idea of memoization is to create a cache object that stores function arguments as keys and computation results as values. Each time the function is called, it first checks if the corresponding result exists in the cache. If it does, the cached result is returned; otherwise, the function executes the computation and stores the result in the cache.

function memoize(fn) {
  const cache = {};
  return function(...args) {
    const key = JSON.stringify(args);
    if (key in cache) {
      return cache[key];
    }
    const result = fn.apply(this, args);
    cache[key] = result;
    return result;
  };
}

Basic Implementation Example

Below is an example of calculating the Fibonacci sequence, demonstrating how to optimize recursive computation using memoization:

// Unoptimized Fibonacci function
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// Optimized with memoization
const memoizedFibonacci = memoize(function(n) {
  if (n <= 1) return n;
  return memoizedFibonacci(n - 1) + memoizedFibonacci(n - 2);
});

// Performance comparison
console.time('Original Fibonacci');
fibonacci(40); // Takes about 1 second
console.timeEnd('Original Fibonacci');

console.time('Memoized Fibonacci');
memoizedFibonacci(40); // Takes about 1 millisecond
console.timeEnd('Memoized Fibonacci');

Advanced Memoization Implementation

For more complex scenarios, we can implement a more powerful memoization function:

function advancedMemoize(fn, options = {}) {
  const {
    resolver = (...args) => JSON.stringify(args),
    maxSize = Infinity,
    ttl = Infinity
  } = options;
  
  const cache = new Map();
  const lruKeys = [];
  
  return function(...args) {
    const key = resolver(...args);
    
    // Check if cache exists and is not expired
    if (cache.has(key)) {
      const { value, timestamp } = cache.get(key);
      if (Date.now() - timestamp < ttl) {
        // Update LRU order
        const index = lruKeys.indexOf(key);
        if (index > -1) {
          lruKeys.splice(index, 1);
          lruKeys.push(key);
        }
        return value;
      }
      cache.delete(key);
    }
    
    // Execute the function and cache the result
    const result = fn.apply(this, args);
    cache.set(key, {
      value: result,
      timestamp: Date.now()
    });
    lruKeys.push(key);
    
    // Check cache size limit
    if (cache.size > maxSize) {
      const oldestKey = lruKeys.shift();
      cache.delete(oldestKey);
    }
    
    return result;
  };
}

Application Scenarios of Memoization

Memoization is particularly suitable for the following scenarios:

1. Pure functions: Functions whose output depends solely on input, with no side effects
2. Computationally intensive functions: High-cost computations
3. Recursive functions: Avoid redundant calculations of the same subproblems
4. API requests: Cache results of requests with the same parameters

// Example of caching API requests
const cachedFetch = memoize(async function(url) {
  const response = await fetch(url);
  return response.json();
});

// Multiple calls to the same URL will only trigger one request
cachedFetch('/api/data').then(data => console.log(data));
cachedFetch('/api/data').then(data => console.log(data)); // Reads from cache

Limitations of Memoization

Although memoization improves performance, it has its limitations:

1. Memory consumption: Caching occupies memory, especially with large amounts of cached results
2. Non-pure functions: Not suitable for functions that depend on external state or have side effects
3. Parameter serialization: Serialization of complex objects may impact performance
4. Cache invalidation: Manual handling of cache expiration or clearing is required

// Example of parameter serialization issues
const obj1 = { a: 1, b: 2 };
const obj2 = { b: 2, a: 1 };

// These objects have the same content but different serialized results
console.log(JSON.stringify(obj1)); // {"a":1,"b":2}
console.log(JSON.stringify(obj2)); // {"b":2,"a":1}

Application of Memoization in React

React provides the useMemo and useCallback hooks for component-level memoization:

import React, { useMemo } from 'react';

function ExpensiveComponent({ list, filter }) {
  const filteredList = useMemo(() => {
    return list.filter(item => item.includes(filter));
  }, [list, filter]); // Recalculates only when list or filter changes

  return (
    <ul>
      {filteredList.map(item => (
        <li key={item}>{item}</li>
      ))}
    </ul>
  );
}

Memoization and Dynamic Programming

Memoization is a foundational technique for dynamic programming algorithms. Many dynamic programming problems can be solved using memoized recursion:

// Memoized solution for the knapsack problem
function knapsack(values, weights, capacity) {
  const memo = {};
  
  function recurse(i, remainingCapacity) {
    const key = `${i},${remainingCapacity}`;
    if (key in memo) return memo[key];
    
    if (i === values.length || remainingCapacity <= 0) {
      return 0;
    }
    
    if (weights[i] > remainingCapacity) {
      return recurse(i + 1, remainingCapacity);
    }
    
    const include = values[i] + recurse(i + 1, remainingCapacity - weights[i]);
    const exclude = recurse(i + 1, remainingCapacity);
    
    memo[key] = Math.max(include, exclude);
    return memo[key];
  }
  
  return recurse(0, capacity);
}

Alternatives to Memoization

In some cases, other optimization techniques may be more suitable than memoization:

1. Loop substitution for recursion: Avoids recursion call stack limitations
2. Precomputation: Computes and stores all possible results in advance
3. Lazy evaluation: Computes only when needed
4. Divide and conquer: Breaks the problem into smaller subproblems

// Iterative solution for the Fibonacci sequence
function fibonacciIterative(n) {
  if (n <= 1) return n;
  
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    const temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}

Performance Considerations for Memoization

When implementing memoization, the following performance factors should be considered:

1. Cache key generation: Simple and fast key generation algorithms
2. Cache data structure: Choose between objects, Maps, or WeakMaps based on the scenario
3. Cache size limits: Avoid memory leaks
4. Cache eviction policies: LRU, timed clearing, etc.

// Using WeakMap for object keys
const weakMemoize = (fn) => {
  const cache = new WeakMap();
  return (obj) => {
    if (cache.has(obj)) {
      return cache.get(obj);
    }
    const result = fn(obj);
    cache.set(obj, result);
    return result;
  };
};

Application of Memoization in Functional Programming

In functional programming, memoization can be combined with other function composition techniques:

// Memoized function combined with currying
function curryMemoize(fn) {
  const cache = new Map();
  
  function curried(...args) {
    if (args.length >= fn.length) {
      const key = JSON.stringify(args);
      if (cache.has(key)) return cache.get(key);
      const result = fn(...args);
      cache.set(key, result);
      return result;
    }
    
    return (...moreArgs) => curried(...args, ...moreArgs);
  }
  
  return curried;
}

const add = curryMemoize((a, b, c) => a + b + c);
console.log(add(1)(2)(3)); // 6
console.log(add(1)(2)(3)); // Reads from cache