(JS) memoization, currying

memoization

동일한 계산을 반복해야 할 때 이전 계산 결과를 저장해놓음으로써 효율을 높이는 것. 관례상 변수는 memo[]

var fibonacci = function ( ) {

var memo = [0, 1];

var fib = function (n) {

var result = memo[n];

if (typeof result !== 'number') {

result = fib(n - 1) + fib(n - 2);

memo[n] = result;

}

return result;

};

return fib;
}( );

* 클로저를 이용해 memo[]를 감췄다.

recursive를 사용하지 않고 iteration으로 짜면서 memo하려면 별도의 stack 변수를 하나 선언하고 거기다가 지나간 memo의 index들을 쌓아 둔 다음, 나중에 stack에서 꺼내면서 한꺼번에 memo를 업데이트하는 그런 로직이 들어가야 하는데 꽤 지저분해진다. 그래서 이런 경우 recursive를 쓰는게 깔끔함. iteration으로 고치면서 STL같은걸 사용하는 경우 오히려 더 느려질 수 있음. 속도 때문에 바꾸는거면 STL같은걸 쓰지 말아야 함.

이를 일반화하여, 메모이제이션 함수를 만들어 반환하는 함수 memoizer를 정의하면 이렇다.

var memoizer = function (memo, fundamental) {

var shell = function (n) {

var result = memo[n];

if (typeof result !== 'number') {

result = fundamental(shell, n):

memo[n] = result;

}

return result;

};

return shell;
};

* memoizer는 마지막에 ( )를 안붙였기 때문에 리턴하게 되는 변수 shell이 아니라 function (memo, fundamental) {...} 자체다.

메모이제이션할 함수를 fundamental로 전달하면 그 함수의 메모이제이션 형태를 반환해준다. 이 때 function(shell, n){ return shell( )... }형태로 메모이제이션할 함수(재귀적으로 호출될 함수) shell을 감싸서 전달해야 한다.

var fibonacci = memoizer([0, 1], function (shell, n) {

return shell(n - 1) + shell(n - 2)
});

함수형 프로그래밍은 이렇게 함수를 반환하거나 인자로 받을 수 있어, 임의의 함수를 입력으로 받아 다른 함수를 만들어 낼 수 있다는데 강점이 있다.

currying

여러 개의 인자를 받는 함수를 분리하여 인자를 하나만 받는 함수들의 체인으로 만드는 방법.

Function.method('curry', function ( ) {

var slice = Array.prototype.slice,

args = slice.apply(arguments),

that = this;

return function ( ) {

return that.apply(null, args.concat(slice.apply(arguments)));

};
});

var sum10 = sum.curry(10);
sum10(5);    // 15