如何提升JavaScript的运行速度(递归篇)
作者:Nicholas C. Zakas 来源:nczonline.net 发布时间:2010-05-17 13:30:00
影响 JavaScript性能的另外一个杀手就是递归,在上一节中提到采用memoization技术可以优化计算数值的递归函数,但memoization 不是万能的,不是所有的递归函数都可以用memoization技术优化,本文介绍了这些情况,并介绍了解决办法,就是将递归转换为迭代,同时需要注意,本文末尾介绍的方案不是最终的方案,还需要和上一节优化循环的方案综合起来才能达到最佳效果。
以下是对原文的翻译:
递归是拖慢脚本运行速度的大敌之一。太多的递归会让浏览器变得越来越慢直到死掉或者莫名其妙的突然自动退出,所以我们一定要解决在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和迭代是代替递归的两种解决方案,最直接的结果当然就是避免那个提示脚本失控的对话框。 (翻译:明达)
猜你喜欢
- 1 , javascript字符集:javascript采用的是Unicode字符集编码。为什么要采用这个编码呢?原因很简单,16位的Uni
- 看一看自己写的类是否能符合这样的标准.要成为高手,我要走的路还很长.摘抄自《OOD 启示录》--Arthur J.Riel(1)所有数据都应
- js模拟随机抽奖程序代码!相关文章推荐:随机6+1选号码摇奖程序 <html><title>模拟抽奖-asp之家&l
- 没注意到MooTools的Cookie类在写的时候自己做了一次encode,在读的时候做了一次decode,在一般的情况下,这个不会有什么问
- 做设计类网址导航的初衷是为了资源整合,也是在尝试解决问题。假定访问用户都是行业人士,或者目地性很强的有一定了解的用户,应该如何考虑这个组织系
- 最近,为了能在数据库服务器中运行其他应用程序,在保持数据库操作系统版本不变的前提下对数据库服务器进行了软、硬件上的升级。在软件上,将操作系统
- 代码如下: <% dim fso,objFolder,objFiles dim filelist Set fso=Server.Cre
- 什么是JSON http://www.json.org/json-zh.htmlJSON(Javascript Object Notatio
- 如何在ADSI中查询用户属性?看看下面这个返回用户可用属性的代码实例,基本上返回了大部分可用的用户属性:<%Dim x&nb
- 存储过程的优缺点: 存储过程优点: 1.由于应用程序随着时间推移会不断更改,增删功能,T-SQL过程代码会变得更复杂,StoredProce
- 写这段代码的原因是昨天项目中遇到的一个问题。一同事要求 写一个效果要求鼠标掠过表格行该行颜色改变以突出显示。这个倒不难,那哥们直接为每个Tr
- 首先建一个access 数据库,库中有一个URLINDEX表,其中URL和Keywords字段分别添加了索引,如下:URL &nb
- 问题:如何保护自己的ASP源代码不泄露? 答:下载微软的Windows Script Encoder,对ASP的脚本和客户端javascri
- 在默认情况下,大多数浏览器都会将有序列表中的数字序列的与其列表文字内容显示为相同的字体。这篇快速教程将教你如何使用有序列表(ol)和段落(p
- 代码如下:--建立数据表createtable TestData ( ID int identity(1,1) primary key, D
- 我们经常会用到表格数据,在做表格的时候,一般都喜欢隔行变色,使表格表现数据的时候非常的清晰。如图,我设计的一个表格表现的样式:在网上找到一个
- { hide_text } CSS文字隐藏总结报告最近整理的一份CSS文字隐藏的demo,总结了几种方法,希望得出一种最完美的方案放进自己的
- 阅读上一篇:FrontPage2002简明教程四:网页超级链接 一、三种添加CSS的方式 在FrontPage 2002里可以通过三种方式给
- 许多游戏玩家一定会对游戏中的动态鼠标指针有很深的印象,其实只要一句简单的CSS(层叠样式表),你也能在网页上实现这种效果。首先,你需要一个鼠
- jQuery的makeArray有其局限性(1.3.4还有bug),我自己实现了一个,不过涉及N多辅助方法。var dom = {},_to