Memoization

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다

https://ko.wikipedia.org/wiki/메모이제이션

여기서는 memoise 패키지에 구현된 함수를 사용한다

memoization 여부에 따른 성능 차이를 확인해보기 위해 쓸데없이 시간을 많이 잡아먹는 함수를 하나 만들어보기로 했다

iris 데이터를 지정한 횟수만큼 중복시켜서 rbind를 반복시키는 함수를 만들고 시간을 측정했다

df = c()
for (i in 1:n){
  df = rbind(df, new_df)  
}

이러한 형태로 data.frame을 합치게 될 경우, 매번 df의 마지막 row를 찾고 합치고 하는 과정을 반복해야 하기 때문에 df의 row 수가 많아질 수록 시간이 오래 걸리게 된다. 실제 코드는 아래와 같다

# install.packages('memoise')
library(memoise)

bind_iris = function(n){
  stopifnot(n%%1 == 0)
  
  new_iris = c()
  
  for(i in 1:n){
    new_iris = rbind(new_iris, iris)
  }
  
  return(new_iris)
}

system.time(bind_iris(500))

##    user  system elapsed 
##   13.65    0.08   13.95

memoise

memoise 함수를 사용하려면 memoise 함수에 원하는 함수를 인자로 넣고 새로운 함수를 생성하면 된다. 새로 만들어진 함수를 이용해서 값을 계산하면 memoise 함수는 인자에 새로운 값이 들어올 때만 새로 계산하게 된다

m_bind_iris = memoise(bind_iris)

따라서 첫 번째 계산때는 시간이 오래 걸리는 반면에 두 번째 계산에서는 시간이 대폭 단축되는 것을 확인할 수 있다

system.time(m_bind_iris(500))

##    user  system elapsed 
##   12.96    0.05   13.20

system.time(m_bind_iris(500))

##    user  system elapsed 
##       0       0       0

하지만 새로운 input 값이 들어오면 전체를 다시 계산하기 때문에 다시 원래의 속도가 나온다

system.time(m_bind_iris(300))

##    user  system elapsed 
##    3.65    0.03    3.70

advanced R 페이지에 memoization 관련하여 실린 예제가 있다. 피보나치 수열을 재귀함수를 통해 계산하도록 구성했는데, 이렇게 동일한 input값이 지속적으로 등장할 수 있는 환경에서는 memoization이 효과를 발휘할 수 있다

실제 내용은 아래 페이지에서 확인할 수 있다

http://adv-r.had.co.nz/Function-operators.html

fib = function(n) {
  if (n < 2) {
    return(1)
  }
  fib(n - 2) + fib(n - 1)
}

system.time(fib(30))

##    user  system elapsed 
##    5.29    0.00    5.39

이제 이 함수에 memoization을 적용한다

m_fib = memoise(function(n){
  if (n < 2) {
    return(1)
  }
  m_fib(n - 2) + m_fib(n - 1)
})

system.time(m_fib(100))

##    user  system elapsed 
##    0.02    0.00    0.02

system.time(m_fib(100))

##    user  system elapsed 
##       0       0       0

기본적으로 함수 내부의 재귀 호출에 걸리는 시간이 큰 폭으로 줄어들기 때문에 성능이 향상된다. 그리고 두 번째로 실행했을 때는 그 자체의 결과물이 캐싱되어 있기 때문에 더 빠르게 결과물을 확인할 수 있다

Caching

캐싱의 여부는 parameter의 이름이 아니라 값에 의해서 결정된다

a = 400
system.time(m_bind_iris(a))

##    user  system elapsed 
##    7.30    0.02    7.41

system.time(m_bind_iris(a))

##    user  system elapsed 
##       0       0       0

따라서 아래와 같은 경우에는 동일한 a 변수이지만 값이 변경되었기 때문에 새로 계산한다

a = 450
system.time(m_bind_iris(a))

##    user  system elapsed 
##    8.79    0.04    8.99

반면에 새로운 변수 b에 이전 a와 동일한 값을 넣게 되면 캐싱된 결과를 바로 가져오는 것을 확인할 수 있다

b = 400
system.time(m_bind_iris(b))

##    user  system elapsed 
##       0       0       0

memoise() 함수는 default parameter에 대한 정보를 가지고 있지 않다. 따라서 함수가 자동적으로 default parameter를 사용한 경우와 사용자가 default parameter와 동일한 값을 지정해 주는 상황을 서로 다른 input으로 간주한다

bind_iris2 = function(n, param = "aaa"){
  stopifnot(n%%1 == 0)
  
  new_iris = c()
  
  for(i in 1:n){
    new_iris = rbind(new_iris, iris)
  }
  
  return(new_iris)
}

m_bind_iris2 = memoise(bind_iris2)

이 함수에서는 param 인자의 기본값이 “aaa”이기 때문에 아래 두 함수는 결과적으로는 같은 함수다. 하지만 memoise 함수는 서로 다른 input으로 보기 때문에 새로 계산하는 것을 확인할 수 있다

system.time(m_bind_iris2(300))

##    user  system elapsed 
##    3.00    0.00    2.99

system.time(m_bind_iris2(300, param = "aaa"))

##    user  system elapsed 
##    3.31    0.00    3.36

함수 내부에 random한 값을 다루는 부분이 있을 경우에는 memoization의 사용을 주의해야 한다. input 값이 같으면 output이 같아지기 때문에 함수 안에 random한 값을 발생시켜야 하는 과정이 있다면 memoise를 적용한 이후에는 동일한 값이 출력된다. 따라서 이러한 경우에는 필요에 맞게 주의해서 사용할 필요가 있다

sapply(1:5, function(x) runif(1))

## [1] 0.59122861 0.06253046 0.46490960 0.81359091 0.31473203

m_runif = memoise(runif)
sapply(1:5, function(x) m_runif(1))

## [1] 0.6717948 0.6717948 0.6717948 0.6717948 0.6717948

forget

만약 memoise 해둔 함수를 제거해야 한다면 forget() 함수를 이용한다

forget(m_fib)

## [1] TRUE