全部标签
写点什么
学习MySQL开源云计算行业资讯算法Python人工智能区块链Linux前端个人成长面试架构师编程企业动态新基建敏捷安全读书笔记高效工作团队管理创业活动专区生涯规划知识管理运维产品经理 查看更多

高性能 JavaScriptの笔记（三）

用户头像
空城机
关注
发布于: 2021 年 05 月 17 日
高性能 JavaScriptの笔记（三）

算法和流程控制

  • 代码的整体结构是影响运行速度的主要因素之一。

  • 代码数量少并不意味着运行速度快，只是看起来更加简洁。

  • 代码的组织结构和解决具体问题的思路是影响代码性能的主要因素

循环

循环处理是常见的编程模式，也是提升性能必须要关注的重点之一。

循环的类型

四种循环类型


  • for 循环

  • while 循环 while 循环是最简单的前测循环

  • do-while 循环 do-while 循环是 JavaScript 唯一一种后测循环，由两部分组成，循环体和后测条件。至少会运行一次

var i = 0;do {    // 循环主体} while ( i++ < 10 )
复制代码


  • for-in 循环可以枚举任何对象的属性名

for (var prop in object) {    // 循环主体}
复制代码

循环性能

在四种循环中，for-in 循环明显比其他几种循环要慢原因：for-in 循环每次迭代操作都会同时搜索实例或原型属性，对于相同迭代次数的循环，for-in 循环最终只有其他类型速度的 1/7

减少迭代工作量

减少迭代的工作量，一个提升循环整体速度的好方法就是限制循环中的耗时操作数量


例子：

for (var i = 0; i < items.length; i++) {     process(items[i])}
复制代码


在上面的 for 循环中，每次运行循环体都会产生如下操作：

  1. 在控制条件中查找一次属性 （ items.length )

  2. 在控制条件中比较一次数值 （ i < items.length )

  3. 一次比较操作，查看控制条件的计算结果是否为 true ( i < items.length == true )

  4. 一次自增操作 （ i++ )

  5. 一次数组查找 ( items[i] )

  6. 一次函数调用 （ process(items[i]) ）


优化方案①：将查询 items.length 的次数减少


例子：


for (var i = 0, len = items.length; i < len; i++) {    process(items[i])}
复制代码


优化方案②：倒序查找。 一般来说，数组项的顺序与所要执行的任务无关，因此可以使用倒序循环提审性能每个控制条件只是简单的与 0 进行比较这下控制条件从两次比较（迭代数小于总数？ 是否为 true？）--> 一次比较（是否为 true 吗？）


例子：


for(var i = items.length; i--;) {    process(items[i])}
复制代码


倒序操作过程：

  1. 一次控制条件中比较 （i == true）

  2. 一次减法操作 （ i-- )

  3. 一次数组查找 ( items[i] )

  4. 一次函数调用 （ process(items[i]) ）

提示

当循环复杂度为 O(n)时，减少每次迭代的工作量是最有效的方法。当复杂度大于 O(n)时，着重减少迭代次数

减少迭代次数 -- 达夫设备

达夫设备（Duff's Device）是一种限制循环迭代次数的模式是否应该使用达夫设备，很大程度上依赖于迭代次数


模板代码：

var i = items.length % n;           //先循环余数次数while(i){    process(items[i--]);}i = Math.floor(items.length / n);   //再循环8的整数倍次数  循环体是普通循环的8倍 可以写成函数传参调用while(i){    process(items[i--]);    process(items[i--]);    process(items[i--]);    process(items[i--]);    process(items[i--]);    process(items[i--]);    process(items[i--]);    process(items[i--]);}
复制代码


效率测试代码：

var arr = [], times = 10000000, times2 = 10000000;for (var i = 1; i <= times; i++) {   arr[i] = i ;}console.time('pre')var sum = 0;for (var i = 1; i <= times; i++) {   sum += (1 / arr[i]);}console.log(sum)console.timeEnd('pre')console.log('************************')// 达夫设备console.time('last')var all = 0;var len = times / 8, startAt = times % 8;do {    switch(startAt) {        case 0: all += (1 / arr[times--]);        case 1: all += (1 / arr[times--]);        case 2: all += (1 / arr[times--]);        case 3: all += (1 / arr[times--]);        case 4: all += (1 / arr[times--]);        case 5: all += (1 / arr[times--]);        case 6: all += (1 / arr[times--]);        case 7: all += (1 / arr[times--]);    }} while (--len)console.log(all)console.timeEnd('last')// 普通while循环console.time('last2')var sumall = 0;while(times2) {    sumall += (1 / arr[times2--]);} console.log(sumall)console.timeEnd('last2')
复制代码

提示

现代浏览器引擎其实已经经过几次优化了，在上面的效率测试代码运行时，如果 times 的次数在 1000 次左右的话，for 循环和 while 循环还有达夫设备运行速度相差不大

下面是执行次数多的情况：

chrome

如果在 chrome 浏览器中，while 循环和达夫设备明显速度快于 for 循环，但是 while 循环和达夫设备时间相差不大，甚至达夫设备可能会小于 while 循环

while > 达夫设备 > for 循环


测试 1：

测试 2：

测试 3：

IE

在 IE 浏览器中，达夫设备的效率会更高一些，for 循环效率低于 while 循环

达夫设备 > while > for 循环


测试 1：

测试 2：

测试 3：


FireFox

在火狐浏览器中也和 IE 类似

达夫设备 > while > for 循环


测试 1：

测试 2：

测试 3：


基于函数的迭代

基于函数的迭代：forEach()


forEach 遍历一个数组的所有成员，并执行一个函数


但是所有情况下，基于循环的迭代比基于函数的迭代快 8 倍，在运行速度要求严格时，基于循环的迭代优先于基于函数的迭代在严格要求性能时，基于函数的迭代不是合适的选择

条件语句

在 JavaScript 中，条件语句主要是 if-else 和 switch 两种


当条件判断的数量越大时，越倾向于使用 switch 语句， 这主要是为了代码的易读性


在大多数情况下，switch 比 if-else 更快。但是只有条件数量很大时才很明显


if-else 语句可以考虑拆分成嵌套的 if-else 语句，最小化条件判断的次数，比如二分法

递归

递归是可以将复杂的算法变得更加简单，比如阶乘函数：

function factorial(n) {    if (n == 0) {        return 1    } else {        return n * factorial(n - 1)    }}
复制代码

递归的缺点

①：递归函数潜在问题是终止条件不明确或缺少终止条件会导致函数长时间运行，也就是可能产生无限递归调用，使用户界面假死。


②： 递归函数还可能遇到浏览器的“调用栈大小限制”


调用栈限制

JavaScript 引擎支持的递归数量与 JavaScript 调用栈大小直接相关。

IE 浏览器的调用栈和系统内存有关，其他所有浏览器都有固定数量的调用栈大小

如果遇到调用栈限制，第一步应该先检查代码中的递归实例

递归模式

有两种递归模式值得注意，一种是“直接递归模式”，就是上面写的阶乘调用，出错时容易检查出来。

另一种是“隐伏模式”,两个函数互相调用，形成一个无限循环，这种模式出错很难被定位


例子：

function first() { second() }function second() { first() }
first();
复制代码

迭代

任何递归能实现的算法同样可以用迭代来实现。

迭代算法通常包含几个不同的循环，优化后的循环替代长时间运行的函数可以提升性能。


运行一个循环比反复调用一个函数的开销要少的多


把递归算法改用迭代实现是避免栈溢出错误的方法之一

Memoization

减少工作量就是最好的性能优化技术


多次执行相同的任务纯粹是浪费时间，Memoization 正是一种避免重复工作的方法。

比如之前的普通阶乘递归，用 Memoization 完善后效率大大提升了修改后：

function memfactorial(n) {    // 设置最初的memfactorial.cache    if (!memfactorial.cache) {        memfactorial.cache = {            "0": 1,            "1": 1        }    }    // 判断memfactorial.cache[n]是否存在  也可以直接!memfactorial.cache[n]    if (!memfactorial.cache.hasOwnProperty(n)) {        memfactorial.cache[n] = n * memfactorial(n - 1);    }    return memfactorial.cache[n];}
复制代码


测试效率：

console.time('普通递归')var six = factorial(16)console.timeEnd('普通递归')console.time('Memoization')var one = factorial(16)console.timeEnd('Memoization')
复制代码


效果


也可以将 Memoization 封装成一个基础函数 memoize()

注意：这种通用 Memoization 方法比手工更新的算法相比效果要差，最好手工实现


function memoize(fundamental, cache) {    cache = cache || {};    var shell = function(arg) {        if(!cache.hasOwnProperty(arg)) {            cache[arg] = fundamental(arg);        }        return cache[arg]    }    return shell;}
复制代码


调用通用函数：


var memfactorial = memoize(factorial)memfactorial(16)
复制代码

小节

平时写代码时可以优化的点①：避免使用 for-in 循环


平时写代码时可以优化的点②：将查询 items.length 的次数减少，并且没有严格顺序时，可以使用倒序查找，减少操作次数


平时写代码时可以优化的点③：在遇到栈溢出时，可以考虑使用 Memoization 来避免重复计算


划线
评论
复制
发布于: 2021 年 05 月 17 日阅读数: 22

版权声明: 本文为 InfoQ 作者【空城机】的原创文章。

原文链接:【http://xie.infoq.cn/article/510482c810e2b5ec3615ddaac】。

本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。

JavaScript前端前端进阶5月日更
用户头像

空城机

关注

曾经沧海难为水,只是当时已惘然 2021.03.22 加入

业余作者，在线水文 主要干前端的活，业余会学学python 欢迎各位关注，互相学习，互相进步

评论

发布
暂无评论
Copyright © 2021, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
高性能 JavaScriptの笔记（三）