Javascript 高性能之递归,迭代,查表法详解及实例
Javascript 高性能之递归,迭代,查表法详解
递归
概念:函数通过直接调用自身,或者两个函数之间的互相调用,来达到一定的目的,比如排序,阶乘等
简单的递归
阶乘
function factorial(n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); } }
递归实现排序
/* 排序且合并数组 */ function myMerge(left, right) { // 保存最后结果的数组 var res = []; // 有一个数组结束了就结束排序,一般情况下,两个数组长度应该保持一样 while (left.length > 0 && right.length > 0) { if ( left[0] < right[0] ) { // 把left第一个成员删除,存储到新数组res中 res.push(left.shift()); } else { res.push(right.shift()); } } // 如果还有剩余直接合并到新数组 return res.concat(left).concat(right); } /* 递归方式 */ function recursion(items) { if (items.length == 1) { return items; } var middle = Math.floor(items.length / 2), left = items.slice(0, middle), // 取数组前半部分 right = items.slice(middle); // 取数组后半部分 // 递归排序 return myMerge(recursion(left), recursion(right)); }
迭代
每个浏览器对递归都有调用栈上限的问题,且如果不小心使用也很容易造成死循环导致程序崩溃。如果考虑到性能问题,可以使用迭代来代替递归,因为运行循环总比反复调用函数的开销少很多
/* 迭代方式,不使用递归,可以避免出现栈溢出问题 */ function iteration(items) { if (items.length == 1) { return items; } var work = []; // 将items成员全部转化成数组,保存到数组中 for (var i = 0, len = items.length; i < len; i++) { work.push([items[i]]); } work.push([]); // 数组长度为奇数时 // 迭代 for (var lim = len; lim > 1; lim = (lim + 1) / 2) { for (var j = 0, k = 0; k < lim; j++, k+=2) { work[j] = myMerge(work[k], work[k + 1]); } work[j] = []; // 数组长度为奇数时 } return work[0]; } /* 迭代过程分析 假设: var test = [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(记忆): 函数可以用对象去记住先前操纵的成果,从而能避免无谓的运算
避免重复工作,将执行过的运算或操作,缓存起来,如果后续有相同的操作可直接从缓存中查找,没有则进行递归,可大大减少递归的工作量,提高性能。
var count = 0; function factorial(n) { console.log("factorial count = " + count++); if (n == 0) { return 1; } else { return n * factorial(n - 1); } } // var f1 = factorial(6); // var f2 = factorial(5); // var f3 = factorial(4); // >>>>> 结果是函数被调用了:18次 /* 递归优化:查表法,通过缓存 */ function memFactorial(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); } // 最终数据都可以在缓存中找到 return memFactorial.cache[n]; } var f1 = memFactorial(6); var f2 = memFactorial(5); var f3 = memFactorial(4); // >>>>> 结果是函数被调用了:只有8次,大大的减少了函数被调用的次数
Memoization通用版,但不建议使用,建议自己手动在普通版中实现函数内容
通用版需要缓存特定参数的函数调用结果,即,传入的参数不同,调用函数的时候,其结果需要缓存起来
/* 递归优化通用版,性能不如普通版,需要缓存每次调用结果, 即内部函数 */ function memoize(func, cache) { // 缓存池 cache = cache || {}; // 没有则新建 var result = function(arg) { // console.log("memoize count = " + count++); if (!cache.hasOwnProperty(arg)) { cache[arg] = func(arg); } }; return result; } // 使用 // 将阶乘函数缓存起来 // 只是优化了cache的通用性,但损失了一部分性能 var memOpfactorial = memoize(factorial, {"0": 1, "1": 1}); var f1 = memOpfactorial(6); var f2 = memOpfactorial(5); var f3 = memOpfactorial(4); // 结果次数依旧是:18次。因此不推荐使用
总结
- 谨慎使用递归,以防造成死循环,程序崩溃,或者调用栈溢出;
- 学会使用迭代来替代递归,可以避免递归调用栈或死循环问题出现;
- 查表法,递归的优化版:Memoization减少重复工作,提升性能。但不推荐使用通用版,相比普通版会损失部分性能。
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
赞 (0)