Why optimize your code when computers are already so fast?

LFNY's 10th graders engaged in a theoretical activity on optimizing code and memoization. They learned the significance of code optimization and memoization techniques for improving algorithm efficiency, without any coding involved.

Pascal’s Triangle is a mathematical concept that consists of a triangle made of numbers. Each row in the triangle is made by adding together adjacent elements from the previous row.

The TypeScript recursive function below returns the value of a specific row and column in Pascal’s triangle.

function pascal(x, y) {
    return (x == 1 || x == y || y == 1)
        ? 1
        : pascal(x - 1, y - 1) + pascal(x, y - 1);
}        

To use this function, simply call it with the desired row and column values as arguments. For example, to get the value of the element in the fourth column and fifth row of Pascal’s Triangle, call the function like this:

pascal(4,5)
=> 4        

It works wonderfully! At least with small numbers. But what’s going on with big number?

Let’s try measuring the performance using performance.now().

const t0 = performance.now();
const rep : number = pascal(15,49)
const t1 = performance.now();
console.log(`Call to do get Pascal Number took ${t1 - t0} milliseconds.`);
console.log('=>',rep)
-------Result from console
x = 15 y = 40
Call to do get Pascal Number took 454587.3893730007 milliseconds.
=> 15084504396        

Although the code for the Pascal Triangle function looks visually appealing, it is unfortunately not optimized for efficiency, resulting in slower performance especially when dealing with larger numbers.

We are performing the same calculation repeatedly. Here is an exemple on pascal(3,5).

The idea is to avoid performing the same calculation multiple times. In this case, we need to recalculate pascal(2,3), but we already know the result!

To avoid duplicating the same subtree, it is important to keep track of previous calculations. One way to do this is to store already calculated values in a dictionary or array. By doing so, if we encounter a (x, y) that has already been calculated, we can access its result rather than performing the calculation again.

So we will have to add a list of values that have already been encountered in the Pascal function.

function pascalMemo(x:number, y:number):number  {
  const memo: number[][] = [];  // let's store all the calculus number here
  function withMemo(x: number, y: number): number {
      if (memo[x] && memo[x][y]) {
          return memo[x][y];
      }
         
      const result = (x == 1 || x == y || y == 1)
          ? 1
          : withMemo(x - 1, y - 1) + withMemo(x, y - 1);
      
       if (!memo[x]) {
          memo[x] = [];
      }
      memo[x][y] = result;
      return result;
      }
    return withMemo(x,y);
}

const x = 15
const y = 40
const t0 = performance.now();
const rep : number = pascalMemo( x,y)
const t1 = performance.now();
console.log("x =",x,"y =", y)
console.log(`Call to do get Pascal Number took ${t1 - t0} milliseconds.`);
-----------
Result from console:
x = 15 y = 40
Call to do get Pascal Number took **0.2899500**
=> 15084504396        

0.2899500 milliseconds with optimization!!!!!

With a simple optimization, we were able to reduce the time needed from 454587.39 milliseconds to 0.29 milliseconds. This is approximately 1572966 times faster.

#computerscience #highschool Lycée Français de New York