Javascript 高性能之递归，迭代，查表法详解及实例
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));
}
迭代
每个浏览器对递归都有调用栈上限的问题，且如果不小心使用也很容易造成死循环导致程序崩溃。如果考虑到性能问题，可以使用迭代来代替递归，因为运行循环总比反复调用函数的开销少很多
/*
迭代方式，不使用递归，可以避免出现栈溢出问题
*/
functioniteration(items){
if(items.length==1){
returnitems;
}
varwork=[];
//将items成员全部转化成数组，保存到数组中
for(vari=0,len=items.length;i<len;i++){
work.push([items[i]]);
}
work.push([]);//数组长度为奇数时
//迭代
for(varlim=len;lim>1;lim=(lim+1)/2){
for(varj=0,k=0;k<lim;j++,k+=2){
work[j]=myMerge(work[k],work[k+1]);
}
work[j]=[];//数组长度为奇数时
}
returnwork[0];
}
/*迭代过程分析
假设：vartest=[1,3,9,7,4,8,6,5,0,2];//len==10
work=[[1],[3],[9],[7],[4],[8],[6],[5],[0],[2],[]];//len==11;
//迭代(二分法)
a)lim:11>1
1)k=0,work[0]=myMerge([1],[3])==>work[0]=[1,3]
2)k=2,work[1]=myMerge([9],[7])==>work[1]=[7,9]
3)k=4,work[2]=myMerge([4],[8])==>work[2]=[4,8]
4)k=6,work[3]=myMerge([6],[5])==>work[3]=[5,6]
5)k=8,work[4]=myMerge([0],[2])==>work[4]=[0,2]
>在后面添加个空数组是为了数组长度为奇数时的情况，能有个对象做比较，否则会出现越界错误
b)lim:6>1,work=[[1,3],[7,9],[4,8],[5,6],[0,2],[]];
1)k=0,work[0]=myMerge([1,3],[7,9])==>work[0]=[1,3,7,9]
2)k=2,work[1]=myMerge([4,8],[5,6])==>work[1]=[4,5,6,8]
3)k=4,work[2]=myMerge([0,2],[])==>work[2]=[0,2]
>最后一个[]会被myMerge函数给合并，所以不用担心添加的空数组对后续产生影响
c)lim:3>1,work=[[1,3,7,9],[4,5,6,8],[0,2],[]];
1)k=0,work[0]=myMerge([1,3,7,9],[4,5,6,8])==>work[0]=[1,3,4,5,6,7,8,9]
2)k=2,work[1]=myMerge([0,2],[])==>work[1]=[0,2]
d)lim:2,work=[[1,3,4,5,6,7,8,9],[0,2],[]];
1)k=0,work[0]=myMerge([1,3,4,5,6,7,8,9],[0,2])==>work[0]=[0,1,2,3,4,5,6,7,8,9]
>至此排序整个过程全部完成
//关键点
a)将数组中的每个元素数组化，以便后续存放已经排好序的元素
b)k的取值，k+=2,每次取两个数组进行比较，形成一个新的数组
c)一定要在比较完之后附加空数组，否则会在数组个数为奇数个的时候出现访问越界错误
d)最外层循环的lim的取值,lim=(lim+1)/2即原数组长度的一半，作为内循环终止的条件
*/
递归优化，查表法-Memoization(记忆):函数可以用对象去记住先前操纵的成果，从而能避免无谓的运算
避免重复工作，将执行过的运算或操作，缓存起来，如果后续有相同的操作可直接从缓存中查找，没有则进行递归，可大大减少递归的工作量，提高性能。
varcount=0;
functionfactorial(n){
console.log("factorialcount="+count++);
if(n==0){
return1;
}else{
returnn*factorial(n-1);
}
}
//varf1=factorial(6);
//varf2=factorial(5);
//varf3=factorial(4);
//>>>>>结果是函数被调用了：18次
/*
递归优化：查表法，通过缓存
*/
functionmemFactorial(n){
console.log("memFactorialcount="+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);
//>>>>>结果是函数被调用了：只有8次，大大的减少了函数被调用的次数
Memoization通用版，但不建议使用，建议自己手动在普通版中实现函数内容
通用版需要缓存特定参数的函数调用结果，即，传入的参数不同，调用函数的时候，其结果需要缓存起来
/*
递归优化通用版，性能不如普通版，需要缓存每次调用结果,即内部函数
*/
functionmemoize(func,cache){
//缓存池
cache=cache||{};//没有则新建
varresult=function(arg){
//console.log("memoizecount="+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减少重复工作，提升性能。但不推荐使用通用版，相比普通版会损失部分性能。
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！