이 문서는 https://blog.bitsrc.io/understanding-memoization-in-javascript-to-improve-performance-2763ab107092 에서 번역한 글 입니다.

Understanding Memoization in JavaScript to Improve Performance

성능 향상을 위한 자바스크립트 메모이제이션 이해하기

우리 앱의 퍼포먼스를 향상시키는 작업이 간절 했다. 메모이제이션은 결과를 캐싱하고, 다음 작업에서 캐싱한 것을 재사용 하는 비싼 작업의 속도를 높이는 자바스크립트 기술 이다.

이 글에서는 메모이제이션을 사용하는 방법과 우리의 앱 성능을 높이는 최적화 방법을 알아 볼 것이다. 레츠고

Tips : JS앱을 만들 때, 코드를 중복하는 것 보다, 재사용하고 공유하는것이 더 낫다. Bit는 프로젝트 전반에서 쉽게 컴포넌트를 관리하고 공유를 할 수 있으며, 변경사항 업데이트하고 팀원간의 협력으로 빠르게 만들 수 있습니다.

메모이제이션: 기본 아이디어

만약 CPU 집약적인 작업을 할 경우, 캐시에 초기 작업 결과를 저장하여 사용함으로 써 최적화 할 수 있다. 만약 작업을 다시 수행해야 한다면, 어딘가에 저장되어진 동일한 결과를 단순히 반환 해주기만 하면 CPU가 다시 지루해지게 하지 않을 것이다.

다음과 같이 표현 할 수 있다.

function longOp(arg) {
    if (/* arg로 캐시된 작업결과 있는지 */) {
        return the cache
    }
    else {
        // 30분 동안 긴 작업을 수행한다.
        // 캐시에 결과를 저장한다.
    }

    return the result
}

longOp('lp') // 이 작업은 첫번째이기 때문에 30분동안 수행된다.
// 다음 캐시에 결과가 저장된다.

longOp('bp') // 이 인풋이 'bp'로 세팅된 작업은 첫번째이기 때문에 30분동안 수행된다.
// 다음 캐시에 결과가 저장된다.

longOp('bp') // 같은 작업
// 긴 작업 없이 캐시 결과를 반환한다. 1초 수행

longOp('lp') // 같은 작업
// 긴 작업 없이 캐시 결과를 반환한다. 1초 수행

위에 수도-함수(pseudo-function) 인 longOp CPU 사용량이 높은 비싼 함수 이다. 먼저, 특정 입력 값의 작업을 수행하고, 그 작업 결과를 캐싱한다. 같은 입력값을 가진 함수가 다시 호출 되면, 시간과 리소스를 소모하는 작업 대신 캐시에 저장된 이전 결과값을 반환한다.

lp 인자를 가진 첫번째 호출은 완료하는데 30분이 소모되는 시간이 걸리는 작업을 수행한다. 같은 입력값 lp와 함게 다시 호출 하면, 캐시에 저장된 이전 결과값을 반환하다. 이것은 1초만에 수행된다. bp 인자 호출 수행도 동일하다.

실제 예제를 봅시다. 제곱근 함수가 있다.

function sqrt(arg) {
    return Math.sqrt(arg);
}

log(sqrt(4)) // 2
log(sqrt(9)) // 3

우리는 sqrt 함수를 메모이제이션 할 수 있다.

function sqrt(arg) {
    if (!sqrt.cache) {
        sqrt.cache = {}
    }
    if (!sqrt.cache[arg]) {
        return sqrt.cache[arg] = Math.sqrt(arg)
    }
    return sqrt.cache[arg]
}

함수 속성인 캐시 객체에 각 결과가 저장된 sqrt 함수를 볼 수 있다.

참고로, 함수가 메모이제이션을 수행 할 때, 작업을 수행하기 위해 이동하지 않을 경우, 먼저 캐시를 생성하고, 캐시안에 입력값이 있는지 확인 하는 것이 이상적이다.

다음은 함수를 여러번 호출하는 것이다.

sqrt(9)
sqrt(9)
sqrt(4)

첫번째 호출인 파라미터 9 는 캐시 되지 않았으므로 계산이 수행되고 결과가 캐시 된다. 두번째 호출은 캐시된 결과를 반환 한다. 세번째 호출은 입력값이 처음이기에 계산을 수행 한다. 계산이 수행되고, 같은 입력값의 함수 호출을 위해 결과는 캐시되어진다.

우리는 로그를 추가하여 캐시에 저장된 객체를 볼 수 있다.

// ...
loq(sqrt.cache) // { "9" : 9, "4": 4}

또다른 예제로, 파라미터로 전달된 값의 제곱하는 square 함수가 있다.

function square(num) {
    return num * num;
}

log(squqre(2)) // 4
log(square(4)) // 16

다음과 같이 메모이제이션 할 수 있다.

function square(num) {
    if (!squre.cache) {
        square.cache = {}
    }
    if (!square.cache[num]) {
        return square.cache[num] = (num * num)
    }

    return square.cache[num]
}

sqrt 함수와 같이, 입력에 대한 결과를 가지고 있는지 확인한다. 만약 가지고 있다면, 캐시에서 결과를 반환 합니다. 그렇지 않은 경우, 계산을 수행하고, 결과를 반환 후 캐시에 저장한다.

log(square.cache) // undefined, 초기에는 캐시가 없다.

log(square(2)) // 4
log(sqaure.cache) // { "2" : 4 } 입력값 2가 캐시 되었다.

log(square(2)) // 4
// 간단하게, 캐시에 저장된 입력값2 에 대한 결과를 반환

log(square(4)) // 16, 계산 수행, 이전에 입력값 4 에 대한 캐시된게 없다.

log(square.cache) // { "2": 4, "4": 16 } 지금은 입력값4 가 캐시 되었다.

log(square(4)) // 16 캐시로부터 결과 값을 추측 할 수 있다.

메모이제이션: 구현

마지막 섹션에서는 메모이제이션 기능을 추가하기 위해 함수를 수정 해보도록 하겠다.

이제 우리는 모든 기능을 메모이제이션 할 수 있는 표준 함수를 생성 할 수 있다. 이 함수는 memoize 라고 한다.

function memoize(fn) {
    return function() {
        var args = Array.prototype.slice.call(arguments)
        fn.cache = fn.cache || {};
        return fn.cache[args] ? fn.cache[args] : (fn.cache[args] = fn.apply(this,args))
    }
}

위 함수는 다른 함수를 인자로 받고, 함수를 반환하는걸 볼 수 있다.

이 함수를 사용하기 위해 메모이제이션 하려는 함수를 memoize 함수 인수로 전달 한다.

memoizedFunction = memoize(functionToMemoize)
memoizedFunction(args)

예를 들어, 첫번째 예제를 봅시다.

function sqrt(arg) {
    return Math.sqrt(arg);
}

const memoizedSqrt = memoize(sqrt)

반환된 memoizedSqrt 함수는 이제 sqrt의 메모이제이션 버전이다.

자 이제 해보자.

// ...
memoizedSqrt(4) // 2 계산
memoizedSqrt(4) // 캐시

memoizedSqrt(9) // 계산
memoizedSqrt(9) // 캐시

memoizedSqrt(25) // 계산
memoizedSqrt(25) // 캐시

함수 프로토타입에 memoize 함수를 추가하여 우리 앱의 모든 함수에 memoize 함수를 상속하고, 호출 정의 할 수 있다.

Function.prototype.memoize = function() {
    var self = this;
    return function() {
        var args = Array.prototype.slice.call(arguments);
        self.cache = self.cache || {};
        return self.cache[args] ? self.cache[args] : (self.cache[args] = self(args))
    }
}

우리는 JS에서 정의 된 모든 함수는 Function.prototype 에서 상속 받는 것을 알고 있다. 그래서 Function.prototype에 추가된 어느 것이든 우리가 정의 한 모든 함수에서 사용 할 수 있다.

아래 예제를 보자.

function sqrt(arg) {
    return Math.sqrt(arg);
}

// ...

const memoizedSqrt = sqrt.memoize()

log(memoizedSqrt(4)) // 2, 계산
log(memoizedSqrt(4)) // 2, 캐시에서 반환

log(memoizedSqrt(9)) // 3, 계산
log(memoizedSqrt(9)) // 3, 캐시에서 반환

log(memoizedSqrt(25)) // 5, 계산
log(memoizedSqrt(25)) // 5, 캐시에서 반환

메모이제이션: 속도와 벤치마킹

메모이제이션의 목표는 속도이다. 메모이제이션은 속도를 위해 저장공간을 트레이드 오프 한다. 에릭슨 소비자랩에서 실시한 분석에 따르면, 느린 웹페이지를 기다리는 것은 호러 무비를 보는 것과 유사하다는 결과가 있다.

메모이제이션과 함께라면 우리 앱의 성능은 향상 된다.

메모이제이션 과 비-메모이제이션 함수 실행 시 차이점을 봅시다. Node가 제공하는 tie 기능을 이용하요 함수를 벤치마킹 할 것이다.

sqrt 함수 벤치마킹 하기

function sqrt(arg) {
    return Math.sqrt(arg)
}

const memoizedSqrt = memoize(sqrt)

console.time("non-memoized call")
console.log(sqrt(4))
console.timeEnd("non-memoized call")

console.time("memoized call")
console.log(sqrt(4))
console.timeEnd("memoized call")

$ node memoize
2
non-memoized call: 8.958ms
2
memoized call: 1.298ms

우리는 메모이제이션 함수보다 느린 비-메모이제이션을 보았다. 우리는 이유를 알고 있다. 메모이제이션 함수는 같은 입력동안엔 계산 하지 않고, 저장되어졌던 캐시 결과를 반환한다.

나는 많은 시간을 나의 컴퓨터에서 테스팅 하였으며, 메모이제이션 함수는 항상 비-메모이제이션 함수를 따라 잡았다.

Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
2
non-memoized call: 8.215ms
2
memoized call: 0.566ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
2
non-memoized call: 7.062ms
2
memoized call: 0.354ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
2
non-memoized call: 7.300ms
2
memoized call: 0.303ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
2
non-memoized call: 7.681ms
2
memoized call: 0.301ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
2
non-memoized call: 7.170ms
2
memoized call: 1.225ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$

다음으로 square 함수를 벤치마크 하였다.

function square(num) {
    return num * num;
}
const memoizedSqrt = memoize(square)
console.time("non-memoized call")
console.log(square(2))
console.timeEnd("non-memoized call")
console.time("memoized call")
console.log(square(2))
console.timeEnd("memoized call")

다음과 같은 결과를 얻었다.

$ node memoize
4
non-memoized call: 9.455ms
4
memoized call: 4.567ms

예상한대로 메모이제이션은 비-메모이제이션 보다 퍼포먼스가 좋다.

더 많은 테스트를 하였다.

Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
4
non-memoized call: 7.167ms
4
memoized call: 0.294ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
4
non-memoized call: 7.444ms
4
memoized call: 0.562ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
4
non-memoized call: 7.472ms
4
memoized call: 1.487ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
4
non-memoized call: 7.002ms
4
memoized call: 0.790ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
4
non-memoized call: 7.841ms
4
memoized call: 1.788ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$

메모이제이션: 언제 사용할까

일반적으로 메모이제이션은 실행 시간이 줄어들고, 앱의 성능에 영향을 미친다. 메모이제이션은 입력값에 따른 결과가 확정적일때 가장 잘 작동한다.

베스트 프랙티스에 따르면, 메모이제이션은 순수 함수로 구현 되어야 한다. 그 이유로, 순수 함수는 프로그램 상태를 변경시키지 않고(사이드이펙트) 입력값에 따라 아웃풋이 생성된다.

메모이제이션은 속도를 위해 공간을 버리기 때문에, 빠른 확인을 위해 입력 범위가 제한된 함수에서 사용 해야 한다.

메모이제이션은 GUI 렌더링, 스프라이트, 애니메이션 물리등에 사용되는 재귀함수를 처리 할 때 가장 좋다.

메모이제이션: 언제 사용하면 안될까

메모이제이션은 입력값에 의존하지 않고 시간이 지나면 변경되는 출력일 경우 사용하지 않아야 한다.

여기 예제가 보자.

function unpredicatble(input) {
    return input * Date.now()
}
log(unpredicatble(4))
log(unpredicatble(4))
$ node memoize
6169843078712
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
6169843091424

보다시피, 같은 파라미터로 함수를 호출 하였지만, 다른 결과/출력이 생성되었다.

시간이 지남에 따라 변경되는 출력은 메모이제이션이 현재 출력을 캐치 하지 못하므로, 이상적이지 못하다.

사용 사례: 피보나치

피보나치는 메모이제이션을 사용하여 최적화 할 수 있는 복잡한 알고리즘중 하나이다. 피보나치 수열은 첫번째 두개 이후에 앞의 두개를 합한 것이 특징이다.

1,1,2,3,5,8,13,21,34,55,89

각 숫자는 이전 두개 숫자 합이다.

F2 = F1 + F1 => (2 = 1+1)
F5 = F3 + F2 => (5 = 3+2)

Therefore,
Fn = Fn-1 + Fn-2

JS에서는 이렇게 구현 할 수 있다.

function fibonacci(num) {
    if (num == 1 || num == 2) {
        return 1
    }
    return fibonacci(num-1) + fibonacci(num-2)
}

이 함수는 num이 2를 초과하면 재귀가 됩니다. 자기 자신을 재귀적으로 호출 하여 감소시킵니다.

log(fibonacci(4)) // 3

피보나치를 메모이제이션 버전으로 실행하여 벤치마킹 해보자.

const memFib = memoize(fibonacci)
log('profiling tests for fibonacci')
console.time("non-memoized call")
log(memFib(6))
console.timeEnd("non-memoized call")
console.time("memoized call")
log(memFib(6))
console.timeEnd("memoized call")
$ node memoize
profiling tests for fibonacci
8
non-memoized call: 2.152ms
8
memoized call: 1.270ms

첫번째 호출은 2.1252ms가 걸렸고, 다음 호출은 캐시된게 호출 되어 1.270ms가 걸렸다. 0.882ms차이가 난다. 오마이갓

더 테스트 해보자.

$ node memoize
profiling tests for fibonacci
8
non-memoized call: 3.031ms
8
memoized call: 1.136ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
profiling tests for fibonacci
8
non-memoized call: 1.444ms
8
memoized call: 0.249ms
Admin@PHILIPSZDAVIDO MINGW64 /c/wamp/www/developerse/projects/trash
$ node memoize
profiling tests for fibonacci
8
non-memoized call: 1.200ms
8
memoized call: 0.242ms

당신은 어떤 포인트에서 메모이제이션 버전이 0ms가 걸리는 것을 볼 수 있다.

사용 예제: 팩토리얼

팩토리얼은 숫자를 1까지 순차적으로 감소시키면서 곱하는 것이다.

5! = 5 * 4 * 3 * 2 * 1
such that,
N! = N * (N-1) * (N-2) * (N-3) * ... * 2 * 1

JS에서는 다음과 같이 구현 할 수 있다.

function factorial(num) {
    if(num == 1 || num == 0) {
        return 1
    }
    return num * factorial(num-1)
}

팩토리얼은 재귀-바운드(recursive-bound) 알고리즘이며, 여러번 호출 하는데 많은 비용이 발생한다.

팩토리얼 20을 계산 해보자.

log(factorial(20)) // 2432902008176640000

매우 거대한 숫자이다. 그리고 다음과 같다.

console.time("factorial(20) call")
log(factorial(20))
console.timeEnd("factorial(20) call")
factorial(20) call: 1.932ms

팩토리얼은 단계적으로 숫자를 반복한다.

factorial(20)

이것은 다음과 같다.

factorial(20) = 20 * factorial(19)
20! = 20.19!
N! = N.(N-1)!

만약 우리가 이전 계산 결과를 캐싱 할 수 있다면, 함수의 실행 시간을 스피드업 할 수 있다.

매번 팩토리얼(19)를 찾는 대신 캐시에서 이전 결과 를 반환한다.

우리는 팩토리얼 함수를 메모이제이션 한다. 그러면 퍼포먼스 벤치마킹 할 수 있다.

const memFact = memoize(factorial)

log('profiling tests for factorial')
console.time("non-memoized factorial(20) call")
log(memFact(20))
console.timeEnd("non-memoized factorial(20) call")

console.time("memoized factorial(20) call")
log(memFact(20))
console.timeEnd("memoized factorial(20) call")

$ node memoize
profiling tests for factorial
2432902008176640000
non-memoized factorial(20) call: 2.956ms
2432902008176640000
memoized factorial(20) call: 2.084ms

메모라이제이션 팩토리얼은 더 나은 것이다.

결론

이 포스트에서, 메모이제이션이 무엇이며, 웹앱의 성능에 어떤 영향을 미치는지 배웠다.

다음으로 우리는 몇가지 함수를 만들고, 그것들의 메모이제이션 버전을 만들었다. 그런 다음 벤치마킹을 통해서 메모이제이션과 비-메모이제이션의 성능 차이를 확인 하였다. 마지막으로 우리는 몇가지 사용 예제를 통해서 메모이제이션이 어떻게 영향을 미치는지 보았다.

그렇지만, 메모이제이션은 큰 이점이 있지만, 비용이 따른다. 속도를 위해선 많은 메모리 사용량이 소비된다. 로우-메모리 함수에서는 알아차릴 수 없겠지만, 많은 RAM을 사용하는 함수를 처리 할때는 영향이 미친다.

이 문제나 다른 질문 사항이 있으면 언제든 메일을 보내거나 의견을 보내주세요.