JavaScript Memoization

 

1. Memoization 메모이제이션이란?

기억되어야 할 것이라는 뜻의 라틴어에서 파생된 단어로, 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행 속도를 빠르게 해주는 기법으로 동적 계획 법(DP: Dynamic Programming)의 핵심이 되는 기술이다.

 

// 지정한 수가 소수인지 여부를 반환
var isPrime2 = function (num) {
  console.time('소요 시간');
  console.log('소수 판별 시작.', num);

  // TODO: 소수 판별 코드
  let prime = num > 1; // 1은 소수가 아님

  for (let i = 2; i < num; i++) {
    if (num % i === 0) {
      prime = false;
      break;
    }
  }

  console.log('소수 판별 결과.', prime);
  console.timeEnd('소요 시간');
  return prime;
};

 

소수는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수라고 한다. 그래서 위 코드는 소수를 판별하는 코드인데, 

입력받은 num이 소수인지 아닌지를 판단한다.

let prime = num > 1로 시작하여, 기본적으로 num이 1보다 크면 true 아니면 false로 초기설정을 했다.

for 반복문에서 2부처 num - 1까지 반복문을 돌며 num이 어떤 수로도 나누어 떨어지지 않는 지 확인을 한다. 나누어 떨어지면 소수가 아니므로 prime을 false로 설정하고, 반복문을 종료한다. 

 

function memo(fn) {
  return function (args) {
    fn._cache = fn._cache || {}; // 캐시 객체를 초기화하거나 유지
    if (fn._cache[args] !== undefined) {
      console.log('cache hit!', args, fn._cache[args]); // 캐시된 결과가 있을 경우 로그 출력
      return fn._cache[args]; // 캐시된 결과 반환
    } else {
      return (fn._cache[args] = fn(args)); // 없을 경우 함수 실행 후 결과를 캐시에 저장하고 반환
    }
  };
}

 

이 코드는 이제 메모이제이션 기능울 추가한 함수이다.

다른 함수 fn을 인자로 받아서, fn에 메모이제이션을 추가한 새로운 함수를 반환한다.

fn._cache = fn._cache || {}; 는 함수 fn의 캐시를 초기화한다. 만약에 이전의 캐시가 있다면 기존 캐시를 유지하고, 없다면 빈 객체 {}로 설정한다.

if(fn._cache[arg] !== undefined)로 캐시된 결과 있는지 확인한다.

• 캐시된 결과가 있다면 fn._cache[args]를 반환하고, cache hi 라는 메세지와 함께 캐시된 값을 출력한다.
• 캐시된 값이 없다면 fn(args)를 실행하여 결과를 fn._cache[args]에 저장하고 반환한다. 이렇게 저장된 결과는 이후에 같은 입력을 호출될 때 빠르게 반환된다.
• 아래 함수들을 실행을 하면 값에 대한 실행속도와 그것을 판단해준다.

isPrime(1);
isPrime(2);
isPrime(3);
isPrime(4);
isPrime(5);
isPrime(6);
isPrime(7);
isPrime(8);
isPrime(9);
isPrime(1000000007);
isPrime(1000000007);
isPrime(1000000007);

아래와 같이 실행 값이 이렇게 나온다.