Boost Your Code Performance with Memoization Techniques

Photo by Oli Dale on Unsplash

Alright! Let’s start with what memoization is?
Simply put, memoization shares similarities with caching in terms of principles, usage, and purpose. Both are used to store “something” that might be repeated or frequently used, so when that “something” is needed again, it can be accessed much faster.

Now, we can conclude that the memoization technique offers significantly better performance improvements.

So, what is the difference between memoization and caching?
In context, memoization is typically used within functions to store results based on specific inputs or processes. Meanwhile, caching is more generally used to store frequently accessed data, such as files, APIs, or database query results.

I will save the discussion about caching for the next article, and let’s focus on memoization.

For example, I will use the Fibonacci algorithm to compare the performance before and after using the memoization technique.

Fibonacci Series

The Fibonacci series is a series of numbers where each number is the sum of the two preceding numbers

const fibonacciSeries = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

Fibonacci Algorithm

The Fibonacci algorithm itself has two approaches: recursion and looping. However, for the memoization example, we will use the recursion approach.

Recursion means that the function will call itself within its own definition. Here are the steps:

• If n = 0, return 0.
• If n ≤ 2, return 1.
• If n > 2, count F(n) = F(n-1) + F(n-2)

Example code:

const fib = (n) => {
  if (n <= 2) return 1
  return fib(n-1) + fib(n-2)
}

console.log(6) // 8

For n = 8,

• F(8) = F(7) + F(6)
• F(7) = F(6) + F(5)
• F(6) = F(5) + F(4)
• …
• Recursions will continue until n ≤ 2 and will return 8 at the end.

Fibonacci Recursion Breakdown

Please take a look at the following diagram.

Fibonacci Recursions Brakdown

To calculate Fibonacci with n = 6, it takes 14 recursive calls to get the result. As the value of n increases, the process becomes longer.

Get Fhaladin Dev’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

But if we observe closely, there are many repeated processes, such as fib(3) being called 3 times, meaning the same calculation is being done 3 times.

By using the memoization technique, we can eliminate these repeated processes with the following steps:

1. Check if the process has been executed before.
2. If it hasn’t been executed before, run the process and store the result in the memo.
3. If it has been executed before, simply retrieve the result from the memo without running the same process again.

The logic is that simple, but how do we implement it?
Take a look at the Fibonacci function/method with memoization added below:

const fib = (n, memo = {}) => {
  if (n in memo) return memo[n]
  if (n <= 2) return 1

  memo[n] = fib(n-1, memo) + fib(n-2, memo)
  return memo[n]
}

console.log(6) // 8

There is an additional memo parameter with the type object in the fib function/method, which is used to store previously executed processes so that they are not executed again in all subsequent recursions.

Performance Comparison

Now, let’s prove whether applying memoization really improves performance or not. And if it does, is the improvement significant or just marginal?

To check this, let’s add a few lines of code.

— Without Memoization

const fib = (n) => {
  if (n <= 2) return 1
  return fib(n-1) + fib(n-2)
}

const time = Date.now()
console.log(fib(45)) // 1134903170
console.log(Date.now() - time)

Without memoization, it takes 9412ms to calculate Fibonacci with n = 45, almost 10 seconds to execute.

— With Memoization

const fib = (n, memo = {}) => {
  if (n in memo) return memo[n]
  if (n <= 2) return 1

  memo[n] = fib(n-1, memo) + fib(n-2, memo)
  return memo[n]
}

const time = Date.now()
console.log(fib(45)) // 1134903170
console.log(Date.now() - time)

Meanwhile, with memoization, we only need 7ms, not even one-tenth of a second.

It’s proven, isn’t it? By using memoization, the Fibonacci function/method’s performance can be improved by up to 99.926% faster, a truly fantastic number!

When to Use Memoization
In addition to the recursive case in the previous example, there are many situations where we can improve performance using memoization. Some of them include:

1. Dynamic Programming, such as the knapsack problem.
2. Computationally Expensive Functions, such as for factorials, permutations, combinations, etc.
3. Queries, such as for filtering or sorting data.
4. Data Rendering, for example in Vue.js with computed properties and watchers that store calculated values if the input doesn’t change.
5. Iteration Process With Big Data, such as when implementing pagination or infinite scroll.
6. Higher-Order Components, used to avoid re-rendering the same component if the props haven’t changed.

Thank you for reading. Share if it’s useful! Like if you enjoyed it!
Happy Coding… ^^

New features in Vue 3.5 that I like!

Why Rem is Better than Px for Web Development?

Step-by-Step Guide to Building a Vue.js UI Component Library