맨위로가기

메모이제이션

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

메모이제이션은 함수의 결과를 저장하여 동일한 입력에 대한 중복 계산을 피하는 최적화 기법이다. '메모리에 넣기'를 의미하는 라틴어에서 유래되었으며, 도널드 미치가 1968년 논문에서 처음 사용했다. 함수가 참조 투명성을 가질 때, 즉 부작용 없이 동일한 결과를 반환할 때 메모이제이션이 가능하다. 메모이제이션은 룩업 테이블을 사용하여 결과를 저장하며, 팩토리얼 계산이나 피보나치 수열과 같은 재귀 함수의 성능을 향상시키는 데 유용하게 사용된다. 또한 자동 메모이제이션, 파싱 전략 등 다양한 분야에 적용된다.

더 읽어볼만한 페이지

  • 컴퓨터 성능 - 전송 (컴퓨팅)
    전송은 컴퓨터 시스템에서 데이터 전송 속도를 나타내는 단위로, 초당 전송 횟수를 의미하며, MT/s는 SCSI 등에서, GT/s는 PCI Express에서 주로 사용된다.
  • 컴퓨터 성능 - 초당 명령 수
    초당 명령 수는 컴퓨터 성능 지표로서 초당 실행 명령어 수를 나타내는 단위이며, MIPS는 유사한 아키텍처 프로세서 성능 비교에 유용하나, 벤치마크 테스트와 함께 다른 아키텍처 간 비교에 활용된다.
  • 소프트웨어 최적화 - 성능 공학
    성능 공학은 시스템의 비즈니스 수익 증대를 위해 정해진 시간 안에 트랜잭션을 처리하도록 보장하고, 시스템 개발 실패 및 유지보수 비용 증가를 방지하며, 성능 관리와 모니터링을 통해 서비스 수준 계약을 준수하도록 한다.
  • 소프트웨어 최적화 - 프로파일링 (컴퓨터 프로그래밍)
    프로파일링(컴퓨터 프로그래밍)은 프로그램의 성능 분석 및 개선을 위한 기술로, 실행 시간 측정과 병목 현상 파악에 사용되며, 다양한 종류의 프로파일러가 존재한다.
메모이제이션

2. 어원 및 역사

메모이제이션은 글자 그대로 해석하면 ‘메모리에 넣기’라는 의미이며 ‘기억되어야 할 것’이라는 뜻의 라틴어 memorandum에서 파생되었다. 흔히 메모라이제이션(memorization)과 비슷하지만 구분되는 용어이다.

도널드 미치는 1968년 네이처에 실린 논문 〈Memo functions and machine learning〉에서 처음으로 메모이제이션이라는 용어를 사용했다.[3] 그는 라틴어 memorandum|메모란둠la(기억해두다)에서 이 용어를 만들었다.[15] ''memorization''(기억, 암기)은 동원어로 매우 유사하지만, 메모이제이션이라는 단어는 정보공학에서 특별한 의미를 갖는다.

3. 원리

도널드 미치가 1968년에 "메모이제이션"이라는 용어를 만들었으며,[3] 이는 라틴어 memorandumla ('기억해야 할 것')에서 유래했다. '함수의 [결과]를 기억해야 할 무언가로 바꾸는 것'을 의미한다.

메모이제이션된 함수는 특정 입력 값에 대한 결과를 "기억"한다. 이후 동일한 입력으로 함수가 호출되면 다시 계산하는 대신 기억된 결과를 반환한다. 이는 해당 매개변수를 사용하는 함수에 대한 첫 번째 호출을 제외한 모든 호출에서 주요 비용을 제거한다. 함수는 참조 투명성이 있는 경우에만 메모이제이션될 수 있다. 즉, 함수 호출이 부작용 없이 동일한 결과를 반환해야 한다. 메모이제이션은 룩업 테이블과 유사하지만, 필요에 따라 결과를 동적으로 채운다는 점에서 차이가 있다.

메모이제이션은 컴퓨터 메모리 공간을 더 사용하는 대신 실행 ''속도''를 최적화한다. 이는 시간-공간 트레이드오프를 발생시키지만, 메모이제이션은 런타임 최적화라는 점에서 강도 감소와 같은 다른 최적화와 다르다. 또한, 메모이제이션은 머신 독립적이고 크로스 플랫폼 전략이다.

''n''의 팩토리얼을 계산하는 함수를 예로 들어 설명하면 다음과 같다.
메모이제이션을 적용하지 않은 팩토리얼 함수 (의사 코드):```

function factorial (''n''은 음이 아닌 정수)

if ''n''이 0이면

return 1

else

return factorial(''n'' – 1) * ''n''

end if

end function

```

이 경우, 결과를 얻기 위해 `factorial` 함수를 ''n + 1''번 호출해야 하며, 각 호출에는 함수 호출 스택 프레임 설정, 값 비교, 뺄셈, 곱셈, 결과 저장 등의 비용이 발생한다.
메모이제이션을 적용한 팩토리얼 함수 (의사 코드):```

function factorial (''n''은 음이 아닌 정수)

if ''n''이 0이면

return 1

else if ''n''이 ''lookup-table''에 있으면

return ''lookup-table-value-for-n''

else

let x = factorial(''n'' – 1) * ''n''

store ''x'' in ''lookup-table'' in the ''n''th slot

return x

end if

end function

```

메모이제이션을 적용하면, 처음 5로 호출된 후 5 이하의 값으로 호출될 때 이미 저장된 값을 사용하므로 계산 시간을 단축할 수 있다. 예를 들어, 5!의 값이 저장된 후 7!을 계산하면 7과 6에 대한 재귀 호출만 수행하고, 5!의 값은 저장된 값을 사용한다. 이처럼 메모이제이션을 사용하면 함수를 더 자주 호출할수록 효율성이 높아져 전체적인 속도가 향상된다.

4. 예제

메모이제이션은 피보나치 수열이나 팩토리얼 계산과 같이 재귀 함수를 사용하는 예제에서 그 효과를 확인할 수 있다. 재귀 호출 시 중복 계산을 제거하여 실행 시간을 단축시키기 때문이다.

피보나치 수열과 팩토리얼의 경우처럼, '''메모이제이션된 함수'''는 특정 입력 집합에 해당하는 결과를 "기억"한다. 기억된 입력을 사용한 후속 호출은 다시 계산하지 않고 기억된 결과를 반환하므로, 해당 매개변수를 사용하는 함수에 대한 첫 번째 호출을 제외하고 모든 호출에서 매개변수 호출의 주요 비용을 제거한다.

메모이제이션된 함수는 컴퓨터 메모리 ''공간''을 더 많이 사용하는 대신 ''속도''를 위해 최적화된다. 알고리즘의 시간/공간 "비용"은 컴퓨팅에서 ''계산 복잡도''라고 불린다. 모든 함수는 ''시간''과 ''공간''에서 계산 복잡도를 가진다.

메모이제이션은 시간-공간 트레이드오프를 발생시키지만 (즉, 사용된 공간이 얻은 속도), 런타임 최적화라는 점에서 강도 감소와 같은 다른 시간-공간 트레이드오프 관련 최적화와는 다르다. 또한, 강도 감소는 머신 종속적일 수 있지만, 메모이제이션은 더 머신 독립적이고 크로스 플랫폼 전략이다.

메모이제이션은 파싱 과정에서도 활용될 수 있다. 하향식 파서가 모호한 입력을 모호한 문맥 자유 문법 (CFG)에 따라 파싱하려고 할 때, 가능한 모든 구문 분석 트리를 생성하기 위해 CFG의 모든 대안을 시도하는 데 입력 길이와 관련하여 지수적인 단계가 필요할 수 있다. 이는 결국 지수적인 메모리 공간을 필요로 한다.

1991년 Peter Norvig는 파싱 전략으로 메모이제이션을 연구하였으며[1], 동적 프로그래밍과 얼리 알고리즘 (1970)의 상태 집합, Cocke, Younger 및 Kasami의 CYK 알고리즘의 표와 유사한 알고리즘을 간단한 백트래킹 재귀 하강 파서에 자동 메모이제이션을 도입하여 지수적 시간 복잡성 문제를 해결하였다. Norvig의 접근 방식은 파서가 입력에 적용될 때 결과가 메모 테이블에 저장되어 동일한 파서가 동일한 입력에 다시 적용될 때 재사용된다는 것이다.

Richard Frost와 Barbara Szydlowski는 메모이제이션을 사용하여 파서 조합기의 지수적 시간 복잡성을 줄였으며, 그 결과를 메모이제이션하는 순수 함수적 하향식 백트래킹 언어 프로세서로 설명했다.[7] Frost는 기본 메모이제이션 파서 조합기를 CFG의 실행 가능한 사양으로 복잡한 파서를 구성하는 데 사용할 수 있음을 보여주었다.[8][9]

4. 1. 피보나치 수열

피보나치 수열을 구하는 가장 단순한 방법은 다음과 같다.

```text

fib(n) {

if n is 1 or 2, return 1;

return fib(n-1) + fib(n-2);

}

```

이때 fib 함수가 재귀적으로 실행되면서 같은 인자값에 대해서 계속해서 반복되므로, 전체 실행시간은 Ω(1.6n)이다. 그러나 fib(n)의 값을 계산하자마자 저장하면(memoize), 실행시간을 Θ(n)으로 줄일 수 있다.

```text

allocate array for memo, setting all entries to zero;

initialize memo[1] and memo[2] to 1;

fib(n) {

if memo[n] is zero:

memo[n] = fib(n-1) + fib(n-2);

return memo[n];

}

4. 2. 팩토리얼

''n''의 팩토리얼을 계산하기 위한 함수는 재귀 호출을 통해 구현할 수 있다. 단순 재귀 함수로 구현하면 다음과 같다.

```

function factorial (''n'') // n은 음이 아닌 정수

if ''n'' == 0 then

return 1

else

return factorial(n - 1) * ''n'' // 재귀 호출

end if

end function

```

이 경우, ''n'' ≥ 0인 모든 정수 ''n''에 대해, 함수 `factorial`의 결과는 불변이다. 예를 들어 `x = factorial(3)`으로 했을 때, ''x''의 값은 '''항상''' 6이다. 이러한 단순 재귀 구현은 결과를 얻는 데 ''n + 1''번의 재귀 호출이 필요하며, 이는 계산 시간 비용으로 이어진다.[1]

메모이제이션을 적용하면 중복 계산을 줄여 실행 시간을 단축할 수 있다. 다음은 메모이제이션을 적용한 `factorial` 함수의 예시이다.

```

function factorial (''n'') // n은 음이 아닌 정수

if ''n'' == 0 then

return 1

else if (테이블에 ''n''의 팩토리얼이 저장되어 있다) then

return (테이블에 저장된 ''n''의 팩토리얼 값)

else

x = factorial(n - 1) * ''n'' // 재귀 호출

''x''를 ''n''의 팩토리얼 값으로 테이블에 저장한다

return x

end if

end function

```

여기서 "테이블"은 광역 변수로, ''n''을 키로 하는 연관 배열과 같은 역할을 한다. 이 룩업 테이블을 통해 `factorial` 함수를 같은 인수로 반복 호출할 때 걸리는 시간을 줄일 수 있다.[1] 예를 들어 `factorial(5)`를 호출하면 5, 4, 3, 2, 1, 0에 대한 팩토리얼 값이 모두 테이블에 저장된다. 이후 `factorial(7)`을 호출하면 7과 6에 대한 계산만 수행하고, 5!의 값은 테이블에서 가져와 사용한다. 이처럼 메모이제이션을 통해 함수 호출 빈도가 늘어날수록 효율성이 증가하여 전체적인 속도 향상을 이끌어낸다.

5. 자동 메모이제이션

함수형 프로그래밍 언어에서 주로 사용되는 자동 메모이제이션은 프로그래머가 명시적으로 구현하는 대신, 자동으로 메모이제이션을 적용하는 기법이다.[1] 이는 함수가 일급 객체인 Lua, Python과 같은 프로그래밍 언어에서 구현 가능하다.[6]

자동 메모이제이션의 핵심은 함수 호출 시 결과를 저장하고, 동일한 호출 시 저장된 결과를 반환하도록 함수를 런타임에 대체하는 것이다. 이를 위해 클로저를 이용하여 메모이제이션 함수 객체를 생성한다.

자동 메모이제이션의 작동 방식은 다음과 같다.

# 함수 호출 시, 먼저 해당 함수에 연결된 연관 배열(캐시)이 있는지 확인한다.

# 연관 배열이 없으면 새로 생성하여 함수에 연결한다.

# 입력 인수를 키로 사용하여 연관 배열에서 값을 검색한다.

# 값이 존재하면(캐시 히트) 해당 값을 반환한다.

# 값이 없으면(캐시 미스) 원래 함수를 실행하여 결과를 계산하고, 결과를 연관 배열에 저장한 후 반환한다.

이러한 과정을 통해 반복적인 계산을 피하고 성능을 향상시킬 수 있다. 자동 메모이제이션은 항 재작성[4] 및 인공 지능[5] 연구에서도 응용된다.[16][17][18]

6. 파싱에서의 응용

피터 노빅은 1991년 구문 분석 전략에 메모이제이션을 적용하여, 백트래킹 방식의 재귀 하강 구문 분석에 자동 메모이제이션을 적용함으로써 얼리 알고리즘과 같은 알고리즘이 됨을 보였다[16]. 1995년에는 존슨(Johnson)과 되레(Dörre)도 구문 분석에서의 메모이제이션 응용을 제안했다[19][20]. 2002년, 포드(Ford)는 이를 팩래트 구문 분석에 응용하는 것을 상당히 자세히 논했다[21].

노빅은 구문 분석기를 메모이제이션으로 강화했지만, 시간 복잡도는 얼리 알고리즘과 같았다. 이는 속도 성능 최적화 외에 메모이제이션을 응용한 예이다. 존슨과 되레[20]도 시간 단축 외에 언어적 제약의 해결을 필요한 정보가 구문 분석에 의해 충분히 모아진 시점까지 지연시키는 것에 메모이제이션을 이용했다. 한편, 포드는 시간적 성능 최적화에 메모이제이션을 응용하여, 팩래트 구문 분석이 최악의 경우 백트래킹이 필요한 형식 언어에서도 선형 시간으로 구문 분석할 수 있음을 보였다[21].

형식 문법에서 생성 규칙 S → (A '''c''') | (B '''d''')의 의미는 "''S''는 ''A'' 다음에 하나의 '''c'''가 이어지거나, ''B'' 다음에 하나의 '''d'''가 이어지는 것 중 하나이다"이다. 생성 규칙 X → '''x''' [X]의 의미는 "''X''는 하나의 '''x''' 다음에 선택적인 ''X''가 이어진다"이다.

이 문법이 생성하는 문자열은 ''xac'', ''xbc'', ''xbd'' (단, ''x''는 1개 이상의 ''x''의 연속) 중 하나이다. 톱다운으로, 왼쪽에서 오른쪽으로 해석할 때, 문자열 ''xxxxxbd''의 해석에서 처리를 진행하다 실패하여 원래대로 돌아가 다른 선택지로 옮겨 처리를 재개하는 것을 백트래킹이라고 부른다.

함수 `RuleAcceptsSomeInput(Rule, Position, Input)`의 인수 의미는 다음과 같다.


  • `Rule`: 검토 중인 생성 규칙의 이름
  • `Position`: 현재 검토 중인 입력상의 오프셋 위치
  • `Input`: 검토 중인 입력


`RuleAcceptsSomeInput`의 반환값은 `Rule`이 수락한 입력의 길이이다. 생성 규칙이 지정된 오프셋 위치의 입력 문자를 수락하지 않은 경우에는 0을 반환한다. 백트래킹과 메모이제이션을 사용하는 경우, 구문 분석은 다음과 같아진다.

통사적 술어를 사용한 구문 분석기에서도, 술어의 구문 분석 결과를 메모이제이션할 수 있다.

구문 분석 시 구문 트리를 구축하는 경우, 메모이제이션에서는 매치된 입력의 길이뿐만 아니라, 그 위치와 생성 규칙에 의해 생성된 부분 트리도 기억해 둘 필요가 있다. 생성 규칙이 매치되었을 때 외부 코드를 호출하는 방식의 구문 분석기의 경우, 호출 순서가 원래 기대되는 순서가 되도록 주의하여 메모이제이션할 필요가 있다.

모든 문법에서 백트래킹이나 통사적 술어가 필요한 것은 아니므로, 개개의 생성 규칙에 대해 결과를 기억해 둠으로써 구문 분석의 성능이 저하될 가능성이 있다. 이는 메모이제이션할 생성 규칙을 명시적으로 선택함으로써 문제를 한정할 수 있다[22].

7. 적용 분야

메모이제이션은 다음과 같은 다양한 분야에서 활용될 수 있다.

참조

[1] 논문 Techniques for Automatic Memoization with Applications to Context-Free Parsing https://dl.acm.org/d[...]
[2] 논문 Memoing for logic programs 1992-03-01
[3] 논문 'Memo' Functions and Machine Learning https://www.cs.utexa[...]
[4] 서적 Algebraic and Logic Programming: Third International Conference, Proceedings, Volterra, Italy, 2–4 September 1992 Springer
[5] 서적 Proceedings of the Eleventh IEEE Conference on Artificial Intelligence for Applications (CAIA '95)
[6] 웹사이트 Bricolage: Memoization http://perl.plover.c[...]
[7] 논문 Memoizing Purely Functional Top-Down Backtracking Language Processors
[8] 논문 Using Memoization to Achieve Polynomial Complexity of Purely Functional Executable Specifications of Non-Deterministic Top-Down Parsers
[9] 서적 Canadian Conference on AI 2003
[10] 논문 Memoization of Top-Down Parsing
[11] 서적 Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics
[12] Master’s thesis Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking Massachusetts Institute of Technology
[13] 서적 Efficient Parsing for Natural Language Kluwer
[14] 서적 Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 15–17 January 2003
[15] 간행물 Memo Functions and Machine Learning Nature
[16] 간행물 Techniques for Automatic Memoization with Applications to Context-Free Parsing Computational Linguistics 1991-03
[17] 간행물 Term Rewriting with Sharing and Memoïzation Algebraic and Logic Programming: Third International Conference, Proceedings 1992-09-02
[18] 간행물 Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems TBD
[19] 간행물 Memoization of Top-Down Parsing Computational Linguistics 1995-09
[20] 간행물 Memoization of Coroutined Constraints Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics
[21] 학위논문 Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking Massachusetts Institute of Technology 2002-09
[22] 간행물 Selective Memoization Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages 2003-01-15


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com