草庐IT

关于 "尾调用优化" 的那些事儿

CoderBin 2023-03-28 原文
大家好,我是 CoderBin

前言

本文将给大家介绍 JavaScript 函数中关于尾调用优化的优点与写法,助你提升编码能力?

如果文中有不对、疑惑的地方,欢迎在评论区留言指正?

1. 尾调用优化是什么

首先,尾调用的概念非常简单:就是指 某个函数的最后一步是调用另一个函数 。那什么是尾调用优化呢?

ECMAScript 6 规范新增了一项内存管理优化机制,让 JavaScript 引擎在满足条件时可以重用栈帧 。具体来说,这项优化非常适合“尾调用”,即 外部函数的返回值是一个内部函数的返回值。 例如:

function outerFn() { return innerFn(); // 尾调用 } 在 ES6 优化前后,执行上面的代码在内存中的表现是不一样的,在讲解之前,需要先了解 "函数调用栈"

2. 函数调用栈的补充

我们知道,函数调用会在内存形成一个"调用记录",又称"调用帧"(call frame),保存调用位置和内部变量等信息。如果在函数A的内部调用函数B,那么在A的调用记录上方,还会形成一个B的调用记录。等到B运行结束,将结果返回到A,B的调用记录才会消失。如果函数B内部还调用函数C,那就还有一个C的调用记录栈,以此类推。所有的调用记录,就形成一个"调用栈"(call stack)。

3. 函数执行在内存中的表现

了解了函数调用栈之后,就可以开始说明上面代码的执行过程了。

3.1 首先是 ES6 优化之前的过程

  1. 执行到 outerFn 函数体,第一个栈帧被推到栈上。
  2. 执行 outerFn 函数体,到return 语句。计算返回值必须先 计算 innerFn 。
  3. 执行到 innerFn 函数体,第二个栈帧被推到栈上。
  4. 执行 innerFn 函数体,计算其返回值。
  5. 将返回值传回 outerFn ,然后 outerFn 再返回值。
  6. 将栈帧弹出栈外。

3.2 在ES6优化之后,执行这个例子会在内存中发生如下操作:

  1. 执行到 outerFn 函数体,第一个栈帧被推到栈上。
  2. 执行 outerFn 函数体,到达 return 语句。为求值返回语 句,必须先求值 innerFn 。
  3. 引擎发现把第一个栈帧弹出栈外也没问题,因为 innerFn 的返回值也是 outerFn 的返回值。
  4. 弹出 outerFn 的栈帧。
  5. 执行到 innerFn 函数体,栈帧被推到栈上。
  6. 执行 innerFn 函数体,计算其返回值。
  7. 将 innerFn 的栈帧弹出栈外。
很明显,第一种情况下每多调用一次嵌套函数,就会多增加一个栈帧。而第二种情况下无论调用多少次嵌套函数,都只有一个栈帧。这就是ES6尾调用优化的关键:如果函数的逻辑允许基于尾调用将其销毁,则引擎就会那么做。

注意:现在还没有办法测试尾调用优化是否起作用。不过,因为这是 ES6 规范所规定的,兼容的浏览器实现都能保证在代码满足条件的情况下应用这个优化。

4. 尾调用优化的条件

尾调用优化的条件就是确定外部栈帧真的没有必要存在了。涉及的条件如下:

  • 代码在严格模式下执行;
  • 外部函数的返回值是对尾调用函数的调用;
  • 尾调用函数返回后不需要执行额外的逻辑;
  • 尾调用函数不是引用外部函数作用域中自由变量的闭包。

5. 不符合尾调用优化的要求的例子

下面展示了几个违反上述条件的函数:

'use strict' // 无优化:尾调用没有返回 function outerFunction() { innerFunction() } // 无优化:尾调用没有直接返回 function outerFunction() { let innerFunctionResult = innerFunction() return innerFunctionResult } // 无优化:尾调用返回后必须转型为字符串 function outerFunction() { return innerFunction().toString() } // 无优化:尾调用是一个闭包 function outerFunction() { let foo = 'bar' function innerFunction() { return foo } return innerFunction() }

6. 符合尾调用优化的要求的例子

下面是几个符合尾调用优化条件的例子:

'use strict' // 有优化:栈帧销毁前执行参数计算 function outerFunction(a, b) { return innerFunction(a + b) } // 有优化:初始返回值不涉及栈帧 function outerFunction(a, b) { if (a < b) { return a } return innerFunction(a + b) } // 有优化:两个内部函数都在尾部 function outerFunction(condition) { return condition ? innerFunctionA() : innerFunctionB() } 差异化尾调用和递归尾调用是容易让人混淆的地方。无论是递归尾调用还是非递归尾调用,都可以应用优化。引擎并不区分尾调用中调用的是函数自身还是其他函数。不过,这个优化在递归场景下的效果是最明显的,因为递归代码最容易在栈内存中迅速产生大量栈帧。

注意:之所以要求严格模式,主要因为在非严格模式下函数调用中允许使用f.argumentsf.caller,而它们都会引用外部函数的栈 帧。显然,这意味着不能应用优化了。因此尾调用优化要求必须在严格模式下有效,以防止引用这些属性。

7. 尾调用递归的改造

可以通过把简单的递归函数转换为待优化的代码来加深对尾调用优化的理解。下面是一个通过递归计算斐波纳契数列的函数:

function fib(n) { if (n < 2) { return n } return fib(n - 1) + fib(n - 2) } console.log(fib(0)) // 0 console.log(fib(1)) // 1 console.log(fib(2)) // 1 console.log(fib(3)) // 2 console.log(fib(4)) // 3 console.log(fib(5)) // 5 console.log(fib(6)) // 8 显然这个函数不符合尾调用优化的条件,因为返回语句中有一个相加的操作。结果,fib(n) 的栈帧数的内存复杂度是 O(2^n)。因此,即使这么一个简单的调用也可以给浏览器带来麻烦:

fib(1000) 当然,解决这个问题也有不同的策略,比如把递归改写成迭代循环形式。不过,也可以保持递归实现,但将其重构为满足优化条件的形式。为此可以使用两个嵌套的函数,外部函数作为基础框架,内部函数执行递归:

'use strict' // 基础框架 function fib(n) { return fibImpl(0, 1, n) } // 执行递归 function fibImpl(a, b, n) { if (n === 0) { return a } return fibImpl(b, a + b, n - 1) } 这样重构之后,就可以满足尾调用优化的所有条件,再调用 fib(1000) 就不会对浏览器造成威胁了。


每文一句:学习犹如登山,有的人则注重最终目标,有的人则注重前进的过程,不论哪种,都有其各自丰富的内涵,无孰优劣孰之分,只要你觉得适合即可。

本次的分享就到这里,如果本章内容对你有所帮助的话欢迎点赞+收藏。文章有不对的地方欢迎指出,有任何疑问都可以在评论区留言。希望大家都能够有所收获,大家一起探讨、进步!

有关关于 "尾调用优化" 的那些事儿的更多相关文章

  1. 使用 ACL 调用 upload_file 时出现 Ruby S3 "Access Denied"错误 - 2

    我正在尝试编写一个将文件上传到AWS并公开该文件的Ruby脚本。我做了以下事情:s3=Aws::S3::Resource.new(credentials:Aws::Credentials.new(KEY,SECRET),region:'us-west-2')obj=s3.bucket('stg-db').object('key')obj.upload_file(filename)这似乎工作正常,除了该文件不是公开可用的,而且我无法获得它的公共(public)URL。但是当我登录到S3时,我可以正常查看我的文件。为了使其公开可用,我将最后一行更改为obj.upload_file(file

  2. c# - 如何在 ruby​​ 中调用 C# dll? - 2

    如何在ruby​​中调用C#dll? 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器,如果它还没有,则使用Ruby的WIN32OLE库来调用它;看看RubyCLR,其中一位作者是JohnLam,他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了,可能不支持.Net2.0以上的版本);正如其他地方已经提到的,看看使用IronRuby,如果这是您的技术选择。有一个主题是here.请注意,最后一篇文章实际上来自JohnLam(看起来像是2009年3月),他似乎很自在地断言RubyCL

  3. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java,并成功地将它与另一个Java包一起使用,但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  4. ruby - 调用其他方法的 TDD 方法的正确方法 - 2

    我需要一些关于TDD概念的帮助。假设我有以下代码defexecute(command)casecommandwhen"c"create_new_characterwhen"i"display_inventoryendenddefcreate_new_character#dostufftocreatenewcharacterenddefdisplay_inventory#dostufftodisplayinventoryend现在我不确定要为什么编写单元测试。如果我为execute方法编写单元测试,那不是几乎涵盖了我对create_new_character和display_invent

  5. 【鸿蒙应用开发系列】- 获取系统设备信息以及版本API兼容调用方式 - 2

    在应用开发中,有时候我们需要获取系统的设备信息,用于数据上报和行为分析。那在鸿蒙系统中,我们应该怎么去获取设备的系统信息呢,比如说获取手机的系统版本号、手机的制造商、手机型号等数据。1、获取方式这里分为两种情况,一种是设备信息的获取,一种是系统信息的获取。1.1、获取设备信息获取设备信息,鸿蒙的SDK包为我们提供了DeviceInfo类,通过该类的一些静态方法,可以获取设备信息,DeviceInfo类的包路径为:ohos.system.DeviceInfo.具体的方法如下:ModifierandTypeMethodDescriptionstatic StringgetAbiList​()Obt

  6. C51单片机——实现用独立按键控制LED亮灭(调用函数篇) - 2

    说在前面这部分我本来是合为一篇来写的,因为目的是一样的,都是通过独立按键来控制LED闪灭本质上是起到开关的作用,即调用函数和中断函数。但是写一篇太累了,我还是决定分为两篇写,这篇是调用函数篇。在本篇中你主要看到这些东西!!!1.调用函数的方法(主要讲语法和格式)2.独立按键如何控制LED亮灭3.程序中的一些细节(软件消抖等)1.调用函数的方法思路还是比较清晰地,就是通过按下按键来控制LED闪灭,即每按下一次,LED取反一次。重要的是,把按键与LED联系在一起。我打算用K1来作为开关,看了一下开发板原理图,K1连接的是单片机的P31口,当按下K1时,P31是与GND相连的,也就是说,当我按下去时

  7. ruby - 如何找到调用当前方法的方法 - 2

    如何找到调用此方法的位置?defto_xml(options={})binding.pryoptions=options.to_hifoptions&&options.respond_to?(:to_h)serializable_hash(options).to_xml(options)end 最佳答案 键入caller。这将返回当前调用堆栈。文档:Kernel#caller.例子[0]%rspecspec10/16|===================================================62=====

  8. ruby-on-rails - 使用 HTTParty 的非常基本的 Rails 4.1 API 调用 - 2

    Rails相对较新。我正在尝试调用一个API,它应该向我返回一个唯一的URL。我的应用程序中捆绑了HTTParty。我已经创建了一个UniqueNumberController,并且我已经阅读了几个HTTParty指南,直到我想要什么,但也许我只是有点迷路,真的不知道该怎么做。基本上,我需要做的就是调用API,获取它返回的URL,然后将该URL插入到用户的数据库中。谁能给我指出正确的方向或与我分享一些代码? 最佳答案 假设API为JSON格式并返回如下数据:{"url":"http://example.com/unique-url"

  9. ruby - 为什么当我调用类的实例方法时,初始化不显示为方法? - 2

    我正在写一篇关于在Ruby中几乎一切都是对象的博客文章,我试图通过以下示例来展示这一点:classCoolBeansattr_accessor:beansdefinitialize@bean=[]enddefcount_beans@beans.countendend所以从类中我们可以看出它有4个方法(当然,除非我错了):它可以在创建新实例时初始化一个默认的空bean数组它可以计算它有多少个bean它可以读取它有多少个bean(通过attr_accessor)它可以向空数组写入(或添加)更多bean(也通过attr_accessor)但是,当我询问类本身它有哪些实例方法时,我没有看到默认

  10. ruby-on-rails - Rake 任务仅调用一次时执行两次 - 2

    我写了一个非常简单的rake任务来尝试找到这个问题的根源。namespace:foodotaskbar::environmentdoputs'RUNNING'endend当在控制台中执行rakefoo:bar时,输出为:RUNNINGRUNNING当我执行任何rake任务时会发生这种情况。有没有人遇到过这样的事情?编辑上面的rake任务就是写在那个.rake文件中的所有内容。这是当前正在使用的Rakefile。requireFile.expand_path('../config/application',__FILE__)OurApp::Application.load_tasks这里

随机推荐