您的位置: 首页 > 技术文档 > 网页制作 > 提升JavaScript运行速度之递归篇
你是一个职业的页面重构工作者吗? 回到列表 CSS3系列教程
 提升JavaScript运行速度之递归篇

作者:明达 时间: 2009-02-26 文档类型:翻译 来自:七月佑安

影响JavaScript性能的另外一个杀手就是递归,在上一节中提到采用memoization技术可以优化计算数值的递归函数,但memoization不是万能的,不是所有的递归函数都可以用memoization技术优化,本文介绍了这些情况,并介绍了解决办法,就是将递归转换为迭代,同时需要注意,本文末尾介绍的方案不是最终的方案,还需要和上一节优化循环的方案综合起来才能达到最佳效果。

【原文】Speed up your JavaScript, Part 3
【作者】Nicholas C. Zakas
【译文】http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
【译者】明达

以下是对原文的翻译

递归是拖慢脚本运行速度的大敌之一。太多的递归会让浏览器变得越来越慢直到死掉或者莫名其妙的突然自动退出,所以我们一定要解决在JavaScript中出现的这一系列性能问题。在这个系列文章的第二篇中,我曾经简短的介绍了如何通过memoization技术来替代函数中太多的递归调用。memoization是一种可以缓存之前运算结果的技术,这样我们就不需要重新计算那些已经计算过的结果。对于通过递归来进行计算的函数,memoization简直是太有用了。我现在使用的memoizer是由 Crockford写的,主要应用在那些返回整数的递归运算中。当然并不是所有的递归函数都返回整数,所以我们需要一个更加通用的memoizer()函数来处理更多类型的递归函数。

function memoizer(fundamental, cache) {
  cache = cache || {};
  var shell = function(arg) {
      if (! (arg in cache)) {
          cache[arg] = fundamental(shell, arg);
      }
      return cache[arg];
  };
  return shell;}

这个版本的函数和Crockford写的版本有一点点不同。首先,参数的顺序被颠倒了,原有函数被设置为第一个参数,第二个参数是缓存对象,为可选参数,因为并不是所有的递归函数都包含初始信息。在函数内部,我将缓存对象的类型从数组转换为对象,这样这个版本就可以适应那些不是返回整数的递归函数。在shell函数里,我使用了in操作符来判断参数是否已经包含在缓存里。这种写法比测试类型不是undefined更加安全,因为undefined是一个有效的返回值。我们还是用之前提到的斐波纳契数列来做说明:

var fibonacci = memoizer(function(recur, n) {
  return recur(n - 1) + recur(n - 2);
}, { "0": 0, "1": 1} );

同样的,执行fibonacci(40)这个函数,只会对原有的函数调用40次,而不是夸张的331,160,280次。memoization对于那些有着严格定义的结果集的递归算法来说,简直是棒极了。然而,确实还有很多递归算法不适合使用memoization方法来进行优化。

我在学校时的一位教授一直坚持认为,任何使用递归的情况,如果有需要,都可以使用迭代来代替。实际上,递归和迭代经常会被作为互相弥补的方法,尤其是在另外一种出问题的情况下。将递归算法转换为迭代算法的技术,也是和开发语言无关的。这对JavaScript来说是很重要的,因为很多东西在执行环境中是受到限制的(the importance in JavaScript is greater, though, because the resources of the execution environment are so restrictive.)。让我们回顾一个典型的递归算法,比如说归并排序,在JavaScript中实现这个算法需要下面的代码:

function merge(left, right) {
  var result = [];
  while (left.length > 0 && right.length > 0) {
      if (left[0] < right[0]) {
          result.push(left.shift());
      } else {
          result.push(right.shift());
      }
  }
  return result.concat(left).concat(right);
}

//采用递归实现的归并排序算法
function mergeSort(items) {
  if (items.length == 1) {
      return items;
  }
  var middle = Math.floor(items.length / 2),
  left = items.slice(0, middle),
  right = items.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

调用mergeSort()函数处理一个数组,就可以返回经过排序的数组。注意每次调用mergeSort()函数,都会有两次递归调用。这个算法不可以使用memoization来进行优化,因为每个结果都只计算并使用一次,就算缓冲了结果也没有什么用。如果你使用mergeSort()函数来处理一个包含100个元素的数组,总共会有199次调用。1000个元素的数组将会执行1999次调用。在这种情况下,我们的解决方案是将递归算法转换为迭代算法,也就是说要引入一些循环(关于算法,可以参考这篇《List Processing: Sort Again, Naturally》):

// 采用迭代实现的归并排序算法
function mergeSort(items) {
  if (items.length == 1) {
      return items;
  }
  var work = [];
  for (var i = 0,
  len = items.length; i < len; i++) {
      work.push([items[i]]);
  }
  work.push([]); //in case of odd number of items
  for (var lim = len; lim > 1; lim = (lim + 1) / 2) {
      for (var j = 0,
      k = 0; k < lim; j++, k += 2) {
          work[j] = merge(work[k], work[k + 1]);
      }
      work[j] = []; //in case of odd number of items
  }
  return work[0];
}

这个归并排序算法实现使用了一系列循环来代替递归进行排序。由于归并排序首先要将数组拆分成若干只有一个元素的数组,这个方法更加明确的执行了这个操作,而不是通过递归函数隐晦的完成。work数组被初始化为包含一堆只有一个元素数组的数组。在循环中每次会合并两个数组,并将合并后的结果放回 work数组中。当函数执行完成后,排序的结果会通过work数组中的第一个元素返回。在这个归并排序的实现中,没有使用任何递归,同样也实现了这个算法。然而,这样做却引入了大量的循环,循环的次数基于要排序的数组中元素的个数,所以我们可能需要使用在 上篇讨论过的技术 来进行修订,处理这些额外开销。

总结一下基本原则,不管是什么时候使用递归的时候都应该小心谨慎。memoization和迭代是代替递归的两种解决方案,最直接的结果当然就是避免那个 提示脚本失控的对话框

本文链接:http://www.blueidea.com/tech/web/2009/6462.asp 

出处:七月佑安
责任编辑:bluehearts

◎进入论坛网页制作WEB标准化版块参加讨论,我还想发表评论

相关文章 更多相关链接
重温Javascript继承机制
再谈javascript图片预加载技术
如何编写高质量的Javascript代码
加载 Javascript 最佳实践
GC与JS内存泄露
作者文章 更多作者文章
JavaScript扩展之__noSuchMethod__
面向Web开发者和设计者的参考手册
提升JavaScript运行速度之DOM篇
Firefox扩展的全局命名空间污染
提升JavaScript运行速度之函数篇
关键字搜索 常规搜索 推荐文档
热门搜索:CSS Fireworks 设计比赛 网页制作 web标准 用户体验 UE photoshop Dreamweaver Studio8 Flash 手绘 CG
站点最新 站点最新列表
周大福“敬•自然”设计大赛开启
国际体验设计大会7月将在京举行
中国国防科技信息中心标志征集
云计算如何让安全问题可控
云计算是多数企业唯一拥抱互联网的机会
阿里行云
云手机年终巨献,送礼标配299起
阿里巴巴CTO王坚的"云和互联网观"
1499元买真八核 云OS双蛋大促
首届COCO桌面手机主题设计大赛
栏目最新 栏目最新列表
浅谈JavaScript编程语言的编码规范
如何在illustrator中绘制台历
Ps简单绘制一个可爱的铅笔图标
数据同步算法研究
用ps作简单的作品展示页面
CSS定位机制之一:普通流
25个最佳最闪亮的Eclipse开发项目
Illustrator中制作针线缝制文字效果
Photoshop制作印刷凹凸字体
VS2010中创建自定义SQL Rule

蓝色理想版权申明:除部分特别声明不要转载,或者授权我站独家播发的文章外,大家可以自由转载我站点的原创文章,但原作者和来自我站的链接必须保留(非我站原创的,按照原来自一节,自行链接)。文章版权归我站和作者共有。

转载要求:转载之图片、文件,链接请不要盗链到本站,且不准打上各自站点的水印,亦不能抹去我站点水印。

特别注意:本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有,文章若有侵犯作者版权,请与我们联系,我们将立即删除修改。

您的评论
用户名:  口令:
说明:输入正确的用户名和密码才能参与评论。如果您不是本站会员,你可以注册 为本站会员。
注意:文章中的链接、内容等需要修改的错误,请用报告错误,以利文档及时修改。
不评分 1 2 3 4 5
注意:请不要在评论中含与内容无关的广告链接,违者封ID
请您注意:
·不良评论请用报告管理员,以利管理员及时删除。
·尊重网上道德,遵守中华人民共和国的各项有关法律法规
·承担一切因您的行为而直接或间接导致的民事或刑事法律责任
·本站评论管理人员有权保留或删除其管辖评论中的任意内容
·您在本站发表的作品,本站有权在网站内转载或引用
·参与本评论即表明您已经阅读并接受上述条款
推荐文档 | 打印文档 | 评论文档 | 报告错误  
专业书推荐 更多内容
网站可用性测试及优化指南
《写给大家看的色彩书1》
《跟我去香港》
众妙之门—网站UI 设计之道
《Flex 4.0 RIA开发宝典》
《赢在设计》
犀利开发—jQuery内核详解与实践
作品集 更多内容

杂⑦杂⑧ Gold NORMANA V2