[JS] 메모이제이션(Memoization)과 캐시 (Cache) / 리트코드 2623 풀이

1. 캐시(Cache) 

이전에 계산한 값을 임시로 저장하는 메모리 영역 

메모리 사용량을 줄일 수 있고 성능을 높일 수 있다. 

 

2. 메모이제이션(Memoization)

프로그래밍을 할 때 반복되는 결과를 메모리에 저장해서 다음 호출에도 같은 결과가 나올 때 캐시된 값을 가져오는 기법

즉 한 번 계산한 값을 기억하고 동일한 입력이 나오면 미리 계산된 값을 반환하여 함수의 실행 속도를 높여줄 수 있다.

 

 메모이제이션 기법을 활용하면 중복을 피하기 때문에 반복되는 결과에서 성능을 최적화 할 수 있다.

 

3. 코드 예시 

function add(n) {
    if (n === 0) {
        return 0;
    } else {
        return n + add(n - 1); 
    }
}

 

이러한 코드가 있다고 예시를 들어보자 여러번 호출하면 계산을 매번 다시해야한다. 

그렇다면 캐시를 사용해서 코드를 들어보자

 

let memo = {};

function add(n) {
    if (memo[n]) {
        return memo[n];
    }
    if (n === 0) {
        return 0;
    } else {
        let result = n + add(n - 1);
        memo[n] = result;
        return result;
    }
}

console.log(add(5)); // 15

 

add 함수는 주어진 숫자 n 부터 1까지의 합을 계산한다. memo 객체에 이전에 계산한 결과를 저장하여 동일한 입력에 대해 계속 반복되는 호출을 피할 수 있다. 이를 통해 실행시간을 줄일 수 있다. 

 

 

4. 리트코드 2623 Memorize 풀이

• 함수 fn이 주어지면 함수의 메모된 버전 반환
• 메모화된 함수는 같은 입력으로 두 번 다시 호출되지 않고, 캐시된 값 반환

function memoize(fn) {
  const cache = {}; 

  return function(...args) {
    const key = JSON.stringify(args); 
    if (cache[key] === undefined) { 
      cache[key] = fn(...args); 
    }

    return cache[key]; 
  };
}


function sum(a, b) {
  return a + b;
}


function fib(n) {
  if (n <= 1) {
    return 1;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
}


function factorial(n) {
  if (n <= 1) {
    return 1;
  } else {
    return factorial(n - 1) * n;
  }
}

const memoizedSum = memoize(sum);
const memoizedFib = memoize(fib);
const memoizedFactorial = memoize(factorial);

 

----------------------------------------------

코드 하나씩 설명

 

function memoize(fn) {
  const cache = {};

 

-함수 memorize는 다른 함수를 매개변수로 받아 그 함수의 메모이제이션된 버전 생성하고자 함

 

-const cache= {}를 통해 함수 내에 캐시를 저장할 객체 선언

이 객체는 함수 호출 결과를 저장할 것 

 

  return function(...args) {
    const key = JSON.stringify(args); 
    if (cache[key] === undefined) { 
      cache[key] = fn(...args); 
    }

    return cache[key]; 
  };
}

 

-const key = JSON.stringify(args): 함수에 전달된 인수들을 JSON 문자열로 변환

-if cache[key]===undefined: 만약 이전에 함수가 아직 호출된 적이 없다면 그냥 매개변수로 받은 함수 실행

 

-return cache[key] 캐시된 결과 반환

 

---각각의 함수를 정의하는 부분은 생략---------

 

 

---

함수 사용이 많은 자바스크립트에서 중복 호출을 줄이는 것은 성능을 정말 좋게 만든다... 열심히 연습해서 

최대한 자주 사용해보자 !