하조은의 블로그

오늘 발견한 재미있는 함수를 소개합니다

memoize

오늘은 memoize 함수를 소개합니다. 이 함수는 '메모이즈' 함수라고 읽는데 이는 메모이제이션(memoization)이라는 기술을 구현한 함수이기 때문입니다. 기술을 구현했다고 표현하니 어렵게 보이기도 하고 멋져보입니다. 여기서 말하는 기술이라고 표현한 메모이제이션을 위키피디아에서는 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이라고 설명합니다. 어떤 경우를 말하는 것이고 또 어떻게 구현하는지 살펴보겠습니다.

(1) 어제의 함수

Copycopy code to clipboard
1const arr1 = [1,2,3,4,5], arr2 = [6,7,8,9,10];
2function sum(arr) {
3  console.log("SUM!")
4  return arr.reduce((sum, num) => sum + num);
5}
6
7console.log(sum(arr1)); // "SUM!" 15
8console.log(sum(arr2)); // "SUM!" 40

sum은 배열을 받아서 값을 모두 더하는 함수입니다. 내부에는 로그 함수가 있어서 결과를 리턴하기 전에 "SUM!"이라는 문자열을 출력합니다. 이 문자열은 실제로 sum 함수가 호출되었는지 확인해주는 역할을 합니다.

Copycopy code to clipboard
1console.log(sum(arr1)); // "SUM!" 15
2console.log(sum(arr2)); // "SUM!" 40
3
4console.log(sum(arr1)); // "SUM!" 15
5console.log(sum(arr2)); // "SUM!" 40
6
7console.log(sum(arr1)); // "SUM!" 15
8console.log(sum(arr2)); // "SUM!" 40

이미 실행 결과를 알고 있는 arr1, arr2를 몇번씩 넣어도 "SUM!"은 출력됩니다. 이 지점이 위키피디아에서 정의한 '컴퓨터 프로그램이 동일한 계산을 반복해야 할 때'입니다.

(2) 오늘의 함수

이제 '이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거'하는 작업을 해보겠습니다. 우선 메모리에 계산한 값을 저장해야겠지요.

Copycopy code to clipboard
1var cache = {}; // [1] 계산된 값을 저장해둘 객체(캐시)
2function sum2(arr) {
3  if (cache[arr]) return cache[arr]; // [2] 저장된 값이 있으면 저장된 값을 리턴한다.
4  console.log("SUM!");
5  return cache[arr] = arr.reduce((sum, num) => sum + num); // [3] 없다면 값을 저장하고 결과를 리턴한다.
6}
7
8console.log(sum2(arr1)); // "SUM!" 15
9console.log(sum2(arr2)); // "SUM!" 40
10
11console.log(sum2(arr1)); // 15
12console.log(sum2(arr2)); // 40

개선된 sum2 함수는 cache라고 이름 붙여진 객체에 계산된 값을 저장함으로써 동일한 계산을 반복하지 않도록 했습니다. 덕분에 같은 값을 넣어 함수를 실행하니 "SUM!"이 출력되지 않게 되었습니다. '반복 수행을 제거'하는 목적을 달성했지만 cache의 선언 방식이나 sum2의 구현이 그리 근사하지 않습니다. 이제 memoize를 사용해보겠습니다.

Copycopy code to clipboard
1var sum = memoize(function(arr) {
2  console.log("SUM!")
3  return arr.reduce((sum, num) => sum + num);
4}, function(key) { return key; });
5
6console.log(sum(arr1)); // "SUM!" 15
7console.log(sum(arr2)); // "SUM!" 40
8
9console.log(sum(arr1)); // 15
10console.log(sum(arr2)); // 40

우리가 원하는 모습입니다. sum의 구현인 익명 함수를 memoize로 한번 실행시켜 만든 sum은 sum2와 같이 반복되는 작업을 하지 않습니다. 더군다나 cache를 선언하지도 않았습니다. 그럼 어떻게 계산된 값을 저장할까요? 이제 memoize의 구현을 살펴볼 시간이네요.

Copycopy code to clipboard
1function memoize(func, hasher) { // [1]
2  function f(...args) { // [2]
3    var key = hasher(...args); // [3]
4    if (f.cache[key]) return f.cache[key]; // [4]
5    return f.cache[key] = func(...args);
6  }
7  f.cache = {}; // [5]
8  return f;
9}

짧은 코드지만 알찬 코드입니다. 한줄씩 살펴보겠습니다. [1] memoize는 두개의 함수를 인자로 받습니다. 실제 로직을 담고 있는 func와 메모리의 키 값을 만들어낼 hasher가 있습니다. [2] f라고 정의된 함수는 이 함수의 최종 리턴 값입니다. 여기서 받는 ...args는 sum의 경우를 놓고보자면 arr1가 됩니다. [3] hasher는 f가 받은 값을 그대로 사용해서 key에 해당하는 값을 만들어냅니다. 이 값은 들어온 args에 따라 달라지겠죠. 이를 완전히 유니크한 키로 만드는 것은 hasher 함수를 잘 정의하는데 달려있습니다. [4] 만약에 캐시(f.cache)에 이미 저장된 값이 있으면 저장된 값을 리턴합니다. 그렇지 않으면 func의 실행 결과를 저장하고 그 값을 리턴합니다. [5] 캐시는 함수에 붙어서 리턴됩니다. 앞선 예제의 경우를 생각하면 sum에 붙어 있게됩니다. 때문에 원한다면 캐시를 비울 수도 있게 됩니다.

짧은 코드에 적은 데이터를 사용하는 함수이기 때문에 예제만으로 '프로그램 실행 속도를 빠르게'했다고 보긴 어렵습니다. 하지만 같은 방식으로 더 큰 데이터를 다루는 코드에서 사용한다면 그 차이를 확연하게 느끼실 수 있습니다.