LeetCode 2623.Memoize 문제를 풀면서 메모이제이션에 대해 공부하게 되어 그 내용을 정리하려고 합니다.

문제 링크

내 풀이 링크

메모이제이션

메모이제이션(memoization)
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.
-위키백과-

메모이제이션을 JavaScript를 사용해 여러가지 방식으로 작성해 봤습니다. 여기서는 총 5가지로 나눠 정리했습니다.

1. 전역 객체를 이용한 방법
2. 클로저를 이용한 방법
3. Map 객체를 이용한 방법
4. 모듈 패턴을 이용한 방법
5. lodash의 memoize함수를 사용한 방법

전역 객체를 이용한 방법

JavaScript에서 전역 객체를 선언하여 그 객체를 사용해 결과를 저장하고 접근하는 방식입니다.

// 전역 객체
const memo = {};

// 계산을 수행하는 함수
function calculateFunction(input) {
  // 계산 수행
}

// 메모이제이션 함수 
function memoizedFunction(x) {
  if(!Object.hasOwn(memo, x)) {
    // 캐시된 결과가 없다면 memo객체에 계산 결과 저장
    memo[x] = calculateFunction(x);
  }
  
  return memo[x];
}

이 방식은 전역 변수를 사용합니다. 그래서 전역 네임스페이스를 오염시키기 떄문에 좋은 방법은 아닙니다.

---

클로저를 이용한 방법

클로저를 이용하는 방법도 위의 코드와 크게 다르지 않습니다.

// 계산을 수행하는 함수
function calculateFunction(input) {
  // 계산 수행
  return input + 100000;
}


// 메모이제이션을 적용할 함수를 생성하는 함수
function createMemoizedFunction(fn) {
  const cache = {};
  
  return function(x) {
    if(!Object.hasOwn(cache, x)) {
      cache[x] = fn(x);
    }
    return cache[x];
  }
}

const memoizedFunction = createMemoizedFunction(calculateFunction);

console.log(memoizedFunction(5)) // 100005
console.log(memoizedFunction(5)) // 100005 캐시된 결과 반환

클로저를 이용하여 메모이제이션을 구현하는 방식은 함수 내부에 캐시를 숨겨서 외부에서 접근할 수 없도록 합니다. 전역 객체를 이용한 방법과 달리 전역 공간을 오염시키지 않고, 캐시가 해당 함수의 스코프 내에 존재하기 때문에, 외부에서 직접적으로 캐시에 접근하거나 이를 변경하는 것을 방지할 수 있습니다.

---

Map 객체를 이용한 방법

cache를 일반 객체가 아닌 Map을 사용해도 됩니다.

// 계산을 수행하는 함수
function calculateFunction(input) {
  // 계산 수행
  return input + 100000;
}

function createMemoizedFunction(fn) {
  // Map 객체를 캐시로 사용
  const cache = new Map();
  
  return function(x) {
    if(!cache.has(x)) {
      cache.set(x, fn(x));
    }
    return cache.get(x);
  }
}

const memoizedFunction = createMemoizedFunction(calculateFunction);

console.log(memoizedFunction(5)) // 100005
console.log(memoizedFunction(5)) // 100005 캐시된 결과 반환

---

모듈 패턴을 이용한 방법

function calculateFunction(input) {
  return input + 10000;
}

const memoizationModule = (function() {
  const cache = {};
  
  function createMemoizedFuction(fn) {
	return function (x) {
      if(!Object.hasOwn(cache, x)) {
        cache[x] = fn(x);
      }
      return cache[x];
    }
  }
  
  return createMemoizedFuction: createMemoizedFuction;
})()

const memoizedFunction = memoizationModule.createMemoizedFuction(calculateFunction);

console.log(memoizedFunction(5)); // 10005
console.log(memoizedFunction(5)); // 10005 캐시된 결과 반환

모듈 패턴은 즉시 실행 함수(IIFE)와 클로저를 사용하여 작성할 수 있습니다.

---

lodash의 memoize함수를 사용한 방법

lodash 라이브러리의 memoize 함수를 사용하면 더 쉽게 메모이제이션을 적용할 수 있습니다.
lodash의 memoize 함수에 인자로 메모이제이션을 적용할 함수를 건네주기만 하면됩니다.

먼저, lodash 라이브러리를 프로젝트에 추가합니다.

npm i lodash

그리고 lodash라이브러리에서 memoize 함수를 불러와 사용합니다.

// lodash 라이브러리에서 
import { memoize } from 'lodash';

// 메모이제이션을 적용할 함수
function calculateFunction(input) {
  return input + 100000;
}

// lodash의 memoize 함수로 메모이제이션 적용
const memoizedFunction = memoize(calculateFunction);

// 함수 호출
console.log(memoizedFunction(5)); // 100005
console.log(memoizedFunction(5)); // 캐시된 결과로 바로 100005 반환