¿Qué es la memoization y cómo se aplica? 🚀

¿Qué es la memoization?

La memoización es una técnica de optimización que se utiliza en programación para mejorar el rendimiento de un programa.

Consiste en almacenar el resultado de una función que ya ha sido ejecutada para que, si se vuelve a llamar con los mismos parámetros de entrada, en lugar de volver a calcular el resultado, se recupere de la memoria el valor previamente calculado.

La memoización es particularmente útil cuando se tienen funciones que son costosas en términos de tiempo de ejecución o consumo de recursos, y se espera que se llamen varias veces con los mismos argumentos.

En lugar de volver a ejecutar la función para cada llamada, la memoización puede reducir el tiempo de ejecución y mejorar la eficiencia del programa al evitar la repetición de cálculos.

La memoización puede implementarse de varias maneras, como mediante el uso de estructuras de datos como tablas hash o listas, o mediante la creación de una clase o función que mantenga en memoria los resultados previos de una función y los devuelva en lugar de volver a calcularlos.

Ejemplos aplicando memoization

Memoization con TypeScript

TypeScript cuenta con una clase para implementar tablas de hash que me gusta bastante, es la clase Map.

Te dejo a continuación un ejemplo de TypeScript usando la clase Map

            
  let cache:Map<number,number>= new Map<number,number>();
  function fibonacci(n: number): number {
    const exist_in_cache=cache.get(n);
    if (exist_in_cache) {
      return cache.get(n);
    }
    if (n <= 2) {
      return 1;
    }
    cache.set(n,fibonacci(n - 1) + fibonacci(n - 2));
    return cache.get(n);
  }
  
  console.log(fibonacci(50)); // 12586269025
  
  
        

Memoization con C#

Para el ejemplo de C# usaré un diccionario como tabla de hash.

            
  using System;
  using System.Collections.Generic;
  
  public class MemoizationExample
  {
      private static Dictionary<int, long> memo = new Dictionary<int, long>();
  
      public static long Fibonacci(int n)
      {
          if (n < 0)
          {
              throw new ArgumentException("n cannot be negative");
          }
          
          if (n <= 1)
          {
              return n;
          }
          
          // Check if result is already memoized
          if (memo.ContainsKey(n))
          {
              return memo[n];
          }
          
          // Calculate the Fibonacci number recursively
          long result = Fibonacci(n - 1) + Fibonacci(n - 2);
          
          // Memoize the result
          memo[n] = result;
          
          return result;
      }
      
      public static void Main()
      {
          Console.WriteLine(Fibonacci(50));
      }
  }  
  
        

Hasta luego 🖖