Thememo package implements a simple in-memory cache forthe results of a function. If you have an expensive function that isbeing called repeatedly with the same inputs,memo canhelp.
fib<-function(n)if (n<=1)1elsefib(n-1)+fib(n-2)sapply(0:9, fib)## [1] 1 1 2 3 5 8 13 21 34 55This recursive implementation corresponds closely to the way thesequence is defined in math texts, but it has a performance problem. Theproblem is that as you ask for values further down the sequence, thecomputation becomes inordinately slow due to recursion. To demonstratethe issue, we can try counting every timefib iscalled:
count<-0fib<-function(n) { count<<- count+1if (n<=1)1elsefib(n-1)+fib(n-2)}counted_fib<-function(n) { count<<-0c(n=n,result=fib(n),calls=count)}t(sapply(0:16, counted_fib))## n result calls## [1,] 0 1 1## [2,] 1 1 1## [3,] 2 2 3## [4,] 3 3 5## [5,] 4 5 9## [6,] 5 8 15## [7,] 6 13 25## [8,] 7 21 41## [9,] 8 34 67## [10,] 9 55 109## [11,] 10 89 177## [12,] 11 144 287## [13,] 12 233 465## [14,] 13 377 753## [15,] 14 610 1219## [16,] 15 987 1973## [17,] 16 1597 3193The number of calls increases unreasonably. This is because, forinstance,fib(6) calls bothfib(5) andfib(4), butfib(5) also callsfib(4). The second call tofib(4) is wastedwork. And this pattern goes on – the two calls tofib(4)lead tofour calls tofib(2). Every time youincrementn by one, the number of calls roughly doubles.(Clearly, there are more efficient algorithms for computing theFibbonacci sequence, but this is a toy example, wherefibstands in for some expensive function that is being calledrepeatedly.)
One way to cut down on wasted effort would be to check whetherfib(n) has already been computed for a givenn. If it has,fib can just return that valueinstead of starting over. This is called “memoizing.” Thememo package canautomaticallycreate a memoized version of a given function, just by wrapping thefunction definition inmemo():
library(memo)count<-0fib<-memo(function(n) { count<<- count+1if (n<=1)1elsefib(n-1)+fib(n-2)})counted_fib(16)## n result calls ## 16 1597 17Now, computingfib(16) only takes 17 calls. And if wecall again, it remembers the previous answer and doesn’t make any newcalls:
counted_fib(16)## n result calls ## 16 1597 0Each successive value then only takes two calls:
t(sapply(17:30, counted_fib))## n result calls## [1,] 17 2584 1## [2,] 18 4181 2## [3,] 19 6765 2## [4,] 20 10946 2## [5,] 21 17711 2## [6,] 22 28657 2## [7,] 23 46368 2## [8,] 24 75025 2## [9,] 25 121393 2## [10,] 26 196418 2## [11,] 27 317811 2## [12,] 28 514229 2## [13,] 29 832040 2## [14,] 30 1346269 2The tradeoff for this speedup is the memory used to store previousresults. By defaultmemo will remember the 5000 mostrecently used results; to adjust that limit you can change thecache option:
fib<-memo(cache=lru_cache(5000),function () {...})The Fibonacci sequence being kind of a toy example, memoization has avariety of uses, such as: