使用记忆化优化你的 R 代码
本文翻译自《Optimize your R Code using Memoization》（有删减）
https://www.inwt-statistics.com/read-blog/optimize-your-r-code-using-memoization.html
本文介绍如何应用名为“记忆化（Memoization）”的编程技术来加速你的 R 代码并解决性能瓶颈。维基百科：
在计算中，... 记忆化是一种优化技术，主要用于通过存储代价高昂函数调用的结果，并在再次出现相同输入时返回缓存结果来加速计算机程序。
如果你想提升速度，并且只依赖该技术，你可以在 CRAN 上找到两个包 R.cache 和 memoise。下面我将提供不同版本的实现，一来说明记忆化不是魔法而是一种相当简单的技术；二来显示 R 可以远远快于 C++！
R 中的性能优化
如果我阅读到有关高性能计算的文字，在原始计算速度方面，R 似乎声名狼藉。感谢有了 Rcpp，可以尽可能简单地将 C++ 集成到你的 R 项目中。虽然不一定容易：你仍然需要学习一些 C++。我经常觉得围绕这个主题的讨论忽略了实现的成本其实包括方方面面，因此太快提出建议意味着你必须使用不同的语言。但是，我们经常可以使用普通的旧式 R 技术并提高运行时性能，同时易于实现。怎么做？通常通过重新定义问题（作弊），将计算分解成碎片（分而治之）或找到瓶颈并优化（最大限度地利用语言）！
当然，任何这些步骤都可能迫使我们最终使用 C++ 或其他东西。但是我们可以将这一点推向更远的地方，并用一些脑力和优化策略工具箱来弥补它。在优化方面有很多东西需要学习。记忆化可以成为你的一种技巧，可以神奇地使 R 代码运行得更快。这是通过避免不必要的计算来完成的，或者说不必要地计算两次。
R 何时变慢
要开始这个练习，让我们看看 R 何时变慢，以及随后我们如何改进它。我从 Rcpp 文档中获取了这个示例，该文档显然是为了回应 StackOverflow 上的一个问题而创建的，该问题询问为什么 R 的递归函数调用如此之慢。
挑战在于使用计算效率最低的定义之一来计算斐波那契数。当然，具体的例子并非如此。还有其他更有效的方法来计算斐波那契序列。但递归定义会让你的 CPU 风扇狂转，这就是它有趣的原因。在下文中，你可以找到算法的“菜鸟”实现。这两种语言看起来或多或少都是一样的。但是，正如你所看到的，耗时已经不同了。我们可以稍微改变 N，R 中的实现将快速达到它的极限。
N <- 35 ## the position in the fibonacci sequence to compute
fibRcpp <- Rcpp::cppFunction(
'
int fibonacci(const int x)
{
if (x == 0) return(0);
if (x == 1) return(1);
return (fibonacci(x - 1)) + fibonacci(x - 2);
}
')
fibR <- function(x)
{
## Non-optimised R
if (x == 0) return(0)
if (x == 1) return(1)
Recall(x - 1) + Recall(x - 2)
}
rbenchmark::benchmark(
baseR = fibR(N),
Rcpp = fibRcpp(N),
columns = c("test", "replications", "elapsed", "user.self"),
order = "elapsed",
replications = 1)
## test replications elapsed user.self
## 2 Rcpp 1 0.07 0.06
## 1 baseR 1 29.27 27.69R 何时变（更）快
现在让我们看看我们如何定义一个函数，仍然计算相同的数字，避免所有不必要的计算。请注意，在递归定义中，要计算第 N 个数，我们必须计算第 N-1 和 N-2 个数。这将导致计算次数的爆炸。同时，如果我们想要计算 N = 35 的斐波那契数，并且我们已经得到 N = 34 和 N = 33 的结果，我们不必重新计算它们，我们只是使用我们已经知道的东西。让我们看看如何做到这一点：
fibRMemoise <- local(
{
memory <- list()
function(x)
{
valueName <- as.character(x)
if (!is.null(memory[[valueName]])) return(memory[[valueName]])
if (x == 0) return(0)
if (x == 1) return(1)
res <- Recall(x - 1) + Recall(x - 2)
memory[[valueName]] <<- res # store results
res
}
})我们所做的：
- 检查是否已经知道了结果
- 如果已经知道，返回结果并在此停止（不做任何计算）
- 如果不知道，进行第 2 步
- 计算必要的结果（例如斐波那契数）
- 在我们退出函数之前记住结果
- 然后，返回结果
所以这个想法非常简单。另一个复杂性是，我们需要一个闭包。在这里，我们使用 local。local 将创建一个新的作用域（环境）并运行该环境中的代码。因此，该函数可以访问该环境，即它可以访问内存，但是我们在全局环境中看不到内存：它是函数定义的本地内容。此外，我们需要超级赋值运算符（<<-），以便我们可以对内存进行赋值。好吧，让我们看看除了抽象之外我们获得了什么，以及代码：
rbenchmark::benchmark(
baseR = fibR(N),
Rcpp = fibRcpp(N),
memoization = fibRMemoise(N),
columns = c("test", "replications", "elapsed", "user.self"),
order = "elapsed",
replications = 1)
## test replications elapsed user.self
## 3 memoization 1 0.00 0.00
## 2 Rcpp 1 0.04 0.04
## 1 baseR 1 32.03 31.67看到没？R 竟然比 C++ 快！如果你有时间等待 C++ 实现，我们可以看到我们可以走多远，并且 C++ 中的实现快速达到极限。
N <- 50 # not very far, but with memoization Int64 is the limit.
rbenchmark::benchmark(
# baseR = fibR(N), # not good anymore!
Rcpp = fibRcpp(N),
memoization = fibRMemoise(N),
columns = c("test&quo