memoize 함수 만들기

2623. Memoize

Given a function fn, return a memoized version of that function.

A memoized function is a function that will never be called twice with the same inputs. Instead it will return a cached value.

You can assume there are 3 possible input functions: sum, fib, and factorial.

sum accepts two integers a and b and returns a + b.
fib accepts a single integer n and returns 1 if n <= 1 or fib(n - 1) + fib(n - 2) otherwise.
factorial accepts a single integer n and returns 1 if n <= 1 or factorial(n - 1) * n otherwise.

인자로 받은 함수를 이용하여 이미 계산이 수행된 경우는 다시 수행하지 않고 memoize된 함수를 리턴하는 문제이다.

1. 인자를 key로 잡고 연산값을 value로 넣는다.
2. 들어온 인자를 보고 key가 있으면 해당 value를 리턴하고, 없으면 연산 후 해당 인자의 key-value 저장한다.

문제를 보고 위 두 가지 생각을 잡았고, 문제를 풀어보았다.
처음에는 Map을 생성해서 아래 코드처럼 풀었었다.

function memoize(fn: Fn): Fn {
  const memo = new Map();

  return function (...args) {
    const key = JSON.stringify(args);
    if (memo.has(key)) return memo.get(key);
    else {
      memo.set(key, fn(...args));
      return memo.get(key);
    }
  };
}

풀고 보니 memo객체에서 get, set해 오는 과정이 번거로워보였다.

그러던 중 mdn에서 Function.prototype.apply() 함수를 찾았다.

apply는 첫번째 인자로 func를 호출하는데 제공될 this의 값, 두번째 인자로 호출할 때 전달할 인자를 받는다.

이 함수는 아래와 같은 경우에 사용된다. (더 자세한건 위 공식문서 참조!)

1. 배열에 배열을 붙이기 위해 apply 사용하기
2. apply 와 내장함수 사용
3. 생성자 체이닝을 위한 apply 사용

이 중 내가 사용할 경우는 3번 경우다.

function memoize(fn: Fn): Fn {
    const memo = {};
    return function(...args) {
        const key = JSON.stringify(args);
        if (key in memo) return memo[key]
        else return (memo[key] = fn.apply(this, args));
    }
}

결과적으로 같은 방식으로 memoize 했지만, 코드가 더 간결해진 것 같다.
(근데 런타임은 apply를 사용하지 않은 경우가 살짝 더 빠르게 나온다.)