데이터 과학 유망주의 매일 글쓰기 — 스물 한 번째 일요일
Memoisation
# Memoisation, # Decorator
오늘 한일:
이번 주 배웠던 내용 중 자세히 들여다보지 못했던 또하나의 주제는 Memoisation이라는 개념이었다. 딱히 한국어로 번역되지 않은 이 개념은, 반복적으로 이루어지는 계산을, 그 결과값을 한번 저장하여, 똑같은 값을 매번 계산하지 않고도 재활용할 수 있게 해주는 개념을 말한다. 인간으로 따지면 암기를 통해 구구단을 외우고, 그 구구단을 조금 더 복잡한 미분이나 적분을 계산할 때 쓰는 형태라고 할 수 있다. 한마디로 암기를 뜻하는 Memorization의 개념과 비슷하다고 볼 수 있다.
그렇다면 오늘은, Memoisation의 개념에 대해 알아보자.
Memoisation
일단 Memoisation이 많이 활용되는 대표적인 예는 재귀(Recursion) 알고리즘을 활용할 때다. 재귀는 조건이 맞을 때까지 프로그램을 반복적으로 실행하는 알고리즘을 말한다. 특히, 이 개념을 이해하기 위해 피보나치 수열(Fibonacci Series)이나 팩토리얼(Factorial)를 많이 예를 들어 활용한다. 이러한 문제들은 트리 형태로 재귀의 개념을 활용하는데, 이 때 같은 계산을 똑같이 반복할 수 있다는 문제가 생긴다. 예를 들어 아래 팩토리얼의 예제를 보자.
- 3! = 3*2*1 = 2
- 2! = 2*1 = 2
위의 예에서는 3의 팩토리얼(3!)과 2의 팩토리얼(2!)을 보여준다. 두 계산에서 2*1의 연산이 공통적으로 이루어지는 것을 볼 수 있다. 만약 재귀를 이용해 값이 1씩 커지는 로직으로 2!에서 3!로 넘어가는 계산을 한다고 하면, 3을 제외한 2부터 1까지의 값을 곱하는 연산을 반복하는 셈이된다. 차라리 2*1 = 2를 다른 곳에 저장하여 이 값을 불러와 여기에 3만 곱하면, 필요한 연산의 수는 1개 더 줄어들게 된다. 바로 이러한 개념을 활용한 것이 Memoisation이라고 볼 수 있다.
파이썬에서는 이 기법을 decorator라는 것을 이용해 적용할 수 있는데, 아래의 예제를 통해 조금 더 자세히 알아보자.
# 단순한 형태의 팩토리얼 함수def facto(num): # 1이면 그대로 리턴
if num == 1: return 1 # 아니면 팩토리얼 계산
else: return num * facto(num-1)# 함수 호출
print(facto(5))
위 함수는 팩토리얼을 계산하는 가장 단순한 형태의 예이다. 하지만, 여기서는 이전에 언급한대로 재귀를 통해 함수를 재호출하면서, 이전 범위의 계산을 매번 반복해야한다는 문제가 생긴다. 그만큼, 불필요한 계산이 증가할 수 있으므로, 이 문제를 decorator를 통해 아래와 같이 해결할 수있다.
# Decorator를 사용한 Memoisation 팩토리얼 프로그램 (참조: (2))
# 함수 "f"를 변수로 활용하는 Decorator 함수
def memoize_factorial(f):
# 반복되는 계산을 저장하기 위한 Dictionary
memory = {}
# 이 함수가 Dictionary에 접근하며, Decorator에 인자로 사용되는 "f"가 된다.
def inner(num):
# 만약 메모리에 입력한 값이 없으면 딕셔너리에 Key로 저장하고, 계산의 결과는 Dictionary에 저장
if num not in memory:
memory[num] = f(num)
return memory[num]
# 함수 재호출
return inner
# Memoisation 함수
@memoize_factorial
def facto(num):
# 1이면 그대로 리턴
if num == 1:
return 1
# 아니면 재호출하며 팩토리얼 계산
else:
return num * facto(num-1)
# 함수 초기 호출
print(facto(5))위 함수는 Decorator를 활용해 이미 진행한 팩토리얼 계산값을 Dictionary에 저장하는 방식이다. 이 프로그램이 작동되는 방식은 아래와 같다.
- 먼저, memoize_factorial이라는 함수를 정의하여 계산값을 memory라는 dictionary에 저장한다.
- 다음으로, decorator인 memoize_factorial을 계속해서 같이 활용하는 facto라는 함수가 주어진 값의 팩토리얼을 계산한다. facto함수는 decorator에 의해 memory dictionary에 접근할 수 있으며, decorator가 facto를 활용하는 방식은 다음과 같다.
- facto = memoize_factorial(facto)
3. 함수 facto가 최초로 호출될 때(facto(5)), decorator에 의해 중간 계산값을 저장한 이후 재귀 알고리즘이 동작한다. 새로운 계산이 이루어져야 할 때, 결과가 memory에 존재하는지 체크한다. 만약, 존재할 경우, 그 값을 불러와 사용하고, 그렇지 않으면 필요한 계산을 하고 그 결과를 memory에 저장하는 로직을 반복한다.
앞으로 할일:
오늘은 중복되는 계산을 저장하여, 쓸떼 없이 반복하지 않고도, 더 빨리 프로그램을 실행할 수 있는 Memoisation이라는 개념에 대해 다루어보았다. 사실 이 방법은 새로운 데이터를 생성하여 그것을 같이 활용하는 방식이기 때문에, 공간복잡도 면에서는 더 비효율적이다. 그렇지만, 불필요한 계산을 줄일 수 있다는 점에서 더 빠른 계산을 할 수 있으므로 시간복잡도 면에서 더 유리하다.
그렇다면, 현대의 프로그래밍 세계에서는 공간복잡도보다 시간복잡도의 문제가 훨씬 더 우선시 되는 것일까? 문득 그런 생각을 해 보게된다. 이번 주 동안 내내 배운 건 시간복잡도를 줄일 수 있는 개념들이었고, 공간복잡도를 줄일 수 있는 개념에 대해서는 상대적으로 많이 접하지 못했기 때문이다. 왠만한 컴퓨터 용량이 테라바이트의 단위 까지 가고있는 상황에서 어찌보면 메모리는 더 이상 과거만큼 문제가 되지 않는 것인지도 모르겠다. 이 것이 정말 사실인지에 대해서는 앞으로도 공부해 보아야겠다는 생각이 들었다.
새로운 것을 공부하면 그만큼 또 새로운 세계가 열린다. 그만큼 아는 것도 더 많아지지만, 더 모르는 것이 더 보인다. 하지만, 괜찮다. 내 안의 지적 세계가 팽창하고, 나의 지적 호기심이 더 왕성해 진다는 뜻이니까. 다음 주에 배우게될 것들에서 나는 또 어떤 새로운 세계를 맞이하고, 또 그 안에서 얼마나 더 넓은 세상을 발견할지 기대된다. 무한한 프로그래밍의 세계가 쉽지는 않지만, 더욱 더 흥미를 가지게 한다. 더 나은 프로그래머가 되기 위한 다음 주 마지막 스프린트도 더욱 힘차게 내딛을 수 있기를, 화이팅!
참조:
(1) https://www.python-course.eu/images/memoize2.png
(2) https://www.geeksforgeeks.org/memoization-using-decorators-in-python/
