What is Memoization - Simple & Code Examples

What is Memoization - Simple & Code Examples

In this blog post, I will be discussing memoization in programming, which is a technique that can help us achieve just that. I will cover what memoization is, and its best practices, and provide code examples in TypeScript and Python.

What is Memoization in Programming

Memoization is a technique used in programming to speed up function execution by caching the results of expensive function calls and returning the cached result when the same inputs occur again. In other words, it's a way to remember or cache the output of a function based on its input parameters. This can significantly improve the performance of our applications, especially when we are working with expensive computations or database queries.

Best Practices:

Memoization is often used in dynamic programming, a programming technique that solves problems by breaking them down into smaller subproblems and solving each subproblem only once. To ensure that memoization works correctly, we need to follow some best practices. Firstly, we should only cache pure functions that always return the same output for the same input. Secondly, we should ensure that the cache does not grow infinitely and that we have a mechanism to clear the cache if required. Lastly, we should only use memoization when we have identified performance bottlenecks and need to optimize the application.

Code Examples

Let's take a look at two code examples, one in TypeScript and the other in Python.

TypeScript Example

const cache = new Map();

function fibonacci(n: number): number {
  if (n <= 1) {
    return n;
  }

  if (cache.has(n)) {
    return cache.get(n);
  }

  const result = fibonacci(n - 1) + fibonacci(n - 2);
  cache.set(n, result);
  return result;
}

console.log(fibonacci(10)); // Output: 55
console.log(fibonacci(11)); // Output: 89

In this example, we are using memoization to cache the result of the Fibonacci sequence function. The function first checks if the result for a given input is already in the cache. If it is, the function returns the cached result. Otherwise, it calculates the result, adds it to the cache, and returns it. We are using a Map object to store the cached results.

Python Example

def memoize(func):
    cache = {}

    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return wrapper

@memoize
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10)) # Output: 55
print(fibonacci(11)) # Output: 89

This example is similar to the TypeScript example, but we are using a decorator to memoize the Fibonacci function. The memoize function is a higher-order function that takes the Fibonacci function as an argument and returns a wrapper function that caches the results.

Memoization vs Dynamic Programming

Dynamic programming and memoization are closely related concepts, but they are not the same thing. Dynamic programming is a technique that solves problems by breaking them down into smaller subproblems and solving each subproblem only once. Memoization is a technique that stores the result of expensive function calls and returns the cached result when the same inputs occur again. Dynamic programming can use memoization as a technique to optimize the solution, but it's not the only technique used. Memoization is a sub-technique of dynamic programming that is used to store the results of subproblems that have already been solved to avoid recomputing them. In summary, memoization is a useful technique for solving subproblems in dynamic programming, but dynamic programming encompasses a broader set of techniques for solving problems.

Memoization and Skill Level

Memoization is more commonly used by mid-level to senior developers who have experience working with performance optimization and dynamic programming.

Junior developers can still benefit from memoization, but it's not expected that they will be familiar with the concept right away. As junior developers become more familiar with programming concepts, data structures, and algorithms, they can start to identify performance bottlenecks in their applications and apply memoization to optimize their code.