title: "The 'memo' package" author: "Peter Meilstrup" date: "2016-06-05" output: rmarkdown::html_vignette vignette: > %\VignetteIndexEntry{Vignette Title} %\VignetteEngine{knitr::rmarkdown} \usepackage[utf8]{inputenc}

======

The `memo`

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

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)))
```

```
## n result calls
## [1,] 1 1 1
## [2,] 2 2 3
## [3,] 3 3 5
## [4,] 4 5 9
## [5,] 5 8 15
## [6,] 6 13 25
## [7,] 7 21 41
## [8,] 8 34 67
## [9,] 9 55 109
## [10,] 10 89 177
## [11,] 11 144 287
## [12,] 12 233 465
## [13,] 13 377 753
## [14,] 14 610 1219
## [15,] 15 987 1973
## [16,] 16 1597 3193
```

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)))
```

```
## n result calls
## [1,] 1 1 1
## [2,] 2 2 3
## [3,] 3 3 2
## [4,] 4 5 2
## [5,] 5 8 2
## [6,] 6 13 2
## [7,] 7 21 2
## [8,] 8 34 2
## [9,] 9 55 2
## [10,] 10 89 2
## [11,] 11 144 2
## [12,] 12 233 2
## [13,] 13 377 2
## [14,] 14 610 2
## [15,] 15 987 2
## [16,] 16 1597 2
```

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)
```

```
## n result calls
## 16 1597 17
```

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

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.