Memoization
메모이제이션은 결과를 캐싱하고, 다음 작업에서 캐싱한 것을 재사용하여 비싼 작업의 속도를 높이는 자바스크립트 기술이다.
처음 메모이제이션에 대해 공부할 때 저 위에 있는 말이 도대체 뭔말이냐 싶었다. 쉽게 내 나름대로 설명해보자면, 만약 5 * 6 * 2 * 3 * 1 의 결과를 구해야 한다면 계산기 혹은 머리속에서 5와 6을 곱하고 그 값에서 2를 곱하고 또 그 값에서 3을 곱하고 1을 곱할 것이다. 위는 비교적 간단한 연산이니 쉽게 값을 구할 수 있겠지만, 만약 곱해야 하는 숫자가 100개라면??? 10000개라면???? 그리고 이 연산을 어딘가 재사용해야 한다면???? 매번 100개의 숫자를 곱해서 답을 구하는 것 보다는, 한 번 연산된 결과값을 포스트잇에 적어놓고 그 값을 계속 재사용 하는 것이 속도와 성능 면에서 훨씬 효율적일 것이다.
여기서 이야기하는 '포스트잇에 적어놓고 그 값을 계속 재사용한다' 라는 개념이 바로 메모이제이션이다. 포스트잇은 메모이제이션에서 주로 캐시(Cache) 혹은 메모(Memo) 스토리지(Storage) 라고 이야기하며 결과를 어딘가 적어놓는 것을 캐싱한다 라고 표현한다.
아래는 제곱근을 구하는 예제이다.
function sqrt (num) {
return Math.sqrt(num);
}
sqrt(4) // 2
sqrt(9) // 3우리는 이 함수를 메모이제이션 할 수 있다.
function sqrt (num) {
if(!sqrt.cache) {
sqrt.cache = {};
}
if(!sqrt.cache[num]) {
return sqrt.cache[num] = Math.sqrt(num);
}
return sqrt.cache[num]
}참고로, 함수가 메모이제이션을 수행 할 때, 작업을 수행하기 위해 이동하지 않을 경우 먼저 캐시를 생성하고 캐시 안에 입력값이 있는지 확인하는 것이 이상적이다.
위의 함수를 여러번 호출해보면
sqrt(100)
sqrt(100)
sqrt(200)- 첫 번째 호출에서의
100은 캐싱 된 적이 없으므로 계산이 수행되고 결과를 캐싱한다. - 두 번째 호출은 저장되어있는 (캐싱되어있는) 값을 반환한다.
- 세 번째 호출은 입력값이 처음이기에 계산을 수행한 후 결과를 캐시에 저장한다.
Memoizatioin 구현하기
Memoize 함수 만들기
function memoize(func) {
const cache = {};
return function () {
const key = JSON.stringify(arguments);
if (cache[key] === undefined) {
cache[key] = func.apply(this, arguments);
}
return cache[key];
};
};.apply(this, arguments)는 한 함수 호출에서 다른 함수 호출로 모든 정보를 전달하는 스탠다드한 방법이다.key는Array.prototype.slice.call(arguments)로도 쓸 수 있다. arguments는 함수에 들어온 인자를 배열 형식으로 반환하는데, 진짜 배열이 아닌 유사배열이기 때문에 배열의 메소드를 사용 할 수 없다. 이 때 call 혹은 apply를 사용한다. 배열의 프로토타입에 있는 slice 함수를 빌려 쓰는것이다.
첫 번째 예제를 memoize 함수에 적용시켜보았다.
function sqrt (num) {
return Math.sqrt(num);
}
function memoize (func) {
const cache = {};
return function () {
const key = JSON.stringify(arguments);
if (cache[key] === undefined) {
cache[key] = func.apply(this, arguments);
}
return cache[key];
};
};
const memoizedSqrt = memoize(sqrt)
console.log(memoizedSqrt(4)) // 계산
console.log(memoizedSqrt(4)) // 캐시
console.log(memoizedSqrt(9)) // 계산
console.log(memoizedSqrt(9)) // 캐시
console.log(memoizedSqrt(25)) // 계산
console.log(memoizedSqrt(25)) // 캐시메모이제이션을 사용 하기 좋을 때
위와 같이 메모이제이션을 하면 실행시간이 줄어들고 퍼포먼스가 좋다. 가장 좋은 경우는 메모이제이션이 순수 함수로 구현되어 있을 때이다. 순수 함수는 외부의 개입 없이 입력값에 따라 아웃풋이 생성된다. 즉 입력값에 따른 결과가 확정적일 때 가장 잘 동작한다. 메모이제이션은 애니메이션이나 스프라이트와 같은 재귀함수를 처리 할 때 가장 좋다.
메모이제이션을 사용 하면 안될 때
다만 메모이제이션은 속도를 위해 공간을 버리기 때문에 입력 범위가 제한된 함수에서 사용해야 한다. 많은 RAM을 사용하는 함수를 처리 할때는 치명적이다. 또한 입력값에 의존하지 않고 시간이 지나면 변경되는 출력일 경우 메모이제이션이 변경된 출력을 캐치하지 못하므로 사용하지 않는 것이 좋다.
