메모이제이션

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 메모이제이션은 함수형 프로그래밍 관련 이야기에서는 빠지지 않고 꼭 등장하는 사례이기도 하다.

함수형 자바스크립트에서 메모이제이션의 대표적인 사례로는, 한 번 들어온 인자에 대한 결과를 캐싱하여 함수 본체를 실행하지 않고 결과를 즉시 리턴하는 _.memoize 같은 고차 함수가 있다. 동일한 인자를 받으면 항상 동일한 결과를 리턴하는 순수 함수의 콘셉트를 잘 활용한 사례이다. 함수 본체에서 하는 일이 복잡하거나 연산이 많거나 내부에서 생성하는 자원이 많거나 시간이 오래 걸리는 함수일수록 메모이제이션을 통해 얻을 수 있는 성능적 이득도 커진다.

memoize 함수

메모이제이션 코드로 이해하기

메모이제이션에 대해 가장 빠르고 쉽게 이해하는 방법은 역시 코드를 통해 확인 하는 것이다. 간단 버전의 memoize 함수를 구현하여 메모이제이션의 콘셉트에 대해 파악해 보려 한다.

function memoize(func) {
  var cache = {};
  return function (arg) {
    if (cache[arg]) { // 이미 동일한 인자에 대한 결과가 있으면 리턴
      console.log('캐시로 결과 바로 리턴', arg);
      return cache[arg];
    }

    console.log('본체 실행', arg);
    // 받아둔 함수를 실행하면서 결과를 cache에 남겨둠
    return cache[arg] = func.apply(this, arguments);
  }
}

간단한 memoize 함수를 구현했다. memoize 함수를 이용해 mult5 라는 함수를 만든다.

var mult5 = memoize(function (a) {
  return a * 5;
})

console.log(mult5(1));
// 본체 실행 1 -> 5
console.log(mult5(2));
// 본체 실행 2 -> 10
console.log(mult5(1));
// 캐시로 결과 바로 리턴 1 -> 5
console.log(mult5(2));
// 캐시로 결과 바로 리턴 2 -> 10

매우 간단한 개념이다. memoize는 고차 함수다. 해당 로직을 memoize가 대신하도록 만든 사례이다. 메모이제이션은 인자가 하나일 때 활용성이 높다. 하지만 위의 memoize는 인자를 하나만 사용할 수 있다는 점과 문자열로 식별이 가능한 인자만 사용할 수 있다는 점이 아쉽다.

var add = memoize(function (a, b) {
  return a + b;
})

console.log(add(3, 5)); // 본체 실행 3 -> 8
console.log(add(3, 10)); // 캐시로 결과 바로 리턴 8 캐시가 동작했지만 3에만 의존하기 때문

var keys = memoize(function (obj) {
  return _.keys(obj);
});

console.log(keys({ a: 1, b: 2 }));
// 본체 실행 Object {a: 1, b: 2} -> ['a','b']
console.log(keys({ a: 1, b: 2 }));
// 캐시로 결과 바로 리턴 Object {a: 1, b: 2} -> ['a','b']
console.log(keys({ a: 10, b: 20 }));
// 잘 동작하는 듯 했지만 cache가 {[object Object]: ...} 이런 식으로 되기 때문에 오류

위의 코드를 보면 오류가 발생했다. JSON.stringfy(arguments); 를 활용해서 위와 같은 문제를 해결할 수 있다. 하지만 이 방법은 별도의 연산이 생겨 느리기도 하고 해결할 수 있는 범위가 적다. 이럴때는 역시 함수로 추상화를 하는 것이 좋다.

Partial.js의 _.memoize2

Partial.js에도 _.memoize가 있다. partial.js의 _.memoize는 Underscore.js의 _.memoize다. partial.js 에는 또 다른 메모이제이션 함수인 _.memoize2가 있다. 이 함수는 인자를 하나만 사용하는 함수에서만 사용할 수 있으며 인자로 객체만 사용할 수 있다.

_.memoize가 캐시를 함수에 기록한다면 _.memoize2는 캐시를 인자에 기록한다. _.memoize2는 함수 생성 시 함수의 고유 아이디를 만든 후, 인자로 들어오는 객체에 해당 고유 아이디를 기준으로 arg._memoize 밑에 담아 둔다. _.memoize2는 불변 객체 콘셉트와 함께 사용하기 위해 만든 함수이고 실무에서 사용하기 위해 만든 함수다.

/**
 * _.memoize2
 */

var f1 = _.memoize2(function (obj) {
  console.log('함수 본체에 들어옴');
  return obj.a + 10;
});

var obj1 = { a: 1 };
var obj2 = { a: 2 };

console.log(f1(obj1));
// 함수 본체에 들어옴 11
console.log(f1(obj1));
// 캐시 사용
console.log(f1(obj2));
// 함수 본체에 들어옴 12
console.log(f1(obj2));
// 캐시 사용

_.memoize2는 _.memoize와는 다른 특징과 장점을 가지고 있다. 우선 각 함수들에 대한 결과값을 인자로 사용된 객체에 담아두므로 한 번 사용하고 버리는 객체라면, 그 값은 별도의 관리 없이도 메모리에서 비워진다. 이것이 일단 가장 큰 장점이다. _.memoize는 결과 캐시가 함수에 쌓이기 때문에 함수를 없애거나 함수에 달린 캐시를 별도로 관리해야 하지만, _.memoize2는 사용한 인자에 결과 캐시가 쌓이므로 그 값을 계속 사용하느냐 아니냐에 따라 자동으로 메모리가 관리된다. 이것 외에도 값을 불변적으로 다룰 때 얻을 수 있는 실용적인 이점이 있다.

var evens = _.memoize2(function (list) {
  console.log('함수 본체에 들어와서 loop 실행');
  return _.filter(list, function (num) {
    return num % 2 === 0;
  })
});

var list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(evens(list)); // [2,4,6,8,10]
console.log(evens(list)); // [2,4,6,8,10] (캐시를 사용하여 loop를 돌지 않음)

list.push(11);
list.push(12);
console.log(list); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

console.log(evens(list)); // 캐시가 사용되어 12가 나오지 않음.

마지막 evens 실행 시에는 원하는 결과를 얻지 못했다. 값을 가변적으로 다뤘기 때문이다. 불변적으로 값을 다루게 되면 캐시도 자동으로 갱신되고, 값이 변경되지 않은 상태에서는 계속해서 캐시를 사용하기 때문에 성능적으로 이득을 얻을 수 있다.

var list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(evens(list)); // [2,4,6,8,10]
console.log(evens(list)); // [2,4,6,8,10] (캐시를 사용하여 loop를 돌지 않음)

list2 = list2.concat(11, 12);
console.log(list2); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

console.log(evens(list2)); // [2,4,6,8,10, 12]
console.log(evens(list2)); // [2,4,6,8,10, 12] (캐시를 사용하여 loop를 돌지 않음)

_.memoize2로 만든 함수는 인자를 한 개만 받을 수 있다. 두 개 이상의 인자를 필요로 하는 함수는 _.memoize2를 사용할 수 없다.

참조: 함수형 자바스크립트 프로그래밍