메모화

Memoization
암기와 혼동하지 말 것.
"Tabling" 은 여기서 리다이렉트 됩니다.의회 절차는 표(의회 절차)를 참조한다.

컴퓨팅에서 메모화 또는 메모화는 주로 고가의 함수 호출 결과를 저장하고 동일한 입력이 다시 발생할 경우 캐시된 결과를 반환함으로써 컴퓨터 프로그램의 속도를 높이기 위해 사용되는 최적화 기법입니다.메모화는 단순한 상호 재귀적 하강 구문 [1]분석과 같은 다른 컨텍스트(및 속도 향상 이외의 목적)에서도 사용되고 있습니다.메모화는 캐싱과 관련되어 있지만 버퍼링이나 페이지 치환과 같은 캐싱 형태와 구별되는 이러한 최적화의 특정 경우를 가리킵니다.일부 논리 프로그래밍 언어에서는 메모화를 [2]태블링이라고도 합니다.

어원학

무료 사전인 Wiktionary에서 메모화를 찾아보세요.

"메모라이제이션"이라는 용어는 1968년 도널드[3] 미시에 의해 만들어졌으며 보통 미국 영어에서 "메모"로 잘린 라틴어 "메모르망"("기억될 것")에서 유래했으며, 따라서 "함수의 결과를 기억될 것으로 바꾼다"는 의미를 지니고 있다."메모라이제이션"은 "메모라이제이션"과 혼동될 수 있지만, "메모라이제이션"은 컴퓨팅에서 특별한 의미를 갖는다.

개요

메모화된 함수는 특정 입력 세트에 대응하는 결과를 "기억"한다.기억된 입력을 가진 후속 콜에서는 기억된 결과가 재계산되지 않고 반환됩니다.따라서 이들 파라미터를 사용하여 함수에 최초로 발신된 콜 이외의 모든 콜에서 특정 파라미터를 사용한 콜의 프라이머리 비용이 배제됩니다.기억된 연관성의 세트는 함수의 특성 및 용도에 따라 교체 알고리즘에 의해 제어되는 고정 크기 세트 또는 고정 세트일 수 있습니다.함수는 참조적으로 투과적인 경우에만 메모할 수 있습니다.즉, 함수를 호출하는 것이 함수 호출을 반환값으로 대체하는 것과 완전히 동일한 효과가 있는 경우에만 가능합니다.(단, 이 제한에 대한 특별한 예외가 있습니다.)메모화는 룩업 테이블과 관련되어 있지만, 구현에 이러한 테이블을 사용하는 경우가 많기 때문에 메모화는 미리가 아니라 필요에 따라 결과의 캐시를 즉시 투명하게 채웁니다.

메모화는 공간 비용 대신 함수의 시간 비용을 낮추는 방법입니다. 즉, 메모화된 함수는 컴퓨터 메모리 공간을 더 많이 사용하는 대신 속도에 맞게 최적화됩니다.알고리즘의 시간/공간 "비용"은 컴퓨팅에서 특정한 이름인 계산 복잡성이 있습니다.모든 함수는 시간(즉, 실행하는 데 시간이 걸린다)과 공간에서의 계산 복잡성이 있습니다.

공간-시간 트레이드오프가 발생하지만(즉, 사용된 공간은 속도를 얻는다), 이것은 강도 감소와 같은 시간-공간 트레이드오프를 수반하는 일부 다른 최적화와 다르다. 메모화는 컴파일 시간 최적화라기보다는 런타임 최적화라는 점에서 다르다.게다가 강도 저하는, 곱셈등의 고비용의 조작을, 추가등의 저비용의 조작으로 대체해, 절약의 결과는 머신 의존도가 높은(머신간에 휴대할 수 없는) 반면, 메모화는 머신에 의존하지 않는 크로스 플랫폼 전략입니다.

n의 계수를 계산하려면 다음 유사 코드 함수를 고려하십시오.

함수 요인(n은 음이 아닌 정수) n이 0이면 1을 반환합니다(0! = 1이라는 규칙에 따라). 그렇지 않으면 요인(n – 1)을 반환합니다. n은 n보다 작은 매개 변수 1을 사용하여 연속적으로 요인 호출을 끝냅니다.

모든 정수에 대해n ≥ 0, 함수의 최종 결과factorial로서 기동하는 경우는, 불변합니다.x = factorial(3)그 결과 x에는 항상 값 6이 할당됩니다.상기 비메모 실장에서는 관련된 재귀 알고리즘의 성질에 따라 n+1의 호출이 필요합니다.factorial결과에 도달하기 위해, 그리고 이러한 호출 각각은 함수가 계산된 값을 반환하는 데 걸리는 시간에 관련된 비용을 가집니다.기계에 따라 이 비용은 다음과 같은 합계가 될 수 있습니다.

  1. 기능하는 콜 스택프레임 셋업 비용
  2. n과 0을 비교하는 비용.
  3. n에서 1을 빼는 비용.
  4. 재귀 콜 스택프레임 셋업 비용(상기와 같이)
  5. 재귀 호출의 결과를 곱하는 비용factorialn까지.
  6. 콜 컨텍스트에서 사용할 수 있도록 반환 결과를 저장하는 비용.

비메모 실장에서는 에 대한 모든 최상위 콜이factorial에는 초기값 n에 비례하는 단계2 ~ 6의 누적비용이 포함됩니다.

메모화된 버전의factorial함수는 다음과 같습니다.

기능의 계승(n은 음이 아닌 정수)만약 n은 0다음 돌아오1[그 회의에 의해 0!=1] 다른 경우는 얼마인가?에lookup-table 다음 돌아오lookup-table-value-for-n 다른자 x)factorial(n– 1)번 n[재귀적으로 계승을 매개 변수와 함께 호출 1n보다 적은]가게 exinterest이자락lookup-table에 불과하다.hslot [나중에 n!의 결과를 기억한다]기능이 종료되면 x end를 반환한다.

이 예에서는,factorial처음에 5로 호출된 후 나중에 5보다 작거나 같은 값으로 호출된 경우 반환값도 메모됩니다.factorial값은 5, 4, 3, 2, 1, 및0 으로 재귀적으로 호출되어 각 값에 대한 반환값이 저장됩니다.그 후 7과 같이 5보다 큰 번호로 호출되면 재귀 호출은 2개(7과 6)만 이루어지며 5! 값은 이전 호출에서 저장됩니다.이와 같이 메모화를 사용하면 호출 빈도가 높아질수록 함수의 시간 효율이 향상되므로 결과적으로 전체적인 속도가 향상됩니다.

기타 고려사항

기능 프로그래밍

주요 기사:펑크 † 기능 프로그래밍

메모화는 컴파일러의 함수형 프로그래밍 언어에서 많이 사용됩니다.메모화에서는 콜 바이 네임 평가 전략을 사용하는 경우가 많습니다.인수값 계산에 따른 오버헤드를 피하기 위해 이들 언어의 컴파일러는 thunks라는 보조 함수를 많이 사용하여 인수값을 계산하고 반복 계산을 피하기 위해 이들 함수를 메모합니다.

자동 메모

메모화가 내부 및 컴퓨터 프로그래머에 의해 명시적으로 함수에 추가될 수 있는 동안 위의 메모화된 버전의 메모는 거의 같은 방법으로factorial참조 투과 기능이 구현되면 외부에서 [1]자동으로 메모될 수도 있습니다.Peter Norvig가 채택한 기술은 Common Lisp(논문이 자동 메모한 언어)뿐만 아니라 다양한 프로그래밍 언어에도 적용됩니다.자동 메모화의 적용은 용어 재작성과[4] 인공지능 [5]연구에서도 공식적으로 검토되었다.

함수가 1등급 객체(Lua, Python, Perl[6] 등)인 프로그래밍 언어에서는 특정 파라미터 세트에 대해 값이 계산되면 런타임에 함수를 계산된 값으로 대체하여 자동 메모화를 구현할 수 있습니다.이 함수 개체 값 치환을 수행하는 함수는 일반적으로 모든 참조 투과 함수를 래핑할 수 있습니다.다음 의사 코드(함수가 퍼스트클래스 값이라고 가정)에 대해 검토합니다. 

function memoized-call(F는 함수 객체 매개 변수) F에 연결된 배열 값이 없으면 값이라고 하는 연관 배열을 할당하고, F.values[arguments]가 비어 있으면 F.values[arguments]= F(arguments]; f.values[arguments]; f.values; f.values[arguments]를 반환합니다.

자동으로 메모된 버전을 호출하려면factorial콜이 아닌 위의 전략을 사용하여factorial직접, 코드가 호출됩니다.memoized-call(factorial(n))각 콜은 먼저 홀더 어레이가 결과에 할당되어 있는지 여부를 확인하고, 할당되어 있지 않은 경우 해당 어레이를 연결합니다.위치에 엔트리가 없는 경우values[arguments](어디서)arguments어소시에이션 어레이의 키로 사용됩니다).factorial지정된 인수를 사용합니다.마지막으로 키 위치에 있는 배열 내의 엔트리가 발신자에게 반환된다.

상기의 전략에서는, 메모하는 기능에 대해서, 콜 마다 명시적인 래핑을 실시할 필요가 있습니다.폐쇄가 가능한 언어에서는 메모화된 함수 오브젝트를 데코레이터 패턴으로 반환하는 펑터 팩토리를 통해 암묵적으로 메모화가 이루어집니다.의사 코드의 경우는, 다음과 같이 나타낼 수 있습니다.

function constructure-memoized-functor(F는 함수 객체 파라미터)는 memoized-version이라고 하는 함수 객체를 할당합니다.memoized-version(인수)이 self에 연결된 배열 값이 없는 경우 [self는 이 객체에 대한 참조입니다]라고 하는 관련 배열을 할당하고 값을 self에 부가합니다.self.values[self]가 비어 있으면 self.values[self] = F(인수); return self.values[self]; endlet; return memoized-version; end 함수

전화하는 대신factorial, 새로운 함수 오브젝트memfact는 다음과 같이 작성됩니다.

memfact = construct-interized-functor(필수)

위의 예에서는 함수가factorial에의 콜 전에 이미 정의되어 있다.construct-memoized-functor만들어졌다.이 시점부터,memfact(n)n의 계수가 필요할 때마다 호출됩니다.Lua와 같은 언어에서는 함수를 같은 이름의 새로운 함수로 대체할 수 있는 보다 정교한 기술이 존재합니다.이러한 기술은 다음을 가능하게 합니다.

요인 = construct-informized-functor(변수)

기본적으로 이러한 기술에는 다음과 같이 실제 함수에 대한 콜이 필요할 때(무제한 재귀를 피하기 위해) 에일리어스를 통해 작성된 함수에 원래 함수 객체를 부가하고 원래 함수에 콜을 메모로 전송하는 것이 포함됩니다.

function constructure-memoized-functor(F는 함수 객체 파라미터)는 memoized-version이라고 하는 함수 객체를 할당합니다.memoized-version(인수)이 self에 연결된 배열 값이 없는 경우 [self는 이 객체에 대한 참조입니다]라고 하는 관련 배열을 할당하고 값을 self에 부가합니다.에일리어스라는 새로운 함수 오브젝트를 할당하고 에일리어스를 셀프에 부가하며 [나중에 F를 간접적으로 호출하는 기능을 위해]셀프.별칭 = F, 종료되면 종료, self.values[self]가 비어 있으면 self.values[self] = self입니다.alias(인수); [F로의 직접 호출이 아님]종료하는 경우, self.values[인수]; endlet; return memoized-version; end 함수

(주: 위의 절차 중 일부는 구현 언어로 암묵적으로 관리될 수 있으며, 설명용으로 제공됩니다.)

파서스

하향식 파서가 애매한 입력에 대해 해석하려고 할 때 가능한 모든 해석 트리를 생성하기 위해 CFG의 모든 대체 방법을 시도하기 위해 (입력 길이에 대해) 기하급수적으로 많은 스텝이 필요할 수 있습니다.이를 위해서는 결국 기하급수적인 메모리 공간이 필요합니다.메모화는 1991년 피터 노비그에 의해 구문 분석 전략으로 탐구되었다. 피터 노비그는 Earley 알고리즘(1970년)의 동적 프로그래밍 및 상태 집합의 사용과 유사한 알고리즘과 Coke, Younger 및 Kasami의 CYK 알고리즘의 테이블이 단순한 역추적 재귀에 자동 메모화를 도입함으로써 생성될 수 있음을 입증했다.기하급수적인 시간 [1]복잡성 문제를 해결하기 위해 향기 파서를 사용합니다.Norvig의 접근법의 기본 개념은 파서를 입력에 적용했을 때 동일한 파서를 동일한 입력에 다시 적용했을 때 나중에 재사용할 수 있도록 결과를 메모리에 저장하는 것입니다.또한 Richard Frost는 메모화를 사용하여 파서 조합기의 기하급수적인 시간 복잡성을 줄였습니다.이것은 "순수적으로 기능적인 하향식" 구문 분석 [7]기술로 볼 수 있습니다.그는 기본 메모화된 파서 조합기를 구성 요소로 [8][9]사용하여 CFG의 실행 가능한 사양으로 복잡한 파서를 구성할 수 있음을 보여주었다.1995년 Johnson과 Dörre에 [10][11]의해 다시 파싱의 맥락에서 탐구되었다.2002년에 Ford는 packrat [12]parsing이라고 불리는 형태로 상당히 심도 있게 조사했습니다.

2007년에 Frost, Hafiz 및 Callaghan은[citation needed] 메모화를 사용하여 다중 계산을 억제하고 다항식 시간에 모호한 CFG를 수용하는 하향식 해석 알고리즘을 설명했습니다(좌재적 문법은 δ(n4), 비좌재적 문법은 δ(n3)).이들의 하향식 구문 분석 알고리즘은 또한 '콤팩트 표현' 및 '로컬 모호성 그룹화'에 의한 잠재적으로 지수적인 모호성 구문 분석 트리를 위한 다항식 공간을 필요로 한다.그 콤팩트한 표현은 토미타의 콤팩트한 상향식 [13]해석에 필적한다.메모화의 사용은 파서가 동일한 입력 위치에 반복적으로 적용될 때(다항식 시간 요건에 필수) 이전에 계산된 결과를 검색하는 데 한정될 뿐만 아니라 다음과 같은 추가 작업을 수행하는 데 특화되어 있습니다.

  • 메모화 프로세스(파서 실행 주변의 '래퍼'로 간주될 수 있음)는 입력 길이 및 현재 입력 위치에 대해 깊이 제한을 가함으로써 계속 증가하는 직접 좌회귀 해석을 수용합니다.
  • 또한 알고리즘의 메모 테이블 '검색' 절차는 저장된 결과의 계산 컨텍스트와 파서의 현재 컨텍스트를 비교하여 저장된 결과의 재사용 가능성을 결정합니다.이 컨텍스트 비교는 간접적(또는 숨겨진) 좌회귀에 대응하기 위한 열쇠입니다.
  • 메모테이블에서 정상적으로 룩업을 실행하면 완전한 결과 세트를 반환하는 대신 실제 결과의 참조만 반환되고 결과적으로 전체 계산 속도가 빨라집니다.
  • 메모 가능 갱신 중에 메모화 프로세스는 (잠재적으로 지수적으로) 애매한 결과를 그룹화하여 다항식 공간 요건을 확보한다.

또한 Frost, Hafiz 및 Callaghan은 PADL'08에서의[citation needed] 알고리즘 구현을 Haskell에서의 고차 함수 세트(파서 조합기라고 함)로 설명했으며, 이를 통해 CFG의 직접 실행 가능한 사양을 언어 프로세서로 구성할 수 있습니다.하향식 파싱과 함께 '모호한 CFG의 모든 형태'를 수용하는 다항식 알고리즘의 힘의 중요성은 자연어 처리 중 구문 및 의미 분석과 관련하여 매우 중요합니다.X-SAIGA 사이트에는 알고리즘과 구현에 대한 자세한 내용이 있습니다.

Norvig는 메모화를 통해 파서의 파워를 높였지만 증강 파서는 여전히 속도 최적화 이외의 용도로 메모화를 사용하는 얼리 알고리즘만큼 시간이 복잡했다.Johnson과 Dörre는[11] 이러한 비속도 관련 메모화의 또 다른 응용을 보여준다. 즉, 언어적 제약 해소를 그러한 제약 해소에 충분한 정보가 축적된 구문 분석의 한 지점까지 지연시키는 메모화 사용이다.반면 메모화의 속도 최적화 응용 프로그램에서 Ford는 메모화가 최악의 경우 역추적 [12]동작을 초래하는 언어라도 표현식 문법을 선형 시간 내에 해석할 수 있음을 입증했다.

다음 문법을 고려합니다.

S → (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의 하향식 왼쪽-오른쪽 해석에 미치는 영향에 대해 생각해 보겠습니다.

규칙 A는 xxxxb를 인식합니다(처음에는 xxxb를 내림차순하여 1개의 xx를 인식한 후 모든 x가 소비될 때까지 다시 X로 내림차순한 후 b를 인식함). 그런 다음 S로 돌아와 c를 인식하지 못합니다.S의 다음 절은 B로 내려갑니다.B는 다시 X로 내려와서 X에 대한 많은 재귀 호출을 통해 X를 인식하고, 그 다음 b를 통해 S로 돌아와 최종적으로 d를 인식합니다.

여기서 핵심 개념은 X로 다시 내려오는 구절의 고유한 개념이다.앞으로, 실패, 백업 및 다음 대체 방법을 찾는 프로세스는 해석에서는 백트랙킹이라고 불리며, 해석에서는 메모화의 기회를 제공하는 것이 주로 백트랙킹입니다.함수를 고려하다RuleAcceptsSomeInput(Rule, Position, Input)파라미터는 다음과 같습니다.

  • Rule고려 중인 규칙 이름입니다.
  • Position입력에서 현재 고려 중인 오프셋입니다.
  • Input검토 중인 입력입니다.

함수의 반환 값을 설정합니다.RuleAcceptsSomeInput받아들여지는 입력의 길이이다Rule이 규칙이 문자열 내의 오프셋에서 입력을 받아들이지 않을 경우, 또는0 을 지정합니다.이러한 메모화에 의한 백트래킹시나리오의 해석 프로세스는 다음과 같습니다.

규칙 A가 오프셋0의 X로 내림차순하면 길이5가 해당 위치와 규칙 X에 대해 메모됩니다.D에서 실패하면 B는 X로 다시 하강하는 것이 아니라 메모화 엔진 내의 규칙 X에 대해 위치 0을 조회하고 길이 5를 반환하므로 실제로 X로 하강해야 하며 이전과 마찬가지로 X로 하강한 것처럼 계속 진행됩니다.

위의 예에서는 xxxxxxxxxxxxxxxxxxxxxxxd와 같은 문자열을 사용할 수 있도록 X에 대한 설명이 하나 이상 발생할 수 있습니다.사실, b 앞에는 임의의 수의 x가 있을 수 있습니다.S에 대한 콜은 x의 횟수만큼 재귀적으로 X로 내려갈 필요가 있지만, B는 X로 내려갈 필요가 없습니다.이것은 반환값이기 때문입니다.RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)(이 경우는) 16이 됩니다.

구문 술어를 사용하는 파서는 술어 구문 분석의 결과도 메모할 수 있으므로 다음과 같은 구성을 줄일 수 있습니다.

S → (A)?A → /* 일부 규칙 */

A에 한 혈통으로

해석 중에 파서가 해석 트리를 작성하는 경우 특정 규칙에 대한 오프셋으로 일치하는 입력 길이를 메모해야 할 뿐만 아니라 해당 규칙에 의해 생성된 서브 트리를 입력 오프셋에 저장해야 합니다.파서에 의한 규칙에 대한 후속 호출이 실제로 하강하여 해당 트리를 재구축하지 않기 때문입니다.같은 이유로 규칙이 일치할 때 외부 코드(시멘틱액션 루틴이라고도 불립니다)에 대한 콜을 생성하는 메모화된 파서 알고리즘에서는 이러한 규칙이 예측 가능한 순서로 호출되도록 하기 위해 몇 가지 방식을 사용해야 합니다.

주어진 역추적 또는 구문 술어 대응 파서에 대해 모든 문법이 역추적 또는 술어 체크가 필요한 것은 아니기 때문에 입력 내의 모든 오프셋에 대해 각 규칙의 파싱 결과를 저장하는 오버헤드는 실제로 파서의 속도를 저하시킬 수 있습니다.이 효과는 파서가 [14]메모할 규칙을 명시적으로 선택함으로써 완화될 수 있습니다.

「 」를 참조해 주세요.

  • 대략적인 컴퓨팅 – 효율성 향상을 위한 기술 카테고리
  • 계산 복잡도 이론– 알고리즘 복잡도에 대한 상세 정보
  • 디렉터 문자열 - 표현식 중 자유 변수를 빠르게 찾을 수 있습니다.
  • Flyweight 패턴 – 객체 프로그래밍 설계 패턴으로 메모의 일종도 사용합니다.
  • Hashlife – 셀룰러 오토마타의 연산 속도를 높이기 위한 메모 기술
  • 느긋한 평가 – 메모화를 통한 개념 공유
  • 구체화된 뷰– 데이터베이스 쿼리의 유사한 캐싱
  • 부분 평가 – 프로그램 자동 최적화를 위한 관련 기술

레퍼런스

  1. ^ a b c Norvig, Peter (1991). "Techniques for Automatic Memoization with Applications to Context-Free Parsing". Computational Linguistics. 17 (1): 91–98.
  2. ^ Warren, David. "Tabling and Datalog Programming". Retrieved 29 May 2009.
  3. ^ Michie, Donald (1968). "'Memo' Functions and Machine Learning" (PDF). Nature. 218 (5136): 19–22. Bibcode:1968Natur.218...19M. doi:10.1038/218019a0. S2CID 4265138.
  4. ^ Hoffman, Berthold (1992). "Term Rewriting with Sharing and Memoïzation". In Kirchner, H.; Levi, G. (eds.). Algebraic and Logic Programming: Third International Conference, Proceedings, Volterra, Italy, 2–4 September 1992. Lecture Notes in Computer Science. Vol. 632. Berlin: Springer. pp. 128–142. doi:10.1007/BFb0013824. ISBN 978-3-540-55873-6.
  5. ^ Mayfield, James; et al. (1995). "Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems" (PDF). Proceedings of the Eleventh IEEE Conference on Artificial Intelligence for Applications (CAIA '95). pp. 87–93. doi:10.1109/CAIA.1995.378786. hdl:11603/12722. ISBN 0-8186-7070-3. S2CID 8963326.
  6. ^ "Bricolage: Memoization".
  7. ^ Frost, Richard; Szydlowski, Barbara (1996). "Memoizing Purely Functional Top-Down Backtracking Language Processors". Sci. Comput. Program. 27 (3): 263–288. doi:10.1016/0167-6423(96)00014-7.
  8. ^ Frost, Richard (1994). "Using Memoization to Achieve Polynomial Complexity of Purely Functional Executable Specifications of Non-Deterministic Top-Down Parsers". SIGPLAN Notices. 29 (4): 23–30. doi:10.1145/181761.181764. S2CID 10616505.
  9. ^ Frost, Richard (2003). "Monadic Memoization towards Correctness-Preserving Reduction of Search". Canadian Conference on AI 2003. Lecture Notes in Computer Science. Vol. 2671. pp. 66–80. doi:10.1007/3-540-44886-1_8. ISBN 978-3-540-40300-5.
  10. ^ Johnson, Mark (1995). "Memoization of Top-Down Parsing". Computational Linguistics. 21 (3): 405–417. arXiv:cmp-lg/9504016. Bibcode:1995cmp.lg....4016J.
  11. ^ a b Johnson, Mark & Dörre, Jochen (1995). "Memoization of Coroutined Constraints". Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics. Cambridge, Massachusetts. arXiv:cmp-lg/9504028.
  12. ^ a b Ford, Bryan (2002). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (Master’s thesis). Massachusetts Institute of Technology. hdl:1721.1/87310.
  13. ^ Tomita, Masaru (1985). Efficient Parsing for Natural Language. Boston: Kluwer. ISBN 0-89838-202-5.
  14. ^ Acar, Umut A.; et al. (2003). "Selective Memoization". Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 15–17 January 2003. ACM SIGPLAN Notices. Vol. 38. New Orleans, Louisiana. pp. 14–25. arXiv:1106.0447. doi:10.1145/640128.604133.

외부 링크

다양한 프로그래밍 언어의 메모화 예시