# In-Memory Caching for Repeated Computations

A simple in-memory, LRU cache that can be wrapped around any function to memoize it. The cache can be keyed on a hash of the input data (using 'digest') or on pointer equivalence.

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.

## Fibonnacci example

Consider this terrible way to compute the Fibonnacci sequence:

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

``````##        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:

``````##        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:

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

# memo v1.0.1 (Release date: 2018-01-01)

Changes:

• Addressed potential protection issues raised by rchk
• Update to use MARK_NOT_MUTABLE instead of NAMED.

Initial release.

# Reference manual

install.packages("memo")

1.0.1 by Peter Meilstrup, 3 years ago

Browse source code at https://github.com/cran/memo

Authors: Peter Meilstrup <[email protected]>

Documentation:   PDF Manual