用memoization优化递归算法[JS/PHP实现]

目录

递归函数,通过把一个大而复杂问题简化为许多但规模较小的问题,以同一个相似模式来计算,降低了解题的难度;通过调用自身函数,极大地减少了函数代码量的优点而为开发者喜爱。但因其不断调用自身函数开辟新栈,且大量传入同样参数,得到同样的结果,重复同一行为,也会浪费大量的内存。

  • 使用记忆化优化你的 R 代码
    • R 中的性能优化
    • R 何时变慢
    • R 何时变快
    • R 中的记忆化
    • 何时使用记忆化

以经典问题,斐波那契数列为例:

使用记忆化优化你的 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++!

斐波那契数列指的是这样一个数列: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
89, 144,
233,377,610,987,1597,2584,4181,6765,10946,17711,求其第N项的值。

R 中的性能优化

如果我阅读到有关高性能计算的文字,在原始计算速度方面,R
似乎声名狼藉。感谢有了 Rcpp,可以尽可能简单地将 C++ 集成到你的 R
项目中。虽然不一定容易:你仍然需要学习一些
C++。我经常觉得围绕这个主题的讨论忽略了实现的成本其实包括方方面面,因此太快提出建议意味着你必须使用不同的语言。但是,我们经常可以使用普通的旧式
R
技术并提高运行时性能,同时易于实现。怎么做?通常通过重新定义问题,将计算分解成碎片或找到瓶颈并优化(最大限度地利用语言)!

当然,任何这些步骤都可能迫使我们最终使用 C++
或其他东西。但是我们可以将这一点推向更远的地方,并用一些脑力和优化策略工具箱来弥补它。在优化方面有很多东西需要学习。记忆化可以成为你的一种技巧,可以神奇地使
R
代码运行得更快。这是通过避免不必要的计算来完成的,或者说不必要地计算两次。

对数列进行分析,我们发现,从自三项开始,第N项的值就等于其前两项之和,即第N-1和第N-2项的和。所以我们可以这样写func(n)=func(n-1)+func(n-2)

R 何时变慢

要开始这个练习,让我们看看 R 何时变慢,以及随后我们如何改进它。我从 Rcpp
文档中获取了这个示例,该文档显然是为了回应 StackOverflow
上的一个问题而创建的,该问题询问为什么 R 的递归函数调用如此之慢。

挑战在于使用计算效率最低的定义之一来计算斐波那契数。当然,具体的例子并非如此。还有其他更有效的方法来计算斐波那契序列。但递归定义会让你的
CPU
风扇狂转,这就是它有趣的原因。在下文中,你可以找到算法的“菜鸟”实现。这两种语言看起来或多或少都是一样的。但是,正如你所看到的,耗时已经不同了。我们可以稍微改变
N,R 中的实现将快速达到它的极限。

N <- 35 ## the position in the fibonacci sequence to computefibRcpp <- Rcpp::cppFunction(    '    int fibonacci(const int x)    {        if  return;        if  return;        return (fibonacci + fibonacci;    }    ')fibR <- function{    ## Non-optimised R    if  return    if  return    Recall + Recall}rbenchmark::benchmark(    baseR = fibR,    Rcpp = fibRcpp,    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.69

代码如下:

R 何时变快

现在让我们看看我们如何定义一个函数,仍然计算相同的数字,避免所有不必要的计算。请注意,在递归定义中,要计算第
N 个数,我们必须计算第 N-1 和 N-2
个数。这将导致计算次数的爆炸。同时,如果我们想要计算 N = 35
的斐波那契数,并且我们已经得到 N = 34 和 N = 33
的结果,我们不必重新计算它们,我们只是使用我们已经知道的东西。让我们看看如何做到这一点:

fibRMemoise <- local(    {        memory <- list()        function        {            valueName <- as.character            if (!is.null(memory[[valueName]])) return(memory[[valueName]])            if  return            if  return            res <- Recall + Recall            memory[[valueName]] <<- res # store results            res        }    })

我们所做的:

  1. 检查是否已经知道了结果
    • 如果已经知道,返回结果并在此停止
    • 如果不知道,进行第 2 步
  2. 计算必要的结果
    • 在我们退出函数之前记住结果
    • 然后,返回结果

所以这个想法非常简单。另一个复杂性是,我们需要一个闭包。在这里,我们使用
locallocal
将创建一个新的作用域并运行该环境中的代码。因此,该函数可以访问该环境,即它可以访问内存,但是我们在全局环境中看不到内存:它是函数定义的本地内容。此外,我们需要超级赋值运算符(<<-),以便我们可以对内存进行赋值。好吧,让我们看看除了抽象之外我们获得了什么,以及代码:

rbenchmark::benchmark(    baseR = fibR,    Rcpp = fibRcpp,    memoization = fibRMemoise,    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, # not good anymore!    Rcpp = fibRcpp,    memoization = fibRMemoise,    columns = c("test", "replications", "elapsed", "user.self"),    order = "elapsed",    replications = 1)##          test replications elapsed user.self## 2 memoization            1    0.00      0.00## 1        Rcpp            1   87.67     87.24

很棒,非常高效的黑科技。它还说明了为什么语言之间的性能比较就像比较苹果。是的,无论如何,R
就是快:)

1 function fibonacci(n){
2     if((n==0)||(n==1)){
3         return n;
4     }else{
5       return fibonacci(n-1)+fibonacci(n-2);//调用自身函数实现递归
6     }
7 }

R 中的记忆化

上述定义存在一些问题:它不是很通用。我们对记忆化的定义仍然与斐波那契数的定义有关。但是,我们可以定义一个更高阶的函数,它将记忆化与算法分开:

memoise <- function{    memory <- list()    function    {        valueName <- as.character        if (!is.null(memory[[valueName]])) return(memory[[valueName]])        res <- fun        memory[[valueName]] <<- res        res    }}

这是该技术的完美定义,并且不是很长或很复杂。原则上,你会在 R.cache
memoise
中找到同样的东西。显然,这两个包添加了一些功能,例如,你想如何以及在何处存储内存,也许是在磁盘上。上述函数只允许一个参数,这个问题也在上述两个包中得到解决。上述两个包还添加了其他一些有用的东西。

分析代码我们发现,计算第N项的值总要计算第0项或第1项等较小的项的值,且会进行多次运算,结果相同。在此函数内,其边界项(0、1项)简便,若是进行边界项复杂的函数,内存会大量浪费。

何时使用记忆化

何时以及为何要使用记忆化?它不像实现类似斐波纳契序列之类的日常任务。即使如此,我们也会采用不同的方式。我想到的实际用例是完全不同的。这里给你一些想法:

  • 我们可以减少针对 API 的调用次数。大多数提供商(例如 Google 运营的
    Google
    Maps)将限制你每天允许的调用次数。你可以使用记忆化快速构建内存或磁盘缓存。这将允许你快速切换回“旧”配置,而无需再次查询
    API。
  • 调用数据库或常规加载数据。想想一个 Shiny 应用程序,其中 UI
    的更改将触发对数据库的调用。例如,当你有参数化查询时。你缓存这些查询结果后,当用户在设置之间来回切换时,你可以大大加快应用程序的速度。

Whatever we do there needs to be an important property so that
memoization is useful. Wikipedia says:

无论我们做什么,有一个重要的属性是必要的,以便保证记忆化有用。维基百科:

一个函数只有在引用透明的情况下才能被记忆,也就是说,只有在调用函数与使用其返回值替换该函数调用具有完全相同的效果时。(但是,存在排除这种限制的特例。)

换句话说:我们需要留意函数的结果实际上只取决于输入参数。你是否相信你的数据库连接或
API
调用具有此属性?如果是这样,记忆化可能很有用。但要小心:记忆化导致缓存,缓存导致状态管理(何时以及如何更新缓存?),这导致难以调试的问题:确实很有趣。

memoization的思想是通过定义一个数组,用来存放计算过的数据,在需要的时候直接从数组中取出,而不必再次计算,从而省去大量不必要的动作。

以下是JS实现方式:

var fibonacci=function(n){
    var cache=[];//定义一个空数组用来存放计算好的数据
  if((n==0)||(n==1)){
    return n;
  }else{
    cache[n-1]=cache[n-1]||fibonacci(n-1);//应用||或运算符“短路”的特性,若在数组中找到其值,则直接使用数组内的值,若没有,再进行计算,并将值存入数组
    cache[n-2]=cache[n-2]||fibonacci(n-2);
    return cache[n-1]+cache[n-2];//返回数组中的值
  }
}

由上可以看出,在计算过一次后,数据被存入数组,再次调用时便会优先找到数组内的值而免于大量计算,从而提升效率。

以下是PHP实现(其实差不多。。。)

function fibonacci($n){
  $cache=[];
  if(($n==0)||($n==1)){
    return $n;
  }else{
    cacehe[$n-1]=cache[$n-1]||fibonacci($n-1);
    cacehe[$n-2]=cache[$n-2]||fibonacci($n-2);
    return cache[$n-1]+cache[$n-2];
  }
}

开始总结笔记了,如有错误,请各位不吝指正,谢谢。