원문: https://janhesters.com/blog/what-is-memoization-in-javascript-typescript
메모이제이션(memoization)와 캐싱은 프로그래밍의 기본 개념입니다.
메모이제이션을 이해하면 리액트의 고차 컴포넌트인 memo
와 useCallback
및 useMemo
훅, 리덕스의 선택자(selector) 등 메모이제이션을 기반으로 하는 개념들을 더 쉽게 이해할 수 있습니다.
이 글에서는 자바스크립트와 타입스크립트의 예시를 통해 메모이제이션에 대해 자세히 소개합니다.
메모이제이션는 계산을 줄여 성능을 향상시키는 방법입니다.
처음 계산하여 결괏값이 나왔다면, 이를 저장합니다. 동일한 인수에 대한 결과가 다시 필요한 경우 다시 계산하는 대신 저장된 결과를 사용합니다.
메모이제이션를 구현하는 방법에는 두 가지가 있습니다.
암시적 캐싱은 함수 내에서 캐싱 로직을 수동으로 구현하는 경우입니다.
간단한 add
함수가 있는데 이를 메모로 저장한다고 가정해 보겠습니다.
function add(a, b) {
return a + b;
}
add
함수를 다시 작성하여 결과를 메모하도록 할 수 있습니다.
이 글에 따라 코딩하려면 새 npm 프로젝트를 초기화하세요.
npm init --y
그런 다음 memoizeAdd()
라는 함수를 작성합니다.
// implicit-caching.js
function memoizeAdd() {
const cache = {};
return function memoizedAdd(a, b) {
const key = `${a},${b}`;
if (key in cache) {
return cache[key];
} else {
const result = a + b;
cache[key] = result;
return result;
}
};
}
const memoizedAdd = memoizeAdd();
console.log(memoizedAdd(3, 4)); // 결과를 계산하고 캐시합니다.
console.log(memoizedAdd(3, 4)); // 캐시에서 결과를 검색합니다.
console.log(memoizedAdd(5, 6)); // 새 결과를 계산하고 캐시합니다.
console.log(memoizedAdd(3, 4)); // 여전히 캐시에서 결과를 검색합니다.
여기서 무슨 일이 일어나는지 자세히 살펴보겠습니다.
memoizeAdd()
에서는 일반적으로 해시 테이블 또는 객체인 캐시를 생성하여 함수 호출의 결과를 저장합니다. 각 항목은 함수의 입력을 키로, 출력을 값으로 사용합니다.
const cache = {
"3,1": 4,
"9001,2012": 11_013,
};
다음으로, 두 개의 숫자 a
와 b
를 받는 memoizedAdd
함수를 반환합니다.
각 고유한 인수 조합은 하나의 키와 매칭됩니다.
이 함수는 메인 로직을 실행하기 전에 현재 입력을 키로 사용하여 캐시를 확인합니다. 입력이 캐시에 있으면 캐시 된 결과를 반환하고, 입력이 캐시에 없으면 결과를 계산하여 캐시에 저장한 다음 결과를 반환합니다.
memoizedAdd
함수를 호출하면 결과가 매개변수와 함께 저장됩니다. 동일한 매개변수를 사용하여 다시 호출하면 결과는 캐시에서 가져옵니다. 새로운 매개변수인 경우 함수는 결과를 다시 계산합니다.
이 코드를 실행하면 다음과 같은 출력이 표시됩니다.
$ node implicit-caching.js
7
7
11
7
고차 함수를 지원하는 언어에서는 데코레이터를 사용하여 함수의 핵심 로직을 변경하지 않고 메모이제이션를 추가할 수 있습니다.
고차 함수는 함수를 인수로 받아 함수를 반환하는 함수입니다.
이 개념이 생소하다면 “함수형 프로그래밍으로 자바스크립트의 잠재력 발휘하기”를 읽어보세요. 이 글에서는 고차 함수를 비롯한 여러 가지를 원론적인 수준에서 설명합니다.
이제 메모이제이션를 위한 데코레이터 함수의 간단한 예제를 살펴보세요.
// decorator-function.js
function memoize(fn) {
const cache = new Map();
return function (...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
};
}
function add(a, b) {
return a + b;
}
const memoizedAdd = memoize(add);
console.log(memoizedAdd(3, 4)); // 결과를 계산하고 캐시합니다.
console.log(memoizedAdd(3, 4)); // 캐시 된 결과를 반환합니다.
console.log(memoizedAdd(5, 6)); // 새 결과를 계산하여 캐시합니다.
console.log(memoizedAdd(3, 4)); // 여전히 캐시에서 결과를 검색합니다.
이 코드도 단계별로 살펴보겠습니다.
먼저 다른 함수인 fn
을 인수로 받는 memoize
함수를 만듭니다.
이 함수는 Map
을 사용하여 캐시를 초기화하는 것으로 시작합니다. 이 캐시는 함수 호출의 결과를 저장합니다. 객체 대신 Map
을 사용하는 이유는 더 다양한 키 유형을 처리할 수 있기 때문입니다.
const cache = new Map();
// 숫자를 캐시의 키로 사용합니다.
map.set("[3,1]", 4);
// 함수를 캐시의 키로 사용합니다.
map.set("[function increment(), function double()]", 42);
반환된 함수는 원하는 수의 인수를 받습니다. 이 함수는 인수를 문자열로 직렬화하여 캐시의 키로 사용합니다.
반환된 익명 함수는 실행하기 전에 해당 키가 캐시에 이미 존재하는지 확인합니다. 존재하는 경우 함수는 캐시 된 결과를 반환합니다.
캐시에 키가 없는 경우 익명 함수는 fn.apply(this, args)
를 사용하여 기존 함수를 호출합니다. 이 함수는 결과를 캐시에 저장하고 반환합니다.
이제 add
함수를 memoize
함수에 전달하여 메모이제이션할 수 있습니다.
memoizedAdd
함수는 암시적 캐싱 예제에서와 마찬가지로 작동합니다.
코드를 실행하면 동일한 결과가 나타납니다.
$ node implicit-caching.js
7
7
11
7
add
함수는 계산 비용이 적게 듭니다.
메모의 이점을 경험하려면 값비싼 함수를 메모해야 합니다.
대표적인 예가 피보나치
함수입니다. 피보나치 함수는 암기 외에도 코딩 면접에서 자주 출제되는 주제이므로 이 함수를 배워두는 건 유용합니다.
피보나치 수열은 각 숫자가 앞의 두 숫자의 합을 나열한 숫자입니다. 일반적으로 0과 1로 시작합니다. 피보나치 수열은 다음과 같이 시작됩니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
이를 수학적으로 표현하면 다음과 같이 표현할 수 있습니다.
자바스크립트에서 피보나치
함수는 다음과 같습니다.
// fibonacci.js;
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
n
이 0 또는 1이면 함수는 n
을 바로 반환합니다. 이는 피보나치 수열의 처음 두 숫자입니다.
n
이 1보다 큰 값인 경우, 이 함수는 fibonacci(n - 1)
과 fibonacci(n - 2)
를 한 번씩 두 번 호출하고 이 두 호출의 결과를 더합니다.
다음은, 이 함수가 fibonacci(4)
를 계산하는 방법을 보여주는 표입니다.
호출 | n | 계산 | 결과 |
---|---|---|---|
fibonacci(4) | 4 | fibonacci(3) + fibonacci(2) | 3 + 2 = 5 |
fibonacci(3) | 3 | fibonacci(2) + fibonacci(1) | 2 + 1 = 3 |
fibonacci(2) | 2 | fibonacci(1) + fibonacci(0) | 1 + 0 = 1 |
fibonacci(1) | 1 | 1 | 1 |
fibonacci(0) | 0 | 0 | 0 |
fibonacci(2) | 2 | fibonacci(1) + fibonacci(0) | 1 + 0 = 1 |
fibonacci(1) | 1 | 1 | 1 |
fibonacci(0) | 0 | 0 | 0 |
fibonacci(2)
는 fibonacci(4)
를 호출할 때 한 번, fibonacci(3)
에서 다시 두 번 계산하는 것을 볼 수 있습니다.
이러한 불필요한 중복 계산은 fibonacci
함수에 대한 입력 값이 커질수록 성능에 점점 부정적인 영향을 미칩니다. 이 글을 끝까지 읽어보시고 메모이제이션이 어떻게 이러한 계산을 매우 빠르게 최적화하는지 알아보시기를 바랍니다.
fibonacci
함수를 메모하기 전에 메모한 함수에 이름 속성을 추가하세요. 이렇게 하면 함수에서 오류가 발생할 때 스택 추적이 더 쉬워집니다.
// fibonacci.js;
function memoize(fn) {
const cache = new Map();
function memoizedFunction(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
}
// 이름 속성 추가
Object.defineProperty(memoizedFunction, "name", {
value: `memoized_${fn.name}`,
configurable: true,
});
return memoizedFunction;
}
Object.defineProperty
를 사용하여 memoizedFunction
의 name
속성을 memoized_${fn.name}
과 같이 보다 설명적인 값으로 설정합니다(여기서 fn.name
은 원래 함수의 이름입니다). configurable 속성을 설정하려면 필요한 경우 속성을 추가로 수정하거나 삭제할 수 있습니다.
이제 메모이제이션 효과를 측정할 준비가 되었습니다. fibonacci
함수를 메모하고 큰 숫자를 계산하는 데 걸리는 시간을 측정하세요.
// fibonacci.js;
function memoize(fn) {
const cache = new Map();
function memoizedFunction(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
}
Object.defineProperty(memoizedFunction, "name", {
value: `memoized_${fn.name}`,
configurable: true,
});
return memoizedFunction;
}
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(func, arg) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// 나노초를 밀리초로 변환합니다.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const n = 42;
console.log("Starting performance measurement:");
measurePerformance(fibonacci, n);
measurePerformance(memoizedFibonacci, n);
// 두 번째 호출로 캐싱 효과를 표시합니다.
measurePerformance(memoizedFibonacci, n);
measurePerformance
함수는 나노초 단위의 정확한 타임스탬프를 제공하는 process.hrtime.bigint()
로 시작 시간과 종료 시간을 캡처하여 주어진 함수의 실행 시간을 평가하고 보고합니다. 주어진 인수를 사용하여 함수를 실행한 후 종료 시간에서 시작 시간을 빼고 결과를 나노초 단위로 변환하여 밀리초 단위로 지속 시간을 계산합니다. 그런 다음 함수 이름, 인수, 출력 및 실행 기간을 콘솔에 기록합니다.
measurePerformance
을 사용하면 일반적인 피보나치 함수와 메모이제이션된 버전의 성능을 비교할 수 있습니다.
다음은 성능 측정 결과입니다.
$ node fibonacci.js
Starting performance measurement:
fibonacci(42) = 267914296, Time: 2405ms
memoized_fibonacci(42) = 267914296, Time: 2394ms
memoized_fibonacci(42) = 267914296, Time: 0ms
보시다시피 캐시에서 결과가 검색되므로 메모된 버전을 두 번째로 실행하는 것은 즉시 이루어집니다.
메모이제이션를 사용하는 경우 애플리케이션의 리소스와 성능을 관리하기 위해 .clear()
메서드를 구현할 수 있습니다. 그 이유는 다음과 같습니다.
이제 캐시 비우기 기능을 추가하세요.
// fibonacci.js;
function memoize(fn) {
const cache = new Map();
function memoizedFunction(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
}
memoizedFunction.clear = function clear() {
cache.clear();
};
Object.defineProperty(memoizedFunction, "name", {
value: `memoized_${fn.name}`,
configurable: true,
});
return memoizedFunction;
}
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(func, arg) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// 나노초를 밀리초로 변환합니다.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const n = 42;
// 메모이제이션된 피보나치를 측정합니다.
measurePerformance(memoizedFibonacci, n);
// 메모이제이션된 피보나치 두 번째 호출을 측정합니다.
measurePerformance(memoizedFibonacci, n);
// 캐시를 지우고 다시 측정합니다.
console.log("Clearing cache and measuring again:");
memoizedFibonacci.clear();
measurePerformance(memoizedFibonacci, n);
그런 다음 결과가 이미 성공적으로 메모이제이션된 후 .clear()
메서드를 호출하도록 사용 예제를 수정합니다.
$ node fibonacci.js
memoized_fibonacci(42) = 267914296, Time: 2456ms
memoized_fibonacci(42) = 267914296, Time: 0ms
Clearing cache and measuring again:
memoized_fibonacci(42) = 267914296, Time: 2484ms
보시다시피 캐시를 지우면 함수가 결과를 다시 계산합니다.
지금까지 모든 코드는 자바스크립트로 작성되었습니다. 이제 코드 예제를 타입스크립트로 전환하겠습니다.
타입스크립트와 노드 유형을 설치합니다.
$ npm i --save-dev typescript @types/node
added 3 packages, and audited 4 packages in 1s
found 0 vulnerabilities
그런 다음 새 타입스크립트 프로젝트를 초기화합니다.
$ npx tsc --init
Created a new tsconfig.json with:
TS
target: es2016
module: commonjs
strict: true
esModuleInterop: true
skipLibCheck: true
forceConsistentCasingInFileNames: true
You can learn more at https://aka.ms/tsconfig
이제 타입스크립트로 memoize
함수를 작성할 수 있습니다.
// fibonacci.ts;
type AnyFunction = (...args: any[]) => any;
interface MemoizedFunction<T extends AnyFunction> extends CallableFunction {
(...args: Parameters<T>): ReturnType<T>;
clear: () => void;
}
function memoize<T extends AnyFunction>(fn: T): MemoizedFunction<T> {
const cache = new Map<string, ReturnType<T>>();
const memoizedFunction = function (...args: Parameters<T>): ReturnType<T> {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key)!;
}
const result = fn(...args);
cache.set(key, result);
return result;
} as MemoizedFunction<T>;
memoizedFunction.clear = function clear() {
cache.clear();
};
Object.defineProperty(memoizedFunction, "name", {
value: `memoized_${fn.name}`,
configurable: true,
});
return memoizedFunction;
}
function fibonacci(n: number): number {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(
func: MemoizedFunction<typeof fibonacci>,
arg: number
) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// 나노초를 밀리초로 변환합니다.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const n = 42;
// 메모이제이션된 피보나치를 측정합니다.
measurePerformance(memoizedFibonacci, n);
// 메모이제이션된 피보나치 두 번째 호출을 측정합니다.
measurePerformance(memoizedFibonacci, n);
// 캐시를 지우고 다시 측정합니다.
memoizedFibonacci.clear();
measurePerformance(memoizedFibonacci, n);
여기서는 타입스크립트 일반 함수 타입을 나타내는 AnyFunction
타입을 만듭니다. 이 타입은 유연하며 임의의 수의 임의의 타입의 인수를 받고 임의의 타입을 반환하는 모든 함수를 허용합니다.
다음으로, 기본 제공되는 CallableFunction
인터페이스를 확장하고 명확한 메서드를 도입하는 제네릭 형식의 MemoizedFunction
인터페이스를 정의합니다. 여기서 T
는 AnyFunction
타입과 일치하는 모든 함수로 제한되는 제네릭 형식의 매개변수입니다. 이 인터페이스는 메모이제이션 된 함수가 동일한 매개변수를 받아들이고 동일한 타입을 반환한다는 점에서 원래 함수처럼 작동하도록 보장하며, clear
메서드를 추가로 노출합니다.
이제 메모이제이션 된 함수가 MemoizedFunction
인터페이스를 반환하도록 메모이제이션 함수를 구현할 수 있습니다. as
키워드를 사용하면 반환되는 함수가 MemoizedFunction
임을 타입스크립트에 알릴 수 있습니다.
이제 memoizedFibonacci
위로 마우스를 가져가면 타입스크립트가 함수의 올바른 타입을 알 수 있습니다.
const memoizedFibonacci: MemoizedFunction<(n: number) => number>;
또한 타입스크립트는 메모이제이션 된 함수의 .clear()
메서드에 대해서도 알고 있습니다.
(property) MemoizedFunction<(n: number) => number>.clear: () => void
이 함수에는 아직 문제가 있습니다. 현재 메모이제이션는 각 인수에 대한 전체 함수 호출의 결과만 캐시하고 중간 재귀 호출의 결과는 캐시하지 않습니다.
특정 문제를 해결하기 위해 메모이제이션 없이 재귀를 사용하면 어떤 잠재적인 문제가 있을까요?
중복 계산으로 인해 계산 시간과 리소스 사용량이 많이 증가한다는 것입니다.
큰 숫자 n
으로 함수를 호출한 다음 n + 1
로 함수를 호출합니다.
// fibonacci.ts
// ... 이전 코드는 동일합니다.
const n = 42;
measurePerformance(memoizedFibonacci, n);
measurePerformance(memoizedFibonacci, n + 1);
그런 다음 코드를 실행하여 42
와 43
의 성능 차이를 확인합니다.
$ npx tsx example-5.ts
memoized_fibonacci(42) = 267914296, Time: 2442ms
memoized_fibonacci(43) = 433494437, Time: 3975ms
보시다시피 fibonacci(43)
는 결과가 이미 캐시 되어 있음에도 불구하고 fibonacci(42)
를 처음부터 다시 계산하기 때문에 훨씬 더 오래 걸립니다. 다른 모든 중간 재귀 호출에서도 동일한 문제가 발생합니다.
피보나치
함수를 구현할 때 메모이제이션를 사용하면 이 문제를 해결할 수 있습니다.
// fibonacci.ts
// ... `memoize`도 위와 동일합니다.
function fibonacci(n: number): number {
if (n <= 1) {
return n;
}
return memoizedFibonacci(n - 1) + memoizedFibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(
func: MemoizedFunction<typeof fibonacci>,
arg: number
) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// 나노초를 밀리초로 변환합니다.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const numbers = [10, 20, 30, 40, 42, 43, 500];
numbers.forEach((n) => {
measurePerformance(memoizedFibonacci, n);
});
피보나치
함수를 정의한 후 메모가 된 버전을 사용하여 다음 숫자를 계산합니다.
이제 다양한 큰 숫자에 대해 함수를 실행해 보세요.
$ npx tsx fibonacci.ts
memoized_fibonacci(10) = 55, Time: 0ms
memoized_fibonacci(20) = 6765, Time: 0ms
memoized_fibonacci(30) = 832040, Time: 0ms
memoized_fibonacci(40) = 102334155, Time: 0ms
memoized_fibonacci(42) = 267914296, Time: 0ms
memoized_fibonacci(43) = 433494437, Time: 0ms
memoized_fibonacci(500) = 1.394232245616977e+104, Time: 0ms
이제 아무리 큰 함수를 호출해도 계산이 거의 즉각적으로 이루어집니다.
따라서 메모이제이션를 진행할 때는 스스로에게 물어보세요. “무엇을 메모이제이션하고 싶은가?"라고 자문해 보세요. 외부 함수만 메모이제이션하고 싶으신가요, 아니면 구현의 중간 결과도 메모이제이션하고 싶으신가요?
메모이제이션는 언제 사용하나요?
메모이제이션는 다음과 같은 경우에 유용합니다.
아시다시피 메모이제이션는 반복 계산을 피함으로써 작업의 시간 복잡성을 줄이고 컴퓨팅 리소스에 대한 부하를 줄여 성능을 향상시킵니다.
하지만 메모이제이션에는 단점도 있습니다.
좋은글 감사합니다 ^^