How to save money in cloud computing – memoization

Following the serie about how to reduce costs in cloud computing, at this post we’re going to present another technique which should be very helpful.

The main ideia behind the walls is to keep tracking of the previous calculation to do not need to recalculate each time again.

The most famous example about memoization is its application in Fibonacci calculation. The Fibonacci number sequence is found in many nature situations like, shells, galaxies and so on.

In case your not so familiar with the sequence, to find the value of a specific position of the array you must sum the two previous values.

Below follow an implementation of the the algorithm

  function fibonacci(target: number): number {
    if (target < 2) return 1;

    return fibonacci(target - 1) + fibonacci(target - 2);
  }

The implementation is very simple even in a recursive way:

• Validation of the base case, in case value is lower than 2
• Call the function recursively adding the two previous values of the target

When you start to do some tests trying to find the 11th Fibonacci number you gonna be ok, but when reach out the 40th element boundary you gonna realize that running time start increase a lot. Of course it depends on your personal computer.

The chart above presents the exponential growth of the function. But there is a clever way to reduce that. But before, lets explained what is the problem. Calling recursively to find the 5th element you must find the 4th and the 3rd, to find 3rd must find the 2nd and the first. Take a look at tree below.

You gonna realize that to find out the 5th element, you calculate the 2nd 3 times. Imagine it when you try to find the 100th element…

The optimized solution

In fact the solution is simple and elegant, as everything in computing should be. We must create an structure to store the previous calculation always look for the value on this structure before calculate again. Lets take a look at the code below.

  function fibonacciMemo(
    target: number,
    memo: Record<number, number> = {}
  ): number {
    if (target < 2) return 1;

    if (memo[target]) {
      return memo[target];
    } else {
      memo[target] =
        fibonacciMemo(target - 1, memo) + 
        fibonacciMemo(target - 2, memo);
    }
    return memo[target];
  }

The code above the steps:

• Initiate an empty object
• define our base case to stop: Target lower than 2
• IF target is found in memo object, return it
• ELSE store it on memo
• Reaching out base case, return target value from memo

Memoization is not an algorithm by its own, but a technique which can support many algorithms reducing its running time.

Conclusion

In this case, using memoization, until Fibonacci of 5000 you are under ONE second of running time, it is tremendous.

You need to remember that running time is money in cloud computing, so never forget to use some kind of approach reduce the time and consequently reduce costs with cloud computing.

Stay tuned to next posts.