[Python] memoize

프로그래밍 분야에서 동적 계획법의 핵심이 되는 기술로 메모이제이션(memoization)이 있습니다. 이전에 계산한 값을 메모리에 저장함으로써, 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술입니다. 단적으로 말하면, 동일한 input에 대해 동일한 output이 나오는 함수지만 실행 비용이 비싼 경우 메모이제이션을 적용할 수 있습니다.

메모이제이션 구현하기

@memoize라는 간단한 메모이제이션 데코레이터를 구현해 보도록 합시다.

인자들을 stringify하여 cache 딕셔너리에 들어 있는지 검사하고, 들어 있지 않다면 함수의 실행 결과를 저장하여 나중에 똑같은 인자를 통해 해당 함수를 다시 호출했을 때 cache 딕셔너리에 저장된 값을 즉시 반환합니다. 따라서 memoize 데코레이터가 붙어 있는 expensive_fn 함수를 처음 실행했을 때는 3초가 걸렸지만, 똑같은 인자로 두 번째 실행했을 때는 매우 빠른 속도로 결과 값을 얻어낼 수 있습니다.

functools.lru_cache

Python 3.2 이상에서는 빌트인 모듈인 functools의 lru_cache 데코레이터를 사용해서 함수의 반환값들을 메모이제이션할 수 있습니다.