반복 작업이 병목이라면, 메모이제이션

최근 ‘메모이제이션 구현하기’를 해보면서 이것저것 알아봤습니다. 메모이제이션이 리액트 내장 기능인 줄 알았으나, js, ts에서 쓸 수 있다는 걸 알았고 유용하게 쓰일 것 같아서 배운 것들을 공유하고자 이 포스팅을 씁니다.

 

 

메모이제이션(Memoization)이란?

 복잡한 연산을 수행하는 `complexFn(arg)`이라는 함수가 있다고 가정합니다. 이 함수는 굉장히 길고 복잡해서 메모리를 많이 씁니다. 그런데 이 함수의 인자인 `arg`에 같은 값이 자주 들어온다면 어떨까요? 두 번 계산할 필요 없이 이미 나와 있는 답을 저장해두었다가 재사용하면 되지 않을까요? 이게 메모이제이션의 핵심 목표입니다.

정리하자면 메모이제이션은 ‘같은 입력에 대해 동일한 결과를 반환하는 연산을 캐싱하여, 불필요한 재계산을 줄이기 위한 최적화 기법’이죠.

 

어떻게 구현되나?

메모이제이션을 이해하기 위해서는 자바스크립트의 고차함수와 클로저를 알고 있으면 좋습니다. 

고차 함수(Higher-Order Function)는 함수를 인자로 받거나 함수를 반환하는 함수를 의미합니다. 클로저(Closure)는 함수가 자신이 선언될 당시의 렉시컬 스코프(변수 환경)를 기억해서, 그 스코프가 사라진 뒤에도 해당 변수에 접근할 수 있는 현상을 의미합니다.

 

그렇지만 이 개념을 어떻게 한 줄씩만으로 이해하겠어요? 몰라도 됩니다. 아래 예제 코드에서 특이한 이 고차함수와 클로저의 특징 중 메모이제이션에 필요한 부분만 다시 설명해드릴게요.

function 고차함수(바깥인자){
  let 내부값 = 바깥인자;
	
  return function 내부함수(안쪽인자){
    내부값 += 안쪽인자;
	  console.log(`인자는 ${안쪽인자}, 내부값은 ${내부값}`);
  }
}

 

이런 형태는 특정 원시값(숫자, 문자열 등등)을 리턴하지 않습니다. 보시는 것처럼 return 뒤의 '함수가 리턴'되는 형태입니다. 이렇게 선언된 함수는 아래처럼 쓸 수 있습니다.

 

const 고차함수를_넣은_변수 = 고차함수(1); 

고차함수를_넣은_변수(3); //인자는 3, 내부값은 4
고차함수를_넣은_변수(5); //인자는 5, 내부값은 9

 

이렇게 쓰면 특이하게도 `내부값`은 매 호출마다 초기화되지 않고 이전 호출 결과를 유지합니다. `let` 내부값으로 선언된 값이 매 호출마다 `1`로 초기화되지 않고, 앞에서 호출되어 수정된 상태로 유지하다가 이어서 연산하는 모습을 볼 수 있습니다. `고차함수(1)`의 1이 함수 선언부에서 안쪽인자를 담당하고, 이후에 `고차함수를_넣은_변수(3)`, `고차함수를_넣은_변수(5)`로 연달아 호출되면서 1+3+5로 9인채로 마무리되고 있습니다. 이게 클로저입니다.

class를 사용해보신 분들은 내부값이 class의 필드, return된 고차함수를_넣은_변수가 메서드와 비슷하다고 생각하실 수도 있을 것 같아요.

 

다시 메모이제이션으로 돌아가면..

메모이제이션은 계산했던 값을 ‘저장’해 두었다가 같은 연산을 반복하려고 하면 저장한 값을 리턴해서 중복된 연산을 줄여준다고 말씀드렸습니다. 이 ‘값’들을 저장하는 곳이 고차함수 설명에서의 내부값부분입니다.

아주 간단하게 메모이제이션을 구현한 함수를 보겠습니다.

function memoization(complexFn){ // complexFn은 반복되는 연산을 수행하는 함수가 될거예요.
  const 결과저장 = new Map(); // 실제로는 그냥 Map보다는 WeakMap을 쓰는 것 같습니다.
	
  return (param)=>{ // 내부 함수는 function 이름이 딱히 필요하지 않아서, 화살표 함수로 선언할게요
		
    if(결과저장.has(param)){ // param을 키로 저장된 값이 있는지를 확인해요. 있으면 true
	  return 결과저장.get(param); // conplexFn의 내부 로직을 타지 않고, 저장된 값을 리턴
    }
      
    //저장된 값이 없나봐요
    const result = complexFn(param);
    결과저장.set(param, result); // param의 값을 키로, 연산 결과를 값으로 저장하도록 맵에 넣어요
    return result; // 연산의 결과를 리턴합니다. 
  }
}

 

프록시 패턴(Proxy Pattern)과 유사하네요. 특정 함수를 감싸서 캐시를 저장하는 로직을 추가로 진행한 후에 그 함수의 연산을 하고있으니까요.

이렇게 선언한 `memoization`을 사용해 보겠습니다.

 

const memoizedComplexFn = memoization(complexFn); 

 

이때 `memoization(complexFn(2));` 처럼 바로 선언하면 안됩니다. 이렇게 작성하면 `complexFn(2)`가 즉시 실행되고, 그 결과값만이 `memoization`에 전달됩니다. 함수 자체가 전달되지 않습니다. 메모이제이션을 추가한 `complexFn`이 반복적으로 호출될 때의 모습을 보겠습니다.

memoizedComplexFn(2); // 2의 결과가 리턴됩니다. 결과저장 맵은 { 2 : 2의결과} 상태입니다.
memoizedComplexFn(2); // 결과저장.get(2)를 리턴해서, 저장된 값을 리턴합니다. 연산하지 않았습니다.

memoizedComplexFn(4); // 4는 처음 들어오는 인자네요. 연산을 수행하고, 결과저장 맵에도 넣습니다.
//결과 저장 맵에는 {2: 2의결과, 4: 4의결과}가 들어있습니다. 
memoizedComplexFn(4); // 4는 결과저장 맵에 정답이 이미 있습니다. 연산을 다시 수행하지 않고 리턴합니다.

 

메모이제이션을 사용하지 않았다면 총 네 번 연산했을 텐데, 메모이제이션을 사용했기 때문에 중복된 연산을 줄이고 두번만 연산을 수행했습니다.

 

메모이제이션, 모든 함수에 다 쓰면 좋지 않나?

얼핏 생각해보면 앞으로 모든 함수는 메모이제이션으로 감싸서 중복 연산을 없애버리면 좋을 것 같습니다. 하지만 메모이제이션을 쓰기 위해서는 아래 조건을 충족해야 합니다.

 

1. 연산의 결과가 외부 상태의 영향을 받지 말 것

만약 complexFn이 외부 값을 참고하기 때문에 1시에 호출한 `complexFn(2)`의 결과와 2시에 호출한 `complexFn(2)`의 결과가 다르다면, 메모이제이션을 쓰면 안됩니다. 한번 연산한 값은 2를 키로 캐시에 저장하기 때문에 아무리 다시 호출해도 처음에 저장했던 1시의 결과만 리턴할 테니까요. 따라서 메모이제이션은 “같은 인자라면 무조건 같은 값이 나오는 함수”에만 사용해야 합니다.

 

2. 반복할 연산이 복잡

메모이제이션으로 반복을 줄일 연산이 고작 `파라미터 * 2` 정도라면 굳이 중복된 파라미터가 있었는지 확인하고 없다면 저장하는 로직을 타는게 더 손해일 수 있습니다.

 

3. 파라미터가 복잡하지 않을 것

앞서 구현해본 메모이제이션은 파라미터를 맵의 키로 사용하고 있었습니다. 이 키가 원시값이라면 `.has`정도로 쉽게 존재 유무를 확인하고 값을 꺼내올 수 있습니다. 하지만 키가 긴 Object거나, 첩첩이 쌓인 배열이라면 어떻게 될까요? Object가 동일한지를 판별하기 위해서 몇 depth까지 확인할까요? 몇중 배열까지를 허용할 것이고, 어떻게 동일한지를 확인할지까지 고려해봐야 합니다. 이 함수가 그런 확인 작업을 거칠 정도로 메모이제이션이 필요한건지도 고민해야 하겠죠.

 

3. 자주 사용되는 함수와 동일한 파라미터

연산의 결과를 메모리에 주구장창 저장하고 있는데 그 연산의 결과를 다시 꺼내 볼 일이 없다면 메모이제이션을 사용하면 안됩니다. 저장을 하기 위해서는 메모리를 사용해야 하고, 매번 연산을 수행할 때마다 그 파라미터가 이미 계산된 결과를 가지고 있는지 아닌지도 판단해야 하기 때문입니다. 동일한 값의 결과를 자주 찾지 않는 함수라면 메모이제이션을 쓰지 마세요.

 

‘자주’라면 얼마나..

이건 명확한 정답이 없습니다. 어떤 개발자는 쓰나 안쓰나 별 차이 없다고 메모이제이션을 적극 활용하기도 하고, 또 어떤 개발자는 자주 쓰면 얼마나 자주 쓸것이며, 연산이 길면 얼마나 길다고 메모이제이션을 쓰나 생각하기도 합니다. 따라서 메모이제이션 도입은 ‘병목이 실제로 발생했을 때’ 고민해보면 좋을 것 같습니다. 병목의 원인이 반복된 연산 때문인데 이 연산의 파라미터와 결과가 매번 동일하다면? 어떤 버튼을 클릭했을때 다발적으로 같은 연산을 불러낸다면? 이런 고민이 든다면 메모이제이션 도입을 고려해볼 수 있습니다.

 

 

마무리하며

지금 당장 메모이제이션을 쓰지 않더라도 자바스크립트의 중요한 개념을 아우르고 있으면서도 언젠가 도움이 될 수 있는 면이 많습니다. 포스팅이 도움이 되었으면 좋겠습니다!