컴퓨터 프로그램의 속도를 높이기 위해 순수 함수 호출 결과를 저장해 두고 재사용하는 최적화 기법인 메모이제이션을 설명한다.
컴퓨팅에서 메모이제이션(memoization) 또는 **메모이제이션(memoisation)**은 주로 컴퓨터 프로그램의 속도를 높이기 위해 사용되는 최적화 기법이다. 이 기법은 비용이 큰 서브루틴 호출의 결과를, 특히 순수 함수의 결과를 저장해 두었다가 동일한 입력이 다시 등장할 경우 그 결과를 빠르게 반환함으로써 동작한다. 이는 일종의 캐싱이며, 보통 해시 테이블을 사용해 구현된다. 이는 전형적인 공간–시간 트레이드오프의 예로, 프로그램의 실행 시간을 줄이는 대신 메모리 사용량을 늘린다. 메모이제이션은 어떤 프로그래밍 언어로도 구현할 수 있지만, 일부 언어는 함수를 쉽게 메모이제이션할 수 있는 내장 지원을 제공하며, 또 다른 언어들은 특정 함수를 기본적으로 메모이제이션하기도 한다.
메모이제이션은 속도 향상 이외의 목적과 다른 문맥에서도 사용되어 왔는데, 예를 들어 간단한 상호 재귀 하향식 파싱에서 사용되었다.[1] 일부 논리 프로그래밍 언어의 문맥에서 메모이제이션은 테이블링(tabling)이라고도 불린다.[2]
메모이제이션(memoization)이라는 용어는 1968년에 도널드 미치(Donald Michie)에 의해 만들어졌으며[3][검증 필요], 라틴어 단어인 memorandum('기억되어야 할 것')에서 유래하였다. 이 단어는 미국 영어에서 보통 _memo_로 줄여 쓰이므로, ‘함수의 [결과를] 기억되어야 할 것으로 바꾼다’라는 의미를 내포한다. _메모이제이션(memoization)_은 암기(memorization)와 철자가 비슷하여 혼동될 수 있지만(어원상 동족어(cognate)이기 때문), 컴퓨팅에서 _메모이제이션_은 특별한 의미를 가진다.
메모이제이션된 함수는 특정 입력 집합에 대응하는 결과를 "기억"한다. 이후에 기억된 입력으로 다시 호출되면, 계산을 다시 수행하는 대신 이미 기억된 결과를 반환하여, 해당 매개변수로 함수를 호출하는 데 드는 주요 비용을 최초 호출 한 번을 제외하고 제거한다. 기억되는 연관 관계의 집합은 함수의 특성과 사용 방식에 따라, 교체 알고리즘으로 관리되는 고정 크기 집합일 수도 있고, 고정된 집합일 수도 있다. 어떤 함수는 참조 투명성을 가질 때에만 메모이제이션할 수 있다. 즉, 함수 호출을 해당 호출의 반환값으로 교체했을 때, 프로그램의 효과가 정확히 동일해야 한다는 뜻이다. (이 제한에 대한 특수한 예외들도 존재한다.) 메모이제이션은 구현에서 룩업 테이블을 자주 사용하므로 이와 관련이 있지만, 룩업 테이블이 보통 미리 채워지는 것과 달리, 메모이제이션은 필요한 시점에 결과 캐시를 투명하게 채워 나간다.
메모이제이션된 함수는 더 많은 컴퓨터 메모리 공간 사용과 맞바꾸어 _속도_에 최적화된다. 알고리즘의 시간/공간 "비용"은 컴퓨팅에서 특별한 이름을 가지는데, 바로 _계산 복잡도_이다. 모든 함수는 시간 복잡도(실행에 걸리는 시간)와 공간 복잡도를 가진다.
공간–시간 트레이드오프(즉, 더 많은 공간 사용은 더 높은 속도 획득과 대응됨)가 발생한다는 점에서, 메모이제이션은 강도 감소(strength reduction) 같은 다른 시간-공간 트레이드오프 최적화와 유사하지만, 메모이제이션은 컴파일 타임이 아닌 런타임 최적화라는 점에서 다르다. 또한 강도 감소는 곱셈 같은 비용이 큰 연산을 덧셈 같은 비용이 더 적은 연산으로 대체하므로, 절감 효과가 머신 의존적일 수 있고(머신 간 이식성이 떨어짐), 이에 비해 메모이제이션은 보다 머신에 덜 의존적인 크로스 플랫폼 전략이다.
다음은 정수 _n_의 팩토리얼을 계산하기 위한 의사 코드 함수이다.
textfunction factorial (n is a non-negative integer) if n is 0 then return 1 [by the convention that 0! = 1] else return factorial(n – 1) times n [recursively invoke factorial with the parameter 1 less than n] end if end function
모든 정수 _n_에 대해 n ≥ 0이면, factorial 함수의 최종 결과는 불변이다. 예를 들어 x = factorial(3)으로 호출하면, 결과적으로 _x_에는 항상 값 6이 할당된다. 위와 같은 비 메모이제이션 구현에서, 사용된 재귀 알고리즘의 특성상, 결과를 얻기 위해서는 factorial을 _n + 1_번 호출해야 하며, 각 호출은 값을 반환하는 데 걸리는 시간이라는 비용을 가진다. 머신에 따라 이 비용은 다음 항목들의 합이 될 수 있다.
factorial의 결과를 _n_과 곱하는 비용.비 메모이제이션 구현에서는, factorial에 대한 모든 최상위 호출이 초기 값 _n_에 비례하여 2~6단계의 누적 비용을 포함한다.
다음은 factorial 함수의 메모이제이션 버전이다.
textfunction factorial (n is a non-negative integer) if n is 0 then return 1 [by the convention that 0! = 1] else if n is in lookup-table then return lookup-table-value-for-n else let x = factorial(n – 1) times n [recursively invoke factorial with the parameter 1 less than n] store x in lookup-table in the n-th slot [remember the result of n! for later] return x end if end function
이 예에서, factorial이 처음에 5로 호출되고, 나중에 5보다 작거나 같은 값으로 다시 호출된다면, 그 반환값들 역시 메모이제이션되어 있을 것이다. factorial이 재귀적으로 5, 4, 3, 2, 1, 0의 값으로 호출되며, 이 각각의 반환값이 저장되기 때문이다. 이후 7처럼 5보다 큰 값으로 호출되면, 7과 6에 대해서 단 2번만 재귀 호출이 일어나고, 5!의 값은 이전 호출에서 이미 저장되어 있다. 이런 방식으로 메모이제이션은 함수가 호출될수록 점점 더 시간 효율적이 되도록 하여, 궁극적으로 전체적인 속도 향상을 가져온다.
메모이제이션의 극단적인 예로는 싱글턴 패턴, 그 중에서도 게터(getter)의 구현을 들 수 있다. 이 게터는 첫 호출 시에 객체를 생성하고, 그 인스턴스를 캐시에 저장한 후 이후 모든 호출 시에 동일한 객체를 반환하는 함수이다.
메모이제이션은 이름에 의한 호출 평가 전략을 자주 사용하는 함수형 프로그래밍 언어용 컴파일러에서 많이 사용된다. 이러한 언어들의 컴파일러는 인자 값을 계산하는 데 드는 오버헤드를 피하기 위해 썽크(thunk)라 불리는 보조 함수를 많이 사용하며, 인자 값의 반복 계산을 피하기 위해 이 썽크들을 메모이제이션한다.
메모이제이션은 위에서 본 메모이제이션 버전의 factorial 구현처럼, 프로그래머가 함수 내부에 명시적으로 추가할 수도 있지만, 참조 투명 함수는 외부에서 자동으로 메모이제이션할 수도 있다.[1] 피터 노빅(Peter Norvig)이 사용한 기법은, 그의 논문이 자동 메모이제이션을 시연한 언어인 커먼 리스프뿐만 아니라 다양한 다른 프로그래밍 언어에도 적용 가능하다. 자동 메모이제이션의 응용은 항(term) 재작성[4]과 인공지능 연구에서도 공식적으로 탐구되어 왔다.[5]
함수가 일급 객체인 언어들(예: Lua, Python, Perl[6])에서는, 특정 매개변수 집합에 대한 값이 한 번 계산되면, 런타임에 함수 자체를 그 계산된 값으로 교체함으로써 자동 메모이제이션을 구현할 수 있다. 이러한 값-대-함수-객체 교체를 수행하는 함수는, 일반적으로 어떤 참조 투명 함수든 감쌀 수 있다. 다음 의사 코드 예시를 보자(함수가 일급 값이라고 가정한다).
textfunction memoized-call (F is a function object parameter) if F has no attached array values then allocate an associative array called values; attach values to F; end if; if F.values[arguments] is empty then F.values[arguments] = F(arguments); end if; return F.values[arguments]; end function
위 전략을 사용해 자동 메모이제이션된 factorial을 호출하려면, factorial을 직접 호출하는 대신 memoized-call(factorial)(n)을 호출한다. 각 호출은 먼저 결과를 저장할 배열이 할당되어 있는지 확인하고, 없다면 해당 배열을 부착한다. values[arguments] 위치에 항목이 없다면(여기서 arguments는 연관 배열의 키로 사용됨), 주어진 인자를 이용해 실제로 factorial을 호출한다. 마지막으로, 이 키 위치의 배열 항목이 호출자에게 반환된다.
위 전략은 메모이제이션할 함수의 각 호출에 대해 명시적으로 래핑이 필요하다. 클로저를 허용하는 언어에서는, 데코레이터 패턴 형태의 펑터(functor) 팩토리를 통해, 감싸진 메모이제이션 함수 객체를 반환함으로써 메모이제이션을 암묵적으로 적용할 수 있다. 이를 의사 코드로 표현하면 다음과 같다.
textfunction construct-memoized-functor (F is a function object parameter) allocate a function object called memoized-version; let memoized-version(arguments) be if self has no attached array values then [self는 this 객체를 가리키는 참조] allocate an associative array called values; attach values to self; end if; if self.values[arguments] is empty then self.values[arguments] = F(arguments); end if; return self.values[arguments]; end let; return memoized-version; end function
factorial을 호출하는 대신, 새로운 함수 객체 memfact를 다음과 같이 생성한다.
textmemfact = construct-memoized-functor(factorial)
위 예제에서는 construct-memoized-functor를 호출하기 전에 factorial 함수가 이미 정의되어 있다고 가정한다. 이 시점 이후로는 _n_의 팩토리얼이 필요할 때마다 memfact(n)을 호출한다. Lua 같은 언어에서는, 동일한 이름을 가진 새 함수로 기존 함수를 교체할 수 있는 보다 정교한 기술이 존재하므로, 다음과 같은 코드도 가능하다.
textfactorial = construct-memoized-functor(factorial)
본질적으로 이와 같은 기법은, 생성된 펑터에 _원래 함수 객체_를 부착하고, 실제 함수 호출이 필요할 때(무한 재귀를 피하기 위해) 별칭(alias)을 통해 원래 메모이제이션될 함수를 간접적으로 호출하도록 만드는 것을 포함한다. 다음은 이를 보여 주는 예이다.
textfunction construct-memoized-functor (F is a function object parameter) allocate a function object called memoized-version; let memoized-version(arguments) be if self has no attached array values then [self는 이 객체를 가리키는 참조] allocate an associative array called values; attach values to self; allocate a new function object called alias; attach alias to self; [나중에 F를 간접적으로 호출하기 위해] self.alias = F; end if; if self.values[arguments] is empty then self.values[arguments] = self.alias(arguments); [F에 직접 호출이 아님] end if; return self.values[arguments]; end let; return memoized-version; end function
(참고: 위에 제시된 일부 단계는 구현 언어에 따라 암묵적으로 관리될 수 있으며, 설명을 위해 명시적으로 적어 두었다.)
상향식 파서가 모호한 문맥 자유 문법(CFG)에 대해 모호한 입력을 파싱하려고 할 때, 모든 가능한 파스 트리를 생성하기 위해 CFG의 모든 대안을 시도하는 데 (입력 길이에 대해) 지수 개의 단계가 필요할 수 있다. 이는 결국 지수적인 메모리 공간을 요구한다. 메모이제이션은 1991년 피터 노빅에 의해 파싱 전략으로 탐구되었는데, 그는 Earley 알고리즘(1970)의 동적 계획법 및 상태 집합(state-set) 사용과, Cocke, Younger, Kasami의 CYK 알고리즘의 테이블 사용과 유사한 알고리즘이, 단순한 백트래킹 재귀 하향식 파서에 자동 메모이제이션을 도입함으로써 생성될 수 있음을 보였다. 이를 통해 지수 시간 복잡도 문제를 해결할 수 있다.[1] 노빅 접근법의 기본 아이디어는, 파서를 입력에 적용할 때 그 결과를 메모 테이블(memotable)에 저장하고, 동일한 파서가 동일한 입력에 다시 적용될 경우 이 결과를 재사용한다는 것이다.
리처드 프로스트(Richard Frost)와 바르바라 쉐들로브스키(Barbara Szydlowski) 역시 파서 콤비네이터의 지수 시간 복잡도를 줄이기 위해 메모이제이션을 사용했으며, 그 결과를 "메모이제이션된 순수 함수형 상향식 백트래킹 언어 처리기"라고 설명했다.[7] 프로스트는 기본적인 메모이제이션 파서 콤비네이터들이 CFG의 실행 가능한 명세(executable specification)로서 복잡한 파서를 구성하는 빌딩 블록으로 사용될 수 있음을 보여 주었다.[8][9]
메모이제이션은 1995년에 마크 존슨(Mark Johnson)과 요헨 되레(Jochen Dörre)에 의해 파싱 문맥에서 다시 탐구되었다.[10][11] 2002년에는 브라이언 포드(Bryan Ford)가 팩랫 파싱(packrat parsing)이라 불리는 형태로 이를 상당히 깊이 있게 연구했다.[12]
2007년에 프로스트, 하피즈(Frost, Hafiz)와 캘러핸(Callaghan)은[출처 필요] 어떤 형태의 모호한 CFG라도 다항식 시간 안에 처리할 수 있도록, 중복 계산을 피하기 위해 메모이제이션을 사용하는 상향식 파싱 알고리즘을 기술했다(좌재귀 문법에 대해서는 Θ(n⁴), 비좌재귀 문법에 대해서는 Θ(n³)). 그들의 상향식 파싱 알고리즘은 잠재적으로 지수 개의 모호한 파스 트리를 ‘압축 표현(compact representation)’과 ‘국소적 모호성 그룹화(local ambiguities grouping)’를 통해 다항식 공간만 사용하도록 한다. 그들의 압축 표현은 토미타(Tomita)의 하향식 파싱에 대한 압축 표현과 비슷하다.[13] 이들의 메모이제이션 사용은, 파서를 동일한 입력 위치에 반복적으로 적용할 때 이전에 계산한 결과를 가져오는 것(다항식 시간 요구 사항에 필수적인 부분)에 그치지 않고, 다음과 같은 추가 작업을 수행하도록 특수화되어 있다.
프로스트, 하피즈와 캘러핸은 또한 PADL’08에서[출처 필요] 이 알고리즘의 구현을, 하스켈에서 고차 함수 집합(파서 콤비네이터라고 불림)으로 제시했다. 이는 CFG의 직접 실행 가능한 명세를 언어 처리기로 구성할 수 있게 한다. 이들의 다항식 알고리즘이 갖는 ‘어떤 형태의 모호한 CFG’라도 상향식 파싱으로 수용할 수 있는 능력은, 자연어 처리에서 구문 및 의미 분석을 수행할 때 매우 중요하다. 알고리즘과 구현 세부 사항에 대해서는 X-SAIGA 사이트를 참고할 수 있다.
노빅은 메모이제이션을 통해 파서의 _표현력_을 향상시켰지만, 확장된 파서의 시간 복잡도는 여전히 Earley 알고리즘과 같았다. 이는 메모이제이션을 속도 최적화 이외의 목적으로 사용하는 사례를 보여 준다. 존슨과 되레는[11] 메모이제이션을 사용하여, 구문 분석 과정에서 충분한 정보가 축적될 때까지 언어적 제약(linguistic constraint)의 해결을 지연시키는 또 다른 비-속도 관련 응용을 시연했다. 이에 비해 속도 최적화 측면에서, 포드는 메모이제이션을 사용하여 파싱 표현 문법이, 최악의 경우 백트래킹 동작을 보이는 언어에 대해서도 선형 시간에 파싱할 수 있도록 보장할 수 있음을 보여 주었다.[12]
다음 문법을 고려해 보자.
textS → (A c) | (B d) A → X (a|b) B → X b X → x [X]
(표기법 주: 위 예에서 생산식 S → (A c) | (B d)는 “_S_는 A 다음에 c가 오는 경우이거나, B 다음에 d가 오는 경우이다”로 읽는다. 생산식 X → x [X]는 “_X_는 x 다음에 선택적으로 _X_가 오는 경우이다”로 읽는다.)
이 문법은 다음 세 가지 변형 중 하나의 문자열을 생성한다. xac, xbc, xbd(여기에서 _x_는 하나 이상의 x를 의미한다). 이제 이 문법을 파싱 명세로 사용하여 문자열 _xxxxxbd_를 상향식, 좌에서 우로(top-down, left-right) 파싱할 때 어떤 일이 일어나는지 생각해 보자.
규칙 _A_는 _xxxxxb_를 인식한다(먼저 _X_로 내려가 x 하나를 인식하고, 모든 x가 소비될 때까지 반복해서 _X_로 내려간 다음, b를 인식한 후), 그리고 다시 _S_로 돌아와 _c_를 인식하는 데 실패한다. 그러면 _S_의 다음 분기에서 _B_로 내려가고, _B_는 다시 _X_로 내려가 여러 번 재귀적으로 _X_를 호출하면서 x들을 인식하고, 그 다음 b를 인식한 뒤, _S_로 돌아와 마침내 d를 인식한다.
여기서 핵심 개념은 “다시 _X_로 내려간다”라는 표현에 내포되어 있다. 앞을 내다보고(lookahead), 실패하고, 되돌아간 뒤, 다음 대안을 재시도하는 과정은 파싱에서 백트래킹이라고 알려져 있으며, 바로 이 백트래킹이 파싱에서 메모이제이션을 적용할 수 있는 주요 기회를 제공한다. 다음과 같은 함수 RuleAcceptsSomeInput(Rule, Position, Input)을 생각해 보자. 매개변수는 다음과 같다.
Rule은 고려 중인 규칙의 이름이다.Position은 입력에서 현재 고려 중인 오프셋이다.Input은 고려 중인 입력이다.함수 RuleAcceptsSomeInput의 반환값은, 규칙 Rule이 해당 문자열 오프셋에서 받아들이는 입력의 길이이며, 해당 규칙이 그 위치에서 입력을 전혀 받아들이지 못하는 경우 0을 반환한다고 하자. 이와 같은 메모이제이션이 있는 백트래킹 시나리오에서, 파싱 과정은 다음과 같다.
규칙 _A_가 오프셋 0에서 _X_로 내려갈 때, 규칙 _X_와 그 위치에 대해 길이 5를 메모이제이션한다. d에서 실패한 뒤, _B_는 _X_로 다시 내려가는 대신, 메모이제이션 엔진에 규칙 _X_와 위치 0을 질의하고 길이 5를 반환받는다. 이렇게 함으로써 다시 _X_로 실제로 내려갈 필요가 없어지고, 이전에 여러 번 _X_로 내려갔던 것처럼(as if) 계속 진행할 수 있다.
위 예에서 _X_로 한 번 또는 여러 번 내려갈 수 있으며, 예를 들어 문자열 xxxxxxxxxxxxxxxxbd 같은 경우가 가능하다. 실제로 b 전에 _x_가 임의의 개수만큼 올 수 있다. S에 대한 호출은 존재하는 x의 개수만큼 재귀적으로 X로 내려가야 하지만, B는 X로 전혀 내려갈 필요가 없다. 예를 들어 RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)의 반환값이 16이라면(이 특정 경우에서), 그 값을 그대로 사용하면 되기 때문이다.
구문 술어(syntactic predicate)를 사용하는 파서들도, 술어 파싱의 결과를 메모이제이션하여, 다음과 같은 구조를:
textS → (A)? A A → /* some rule */
_A_로 한 번만 내려가도록 줄일 수 있다.
파서가 파싱 중에 파스 트리(parse tree)를 구축하는 경우, 어떤 규칙이 특정 입력 오프셋에서 일치하는 입력의 _길이_뿐 아니라, 그 규칙이 해당 오프셋에서 생성한 서브트리 또한 메모이제이션해야 한다. 왜냐하면 이후 파서가 그 규칙을 다시 호출할 때 실제로 내려가서 해당 트리를 다시 구축하지 않기 때문이다. 같은 이유로, 규칙이 일치할 때 외부 코드(때로는 의미 동작 루틴(semantic action routine)이라고 불림)를 호출하는 메모이제이션 파서 알고리즘은, 그러한 규칙들이 예측 가능한 순서로 호출되도록 하는 체계를 사용해야 한다.
백트래킹이나 구문 술어를 사용할 수 있는 파서의 경우, 어떤 문법은 백트래킹이나 술어 검사를 필요로 하지 않을 수도 있기 때문에, 각 규칙의 파싱 결과를 입력의 모든 오프셋에 저장(그리고 파서가 암묵적으로 파스 트리를 구축하는 경우 트리까지 저장)하는 오버헤드는 오히려 파서를 느리게 만들 수도 있다. 이러한 효과는 파서가 메모이제이션할 규칙들을 명시적으로 선택함으로써 완화할 수 있다.[14]
{{cite book}}: CS1 maint: location missing publisher (link)
Wiktionary, 자유 사전에 있는 memoization 항목을 찾아보세요.