고전적인 CS 질문 중 하나는 Fibonacci 시퀀스를 생성하는 것입니다. 솔루션 중 하나는 재귀 함수이며 다음과 같습니다.

function fib(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fib(n - 1) + fib(n - 2);
}

위의 재귀 피보나치 함수의 주요 문제점은 비용이 많이 드는 함수라는 것입니다. 자신을 너무 많이 호출합니다. 제 형편없는 2015 Macbook air에서 fib(40)을 호출하는 데 약 30초가 걸렸고(자신을 102,334,155번 호출) fib(45)는 거의 5분(자신을 1,134,903,170번 호출 - 10억 번 호출)했습니다.

행운을 빌어 fib(100)을 호출합니다.



이렇게 값비싼 함수를 단축하기 위해 할 수 있는 일이 있을까요?

메모 입력

Memoization (기억과 운율)은 이전 결과를 캐시에 저장하는 CS의 기술이므로 동일한 인수로 함수가 다시 호출될 때 캐시에서 값을 반환하고 함수를 다시 실행합니다. 피보나치와 같은 값비싼 함수에 유용합니다.

피보나치에서 메모이제이션을 어떻게 사용합니까?

다음을 사용할 수 있습니다.

const fib = (function() {
  const cache = {};

  function f(n) {
    let value;

    if (n in cache) {
      value = cache[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

        cache[n] = value;
    }

    return value;
  }

  return f;
})();

(출처: here . 위의 모든 크레딧은 작성자에게 있습니다).

위의 함수를 시도하고 fib(40), fib(50) 및 심지어 fib(100)을 실행하십시오. 당신은 그 차이를 느낄 것입니다.

메모이제이션은 어떻게 작동합니까?

JS 객체( const cache = {}; )에 값을 저장하므로 동일한 값이 다시 호출되면 함수를 실행하는 대신 cache에서 값을 가져옵니다.

우리가 fib(5)를 호출하고 싶다고 합시다. fib(5)가 처음 호출되면 캐시가 비어 있고 캐시에서 5를 찾을 수 없기 때문에(if (n in cache)는 거짓임) 피보나치 논리(value = f(n - 1) + f(n - 2);)를 실행한 다음 결과를 캐시(cache[n] = value;에 저장합니다. ) ). 이제 n = 5에 대한 캐시가 있습니다. {5: 5} (btw, fib(5)의 값은 5입니다).

다음에 우리가 fib(5)를 다시 호출하면 캐시에서 ( {5: 5} )을 찾습니다. fib(5)를 다시 실행하는 대신 단순히 캐시 조회에서 값을 반환합니다value = cache[n]; ... return value;. 피보나치는 재귀적이기 때문에 fib(5)를 호출하면 자동으로 최대 5의 값으로 캐시를 채웁니다. fib(5)를 호출하면 fib(4), fib(3) 등에 대한 캐시가 생성됩니다.

또 다른 예는 방금 fib(49)를 호출했고 다음에 fib(50)을 호출하려고 한다고 가정합니다. fib(50)을 호출하기 전에 캐시 내부에는 다음과 같은 캐시 값이 있습니다.

{
  0: 0,
  1: 1,
  2: 1,
  3: 2,
  ...
  48: 4807526976,
  49: 7778742049
}

이미 0에서 49까지의 값이 있습니다! 우리가 해야 할 일은 value = f(n - 1) + f(n - 2);를 호출하는 것입니다 - 일명 fib(49) + fib(48), 우리는 이미 캐시에 저장했습니다! 이것이 메모화 fib(50)이 메모화되지 않은 버전과 비교하여 거의 즉각적으로 결과를 반환하는 방법입니다.

달콤한! 눈에 보이는 모든 기능을 메모해 두겠습니다!

불행히도 모든 것을 메모할 수 있는 것은 아닙니다. 순수한 함수만 메모이제이션할 수 있습니다.

순수 함수가 되려면 다음을 수행해야 합니다.

반환 값 있음

자체 인수 이외의 인수에 의존하지 않음

범위 밖에서 값을 변경하지 않음

순수 함수는 이 문서의 범위를 벗어나지만 이 항목을 확인하십시오short article on pure function.

기타 참고 사항

메모이제이션은 굉장합니다. 하지만 남용하지 맙시다. 메모이제이션을 사용할 시기를 결정할 때 고려해야 할 몇 가지 사항:

일부 기능은 메모할 수 없습니다. 순수 함수만 있습니다.

메모이제이션의 오버헤드가 높습니다. 메모된 모든 함수에 대해 가능한 많은 인수를 저장하기 위해 캐시를 만들어야 한다는 점을 기억하십시오.

메모이제이션은 비용이 많이 드는 기능에 사용하는 것이 가장 좋습니다. Regex 호출 및 재귀는 내 마음에 들어온 그들 중 일부입니다.

좋네요. 그러나 실생활에서는 피보나치를 사용하지 않을 것입니다. 메모이제이션의 실제 사용 예가 있습니까?

예. VueJS은 메모이제이션을 활용합니다. cached(fn)는 메모이제이션 래퍼입니다.

function cached (fn) {
  var cache = Object.create(null);
  return (function cachedFn (str) {
    var hit = cache[str];
    return hit || (cache[str] = fn(str))
  })
}

그리고 그것은 여러 번 사용되고 있습니다:

const camelizeRE = /-(\w)/g
export const camelize = cached((str: string): string => {
  return str.replace(camelizeRE, (_, c) => c ? c.toUpperCase() : '')
})

export const capitalize = cached((str: string): string => {
  return str.charAt(0).toUpperCase() + str.slice(1)
})

const hyphenateRE = /\B([A-Z])/g
export const hyphenate = cached((str: string): string => {
  return str.replace(hyphenateRE, '-$1').toLowerCase()
})

이러한 기능을 찾을 수 있습니다here. (이 글을 쓰는 시점의 Vue 2.5.0. 향후 변경될 수 있지만 항상 이전 버전으로 돌아갈 수 있습니다.)

행복한 해킹!

자원

메모지에 대한 더 많은 정보:

Understanding JavaScript Memoization In 3 Minutes

JavaScript Function Memoization

Implementing Memoization in Javascript

순수 함수:

Understanding Javascript Mutation and Pure Functions