The 'memo' package

memo

======

The memo package implements a simple in-memory cache for the results of repeated computations.

Fibonnacci example

Consider this terrible way to compute the Fibonnacci sequence:

fib <- function(n) if (n <= 1) 1 else fib(n-1) + fib(n-2)

This function is very slow to compute larger values. Each call to fib(n) with n > 1 generates two more calls to fib, leading to a runtime complexity of O(2^n). Let's count how many recursive calls to fib are involved in computing each fib(n):

count.calls <- function(f) {
  force(f)
  function(...) {
    count <<- count+1;
    f(...)
  }
}

with_count <- function(f) {
  force(f)
  function(x) {
    count <<- 0
    c(n=x, result=f(x), calls=count)
  }
}

fib <- count.calls(fib)

t(sapply(1:16, with_count(fib)))

The number of calls increases unreasonably. This is because, say, fib(6) calls both fib(5) and fib(4), but fib(5) also calls fib(4), so the second computation is wasted work, and this gets worse the higher n you have. We would be in better shape if later invocations of fib could access the values that were previously computed.

By wrapping fib using memo, fewer calls are made:

library(memo)
fib <- memo(fib)
t(sapply(1:16, with_count(fib)))

Here is only called to compute new values. Note that fib(16) only took two calls to compute, because fib(15) was previously computed. To compute fib(16) de novo takes 17 calls:

fib <- function(n) if (n <= 1) 1 else fib(n-1) + fib(n-2)
fib <- memo(count.calls(fib))
with_count(fib)(16)


Try the memo package in your browser

Any scripts or data that you put into this service are public.

memo documentation built on May 2, 2019, 7:01 a.m.