메모이제이션(Memoization)이 작동하는 방식을 이해하려면 우리는 캐싱(Caching)의 의미를 알아야 한다. 캐싱은 나중에 사용하기 위한 값을 저장하는 방법이다.
학교에 가져가는 가방과 필통을 캐싱으로 생각할 수 있다.
등교 이후 학교에서 연필이 필요할 때마다 연필을 가지러 집에 갔다가 학교에 와서 연필을 사용하고, 다 쓰면 집에 돌려놓고 다시 학교로 돌아온다고 생각을 해보자. 매번 이렇게 하는 것보다는 가방에 들어 있는 필통에 넣었다 뺐다 하면서 사용하는 것이 편하다.
완벽한 예시가 아닐 수도 있으나, 그냥 이런 느낌이다.
캐싱은 프로그램을 빠르게 하며, 일부 데이터에 쉽게 접근하는 방법이다.
그리고 메모이제이션은 우리가 이야기할 캐싱의 특정 형태다.
이 메모이제이션은 동적 프로그래밍에 많이 사용된다.
메모이제이션에 대해 알아보기 전에 실제 코드에서 어떻게 사용이 되는지부터 보자. 자바스크립트로 설명을 할 것이다.
add94 라는 함수가 존재하며, 이 함수는 94를 더한 값을 반환한다.
그리고 이 함수를 세 번 실행시켰다.
이 함수를 세 번 실행하게 되었을 때 100이라는 값을 반환하는 동일한 계산임에도 불구하고 작업마다 함수의 처음으로 돌아가서 실행을 해야 한다.
그래서 뭐 어쩌라고? 별로 와닿지 않는다면 다음 그림을 보자.
console.log("아주 긴 시간");부분에 어마어마한 연산이 추가되어 컴파일 비용이 많이 드는 코드가 있다고 생각을 해보자.
이제는 이 코드가 비효율적이라고 느껴질 것이다. 이런 상황에서 우리는 캐싱과 메모이제이션을 통해 이를 최적화 할 수 있다.
cache라는 비어있는 객체를 만들고, memoizedAdd94 라는 함수를 만들었다. 이 함수는 전에 만들었던 add94와 같은 결과를 반환하지만, 특별한 방법을 통해 조건을 분기한 함수다.
cache에 n이 존재하면 그것을 그대로 반환하며 그렇지 않으면 연산 후 이를 캐시에 저장한다. 그리고 그 cache[n]을 반환한다.
add94 함수가 연산이 이루어지기 전 “아주 긴 시간”을 콘솔에 찍었던 것처럼 memoizedAdd94 함수에도 똑같이 적어주었다.
이제 새로 만든 함수를 아까와 같이 세 번 실행해보자
이번에는 함수를 세 번 실행하였으나, “아주 긴 시간”이 콘솔에 한 번밖에 찍히지 않았다. 18번 라인의 함수가 실행된 이후 cache 객체에는 아래와 같이 프로퍼티가 추가될 것이다.
그리고 이후에 실행되는 동일한 매개변수를 전달받은 함수가 실행될 때는 in 연산자를 통해 객체(해시테이블)에 주어진 키가 있는지 확인하게 되고, 바로 cache[6]을 반환하게 된다.
이것이 메모이제이션이다.