Elixir에서 메모이제이션 하기, Part 1
Posted on Monday, 12 Feb 2018
메모이제이션(memoization)은 컴퓨터 프로그래밍 기법 중 하나로, 매개 변수에 따른 함수의 값을 배열 등에 저장하여 다음에 똑같은 매개 변수로 함수를 호출할 경우 함수의 값을 계산할 필요 없이 그냥 배열에 저장된 값을 반환함으로써 프로그램의 실행 효율을 높이는 방식입니다.
거의 모든 알고리즘 관련 글이나 서적에서는 메모이제이션을 다룰 때 피보나치 함수를 예로 들기 때문에, 이 포스트에서도 많은 사람들에게 익숙한 피보나치 함수를 바탕으로 여러 가지 재미있는 것들을 해 볼까 합니다.
0단계: 무식한 피보나치 함수
메모이제이션을 알기 위해서는 일단 메모이제이션을 사용하지 않은 프로그램을 작성해 보아야겠죠. 아래 코드는 수학적인 정의에 충실히 따른 피보나치 함수입니다.
defmodule NaiveFibonacci do
@doc "피보나치 수열의 n번째 수를 반환합니다."
@spec fib(non_neg_integer()) :: non_neg_integer()
def fib(0), do: 0
def fib(1), do: 1
def fib(n) when is_integer(n) and n > 1, do: fib(n - 2) + fib(n - 1)
end이 포스트를 읽고 계신 여러분은 이렇게 구현된 피보나치 함수는 n이 커질 수록 함수의 반환 시간이 엄청나게 길어진다는 것을 알고 계실 겁니다. 피보나치 수열의 40번째 숫자를 구하는 데 걸리는 시간을 한 번 재 볼까요?
iex> :timer.tc(fn -> NaiveFibonacci.fib(40) end)
{3818048, 102334155} # 3.818초거의 4초에 가까운 시간이 걸리는 것을 볼 수 있습니다. 이제 여기에 메모이제이션 기법을 적용하여 써먹을 수 있는 상품을 만들어 봅시다.
1단계: 순수한(?) 메모이제이션
메모이제이션은 mutable한 배열을 사용하는 것이 핵심인 기법입니다. 하지만 Elixir에서는 대부분의 함수형 프로그래밍 언어처럼 모든 데이터가 immutable이고, 전역 변수나 포인터같은 것들을 사용할 수 없습니다. 그리고 가장 필요한 자료구조인 배열도 없지요. 그래서 배열 대신 map을 사용하여 메모이제이션이 적용된 피보나치 함수를 만들어 보겠습니다. 임의의 원소의 접근 시간이 O(1)인 배열에 비하면 성능이 다소 낮겠습니다만, 지금은 map 말고 다른 좋은 게 없는 것 같지요?
defmodule PureFibonacci do
@doc "피보나치 수열의 n번째 수를 반환합니다."
@spec fib(non_neg_integer()) :: non_neg_integer()
def fib(n) do
{result, _memo} = do_fib(n, %{})
result
end
@spec do_fib(non_neg_integer(), map()) :: {non_neg_integer(), map()}
defp do_fib(0, memo), do: {0, %{0 => 0}}
defp do_fib(1, memo), do: {1, %{0 => 0, 1 => 1}}
defp do_fib(n, memo) when is_integer(n) and n > 1 do
case memo[n] do
result when is_integer(result) ->
{result, memo}
nil ->
{n_minus_2, memo1} = do_fib(n - 2, memo)
{n_minus_1, memo2} = do_fib(n - 1, memo1)
result = n_minus_2 + n_minus_1
{n_minus_2 + n_minus_1, Map.put(memo2, n, result)}
end
end
end
우선 fib/1 함수는 private으로 정의된 do_fib/2 함수를 호출하고 그 결과를
정리해서 반환하는 일만 하고 있으며, 실제 피보나치 함수의 구현은 do_fib/2
함수로 옮겨졌습니다. 굳이 이렇게 바삭바삭한 겉면과 촉촉한 속살을 나눠놓은 것은
라이브러리 사용자들이 익숙한 방식으로 피보나치 함수를 사용할 수 있도록 하기
위함입니다.
do_fib/2 함수를 보면, 음이 아닌 정수 n뿐만 아니라 map도 하나 받도록 되어
있습니다. 그리고 fib/1에서 do_fib/2를 최초로 호출할 때 비어 있는 map을
매개변수로 전달하는데, 이 map이 바로 메모이제이션을 위해 함수와 함수 사이를
오가는 state라고 할 수 있습니다. do_fib/2의 구현을 자세히 살펴 보면,
-
먼저
memo에n에 대한 함숫값이 있는지 확인한다.<br>map[key]문법은map에key가 있으면 해당하는 값을 반환하고, 없으면nil을 반환한다. - 만약 함숫값이 저장되어 있다면 추가적인 계산을 수행하지 않고,<br> 그 값과 변경되지 않은 메모이제이션 state를 튜플로 감싸서 반환한다.
- 만약 함숫값이 저장되어 있지 않다면, 함숫값을 계산한 후<br> 그 결과 값과 갱신된 메모이제이션 state를 튜플로 감싸서 반환한다.
이러한 과정을 거쳐서 피보나치 함수의 값을 구하게 됩니다. 계산이 모두 끝난 후의 메모이제이션 state는 이런 모습을 하고 있습니다.
%{
0 => 0, 1 => 1, 2 => 1, 3 => 2,
4 => 3, 5 => 5, 6 => 8, ...
}전역 변수 또는 바깥 스코프에 정의된 mutable한 배열을 사용하는 대신에 map을 이리저리 주고 받으면서 메모이제이션을 수행한다는 차이점만 있을 뿐, C나 Java로 구현한 피보나치 함수와 크게 다른 점이 없습니다. 이제 이 피보나치 함수의 성능을 알아볼까요? 아까는 소심하게 40의 함숫값을 구했지만, 이번에는 통 크게 피보나치 수열의 5757번째 수도 구해 봅시다.
iex> :timer.tc(fn -> PureFibonacci.fib(40) end)
{53, 102334155}
iex> :timer.tc(fn -> PureFibonacci.fib(5757) end)
{9862,
619954643095296712872271097230028261374804255564716399851139687515798326876491
449163631648040157860086770492024484115268894667612537468727681045626281382970
# 12줄 생략...
728120458912634357483281381189510131747238399492497296620478877901560282885686
284787614592205171315930040591362}고작 9.862밀리초만에 결과가 나왔습니다! 이렇게 함수형 언어에서도 마음만 먹으면 메모이제이션의 효과를 누릴 수 있습니다.
2단계: Elixir 프로세스!
바로 앞에서 Elixir에서는 모든 데이터가 immutable하고, 전역 변수를 사용할 수 없다고 했었습니다. 하지만 Elixir는 Erlang VM (BEAM)위에서 동작하는 프로그래밍 언어로, Erlang 특유의 가벼운 프로세스와 메시지 전달 기법의 혜택을 그대로 누릴 수 있고, 이를 이용해서 여러가지 재미있고 대단한 것들을 만들 수 있지요. 이번에는 Erlang의 이러한 기능을 바탕으로 만들어진 Elixir의 모듈인 Agent와 GenServer를 차례대로 사용해 보고자 합니다.
Agent
Agent는 내부적으로 하나의 state를 가지고 있으며, get, update 등의 요청을
받으면 내부의 state에 접근해서 값을 반환하거나 state를 변경시키는 작업을 하는
프로세스입니다. Agent를 사용하면 전역 변수를 사용하는 것과 비슷한 효과를 얻을
수 있습니다.
defmodule AgentFibonacci do
@doc "피보나치 수열의 n번째 수를 반환합니다."
@spec fib(non_neg_integer()) :: non_neg_integer()
def fib(0), do: 0
def fib(1), do: 1
def fib(n) when is_integer(n) and n > 1 do
case get_value(n) do
result when is_integer(result) ->
result
nil ->
result = fib(n - 2) + fib(n - 1)
put_value(n, result)
result
end
end
@spec get_value(non_neg_integer()) :: non_neg_integer() | nil
defp get_value(n), do: Agent.get(MemoizationAgent, &(&1[n]))
@spec put_value(non_neg_integer(), non_neg_integer()) :: :ok
defp put_value(n, value) do
Agent.update(MemoizationAgent, &Map.put(&1, n, value))
end
end
프로세스와 프로세스 사이에 메시지를 주고 받는 것은 side effect입니다. 그리고
Agent에게 get 또는 update 등의 요청을 하는 것은 Agent에게 메시지를 보내는
것과 같습니다. 따라서 이제 fib/1 함수는 순수한 함수라고 볼 수 없습니다. 그
대신에, 함수가 메모이제이션 state를 가지고 있어야 할 책임을 벗어던져서 훨씬
깔끔해 보입니다.
이 피보나치 함수가 제대로 동작하기 위해서는 반드시 비어 있는 map을 초기 state로
갖는 Agent 프로세스가 실행되고 있어야 하며, MemoizationAgent라는 이름으로
등록이 되어 있어야 합니다. 이 프로세스는 독자적으로 실행되거나 Supervisor
프로세스의 관리 하에 놓일 수도 있습니다.
iex> {:ok, pid} = Agent.start_link(fn -> %{} end, name: MemoizationAgent)
iex> AgentFibonacci.fib(100)
354224848179261915075GenServer
GenServer (Generic Server)는 프로세스 간에 클라이언트-서버의 관계가 있는
애플리케이션을 개발할 때 서버 측 프로세스를 간편하게 만들 수 있도록 해주는
일종의 도구입니다. 이름에 “Generic”이 들어있는 것으로부터 알 수 있듯이,
GenServer로는 어떠한 클라이언트-서버 프로그램이든 만들 수 있습니다. 가장 가까운
예로, 바로 앞에서 사용한 Agent도 사실은 GenServer를 기반으로 만들어진 것입니다.
여기서 Agent.get이나 Agent.update 등의 함수를 호출하는 프로세스가 클라이언트
프로세스인 것이죠.
GenServer는 내부적으로 하나의 state를 가지고 있으며, 클라이언트로부터 동기적인
요청을 받고 그 처리 결과를 다시 클라이언트에게 돌려주거나(call), 비동기적인
요청을 처리할 수 있는(cast) 프로세스입니다. 클라이언트가 이 서버 프로세스에게
어떤 종류의 요청을 보낼 수 있고, 서버는 클라이언트로부터 받은 요청을 어떻게
처리해야 하는지는 모두 프로그래머에게 달려 있습니다. 이러한 높은 자유도 덕분에
Elixir와 Erlang에서는 어떤 클라이언트-서버 프로그램이든 쉽고 빠르게 개발할 수
있습니다. 이제 우리가 직접 만든 GenServer로 앞에서 사용한 Agent를 대체해 봅시다.
defmodule MemoizationServer do
@moduledoc "메모이제이션 상태를 관리하는 서버입니다."
use GenServer
#
# 클라이언트 측 함수
#
def start_link(opts) do
GenServer.start_link(__MODULE__, opts, name: __MODULE__) # --(1)
end
@doc """
메모이제이션 상태에 저장된 값을 가져옵니다.
값이 저장되어 있을 경우 `{:value, 값}`을 반환하고,
값이 저장되어 있지 않으면 `:no_value`를 반환합니다.
"""
@spec get_value(term()) :: {:value, term()} | :no_value
def get_value(arg) do
GenServer.call(__MODULE__, {:get_value, arg}) # --(2)
end
@doc """
메모이제이션 상태에 값을 저장합니다.
"""
@spec put_value(term(), term()) :: :ok
def put_value(arg, value) do
GenServer.call(__MODULE__, {:put_value, arg, value}) # --(3)
end
#
# GenServer 콜백
#
def init(_opts) do # --(1)
{:ok, %{}}
end
def handle_call({:get_value, arg}, _from, state) do # --(2)
case state[arg] do
{:value, _} = value -> {:reply, value, state}
nil -> {:reply, :no_value, state}
end
end
def handle_call({:put_value, arg, value}, _from, state) do # --(3)
new_state = Map.put(state, arg, {:value, value})
{:reply, :ok, new_state}
end
end
GenServer는 정말 간단합니다. 우선 MemoizationServer.start_link/1 함수를
호출하면 새로운 프로세스가 시작되고, 그 프로세스에서 init/1 콜백을 실행하고
서버의 초기 state를 설정합니다. 위의 코드를 보면 이 서버 프로세스는 시작한 직후
%{}을 state로 갖게 된다는 것을 알 수 있습니다. 나머지 두 함수, get_value/1과
put_value/2는 모두 GenServer.call/3 함수를 호출하고 있습니다. 이 함수는 서버
프로세스가 요청에 맞는 handle_call/3 콜백을 실행하도록 합니다.
메모이제이션 서버가 state에 함숫값을 저장할 때 값을 그대로 삽입하지 않고 굳이
{:value, 값}의 형태로 감싸서 삽입하는 것은 “state에 함숫값이 존재하지 않는
경우”와 “state에 nil이라는 값으로 존재하는 경우”를 구별하기 위해서입니다.
지금은 피보나치 함수에 메모이제이션을 적용하고 있어서 nil 값이 발생할 리가
없지만, 여러 함수에 사용할 수 있도록 하기 위해서는 이렇게 해 줘야겠죠.
MemoizationServer를 이용해 구현한 피보나치 함수는 Agent를 사용하여 만든 것과
거의 동일합니다. Agent의 함수를 사용한 부분을 MemoizationServer의 함수 호출로
바꾸고, case 내에서 값의 존재 여부를 확인하는 패턴만 다를 뿐입니다.
defmodule GenServerFibonacci do
@doc "피보나치 수열의 n번째 수를 반환합니다."
@spec fib(non_neg_integer()) :: non_neg_integer()
def fib(0), do: 0
def fib(1), do: 1
def fib(n) when is_integer(n) and n > 1 do
case MemoizationServer.get_value(n) do
{:value, result} ->
result
:no_value ->
result = fib(n - 2) + fib(n - 1)
MemoizationServer.put_value(n, result)
result
end
end
end
지금까지 Elixir에서 사용할 수 있는 여러 가지 메모이제이션 기법을 단계적으로
적용해가며 피보나치 함수를 발전시켜 왔습니다. 사실 여기까지 해도 이미 충분히
훌륭한 프로그램이 되었다고 볼 수 있겠는데요, 저는 욕심이 있어서 여기서 만든
MemoizationServer의 기능을 좀 더 확장시키고자 합니다. 하지만 이제 슬슬
포스트의 길이가 너무 길어지는 것 같으니 여기에 대한 내용은
다음 포스트에서 이어서
진행할게요~
스포일러:
다음 포스트에서 다룰 내용은 사실 메모이제이션과는 큰 관련이 없을 수도 있습니다. (…)