[JS] 메모이제이션

메모이제이션

계산을 줄여 성능을 향상시키는 방법이다. 처음 계산하여 결과값이 나왔다면 저장하고,
나중에 동일한 인수에 대한 결과가 다시 필요할 경우 다시 계산하는 대신 저장된 결과를 return 한다. 
이렇게 결과를 캐싱하여 작업 속도를 높을 수 있다.

 

예제1 : 팩토리얼 함수

//메모이제이션을 이용하여 팩토리얼 함수 만들기

const memoizedFactorial = memoized(function A(n) {
  memoizedFactorialRunCnt += 1;
  if (n === 1) return 1;
  return n * memoizedFactorial(n - 1);
});

let memoizedFactorialRunCnt = 0; // 실행횟수 계산
console.log(memoizedFactorial(3)); // B(3)➡️ 6
console.log(memoizedFactorial(5));
console.log(`runCnt=${memoizedFactorialRunCnt}`);

memoizedFactorial에 함수를 인자로한 memoized를 선언되어 있다. 

function A(n) memoized의 인자이다.

 

function memoized(fn) {
  const memoizedTable = {}; // {3: 3 * 2, 2: 2 * 1, 1: 1}
  return function B(k) {
  	//캐싱된 값이 있다면 값을 리턴, 없을 경우 fn을 통해 값을 구해서 캐싱해준다.
    return memoizedTable[k] ?? (memoizedTable[k] = fn(k)); 
  };
}


// 화살표 함수로 표현
const memoized = fn => {
  const memoizedTable = {};
  return k => memoizedTable[k]
       ?? (memoizedTable[k] = fn(k));
};

 

memoizedTable : 캐싱되는 테이블

memoizedTable은 지속적으로 관리가 되어야 한다.  ➡️ 캐시된 값이 사라지면 안된다. ➡️ GC에 의해 제거되면 안된다. 

➡️ 클로저를 이용하자 ( 참조를 하면 GC에 의해 제거되지 않기 때문에 )

return 되는 B(k)함수로인해 EnvRec를 계속해서 참조하게 된다. 그래서 해당 함수가 사라지지 않고, 캐싱되는 테이블 또한 사라지지 않기 때문에 메모이제이션이 가능해진다.

memoized 인자로 넘어온(?) A(n)이 팩토리얼 값을 구해서 다시   memoized 함수에 넘겨주어 캐싱을 하게 된다. 

 

예제2 : 피보나치 수열

//캐싱할 함수 , 클로저 이용
function memoized(fn) {
  const memoizedTable = {};
  return function B(k) {
    return memoizedTable[k] ?? (memoizedTable[k] = fn(k));
  };
}

const memoizedFibo = memoized((n) => {
  if (n <= 1) return n;
  return memoizedFibo(n - 2) + memoizedFibo(n - 1);
});

memoizedFibo(3);
console.log("🚀 ~ memoizedFibo:", memoizedFibo(10));

 

아래는 루프와 재귀로 구현한 피보나치 수열이다.

//Loop
function fiboLoop(n) {
  if (n <= 1) return n;
  let prev = 0;
  let curr = 1;
  for (let i = 2; i <= n; i += 1) {
    // let temp = prev;
    // prev = curr;
    // curr = temp + curr;
    [prev, curr] = [curr, curr + prev]; // 이런 형식으로 많이 쓴다.
  }
  return curr;
}
console.log("🚀 ~ fiboLoop ~ fiboLoop:", fiboLoop(10));
console.log("------------------------");

// 재귀 함수
function fiboRecur(n) {
  if (n <= 1) return n;
  return fiboRecur(n - 2) + fiboRecur(n - 1);
}

console.log("🚀 ~ fiboRecur ~ fiboRecur:", fiboRecur(10));
console.log("------------------------");

 

 

추가 예정..🤓