Memoization - functional memoization

by Dawid Ryłko

HTML

<!-- Memoizacja funkcyjna -->

<a href="https://dawidrylko.com/memoizacja-harry-potter-i-myslodsiewnia/" target="_blank">Memoizacja funkcyjna</a>

TypeScript

const memoize = <F extends (...args: any[]) => any>(fn: F): F => {
  const cache = new Map<string, ReturnType<F>>();

  return ((...args: any[]) => {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      return cache.get(key)!;
    }

    const res = fn(...args);
    cache.set(key, res);
    return res;
  }) as F;
};

const test = () => {
  const fib = (n: number): number => (n < 2 ? n : fib(n - 1) + fib(n - 2));
  const fibMemoized = memoize(fib);

  const results: any[] = [];

  const measure = (label: string, fn: () => any, expectCached: boolean = false) => {
    const start = performance.now();
    const result = fn();
    const time = (performance.now() - start).toFixed(2);
    results.push({ call: label, result, time: `${time}ms`, cached: expectCached ? '✅ Yes' : '❌ No' });
  };

  measure('fib(35) normal', () => fib(35));
  measure('fib(35) memoized 1st', () => fibMemoized(35));
  measure('fib(35) memoized 2nd', () => fibMemoized(35), true);
  measure('fib(30) memoized', () => fibMemoized(30), true);
  measure('fib(40) normal', () => fib(40));
  measure('fib(40) memoized 1st', () => fibMemoized(40));
  measure('fib(40) memoized 2nd', () => fibMemoized(40), true);

  console.table(results);
};

test();