最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
Javascript高性能之递归,迭代,查表法详解及实例
时间:2017-01-09 编辑:简简单单 来源:一聚教程网
Javascript 高性能之递归,迭代,查表法详解
递归
概念:函数通过直接调用自身,或者两个函数之间的互相调用,来达到一定的目的,比如排序,阶乘等
简单的递归
阶乘
代码如下 | 复制代码 |
functionfactorial(n) {
if(n == 0) {
return1;
}else{
returnn * factorial(n - 1);
}
}
|
递归实现排序
代码如下 | 复制代码 |
/*
排序且合并数组
*/
functionmyMerge(left, right) {
// 保存最后结果的数组
varres = [];
// 有一个数组结束了就结束排序,一般情况下,两个数组长度应该保持一样
while(left.length > 0 && right.length > 0) {
if( left[0] < right[0] ) {
// 把left第一个成员删除,存储到新数组res中
res.push(left.shift());
}else{
res.push(right.shift());
}
}
// 如果还有剩余直接合并到新数组
returnres.concat(left).concat(right);
}
/*
递归方式
*/
functionrecursion(items) {
if(items.length == 1) {
returnitems;
}
varmiddle = Math.floor(items.length / 2),
left = items.slice(0, middle),// 取数组前半部分
right = items.slice(middle); // 取数组后半部分
// 递归排序
returnmyMerge(recursion(left), recursion(right));
}
|
迭代
每个浏览器对递归都有调用栈上限的问题,且如果不小心使用也很容易造成死循环导致程序崩溃。如果考虑到性能问题,可以使用迭代来代替递归,因为运行循环总比反复调用函数的开销少很多
递归优化,查表法-Memoization(记忆): 函数可以用对象去记住先前操纵的成果,从而能避免无谓的运算
避免重复工作,将执行过的运算或操作,缓存起来,如果后续有相同的操作可直接从缓存中查找,没有则进行递归,可大大减少递归的工作量,提高性能。
代码如下 | 复制代码 |
varcount = 0;
functionfactorial(n) {
console.log("factorial count = "+ count++);
if(n == 0) {
return1;
}else{
returnn * factorial(n - 1);
}
}
// var f1 = factorial(6);
// var f2 = factorial(5);
// var f3 = factorial(4);
// >>>>> 结果是函数被调用了:18次
/*
递归优化:查表法,通过缓存
*/
functionmemFactorial(n) {
console.log("memFactorial count = "+ count++);
// JS中函数即可视为一个对象,所以可以直接通过函数名+点语法给此对象添加属性
if(!memFactorial.cache) {
memFactorial.cache = {
"0": 1,
"1": 1
};
}
// hasOwnProperty(n)可以判断对象中是否存在该属性,不会查找原型(但是"in"会先查实例再原型)
if(!memFactorial.cache.hasOwnProperty(n)) {
// 缓存中不存在的情况下再进行递归,并且将新数组缓存起来
memFactorial.cache[n] = n * memFactorial(n - 1);
}
// 最终数据都可以在缓存中找到
returnmemFactorial.cache[n];
}
varf1 = memFactorial(6);
varf2 = memFactorial(5);
varf3 = memFactorial(4);
|
Memoization通用版,但不建议使用,建议自己手动在普通版中实现函数内容
通用版需要缓存特定参数的函数调用结果,即,传入的参数不同,调用函数的时候,其结果需要缓存起来
代码如下 | 复制代码 |
/*
递归优化通用版,性能不如普通版,需要缓存每次调用结果, 即内部函数
*/
functionmemoize(func, cache) {
// 缓存池
cache = cache || {}; // 没有则新建
varresult =function(arg) {
// console.log("memoize count = " + count++);
if(!cache.hasOwnProperty(arg)) {
cache[arg] = func(arg);
}
};
returnresult;
}
// 使用
// 将阶乘函数缓存起来
// 只是优化了cache的通用性,但损失了一部分性能
varmemOpfactorial = memoize(factorial, {"0": 1,"1": 1});
varf1 = memOpfactorial(6);
varf2 = memOpfactorial(5);
varf3 = memOpfactorial(4);
// 结果次数依旧是:18次。因此不推荐使用
|
总结
- 谨慎使用递归,以防造成死循环,程序崩溃,或者调用栈溢出;
- 学会使用迭代来替代递归,可以避免递归调用栈或死循环问题出现;
- 查表法,递归的优化版:Memoization减少重复工作,提升性能。但不推荐使用通用版,相比普通版会损失部分性能。
-
上一个: Three.js的基础部分学习
相关文章
- JavaScript实现二分查找实例代码 04-24
- JavaScript实现的鼠标响应颜色渐变效果完整实例 04-17
- JavaScript实现图像模糊化的方法实例 02-04
- JavaScript中localStorage对象存储方式实例分析 01-14
- javascript中定时器的实例代码 12-20
- JavaScript 创建对象的实例详解 06-28