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次。因此不推荐使用

总结

  1. 谨慎使用递归,以防造成死循环,程序崩溃,或者调用栈溢出;
  2. 学会使用迭代来替代递归,可以避免递归调用栈或死循环问题出现;
  3. 查表法,递归的优化版:Memoization减少重复工作,提升性能。但不推荐使用通用版,相比普通版会损失部分性能。

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • JS的数组迭代方法

    本文实例讲述了JS的数组迭代方法.分享给大家供大家参考.具体实现方法如下: <!doctype html> <html> <head lang="zh"> <meta charset="utf-8"> <title>js数组迭代</title> <meta name="renderer" content="webkit"> <script

  • 总结javascript中的六种迭代器

    1.forEach迭代器 forEach方法接收一个函数作为参数,对数组中每个元素使用这个函数,只调用这个函数,数组本身没有任何变化 //forEach迭代器 function square(num){ document.write(num + ' ' + num*num + '<br>'); } var nums = [1,2,3,4,5,6,7,8]; nums.forEach(square); 在浏览器中输出的结果是: 2.every迭代器 every方法接受一个返回值为布尔类型的函数,

  • js中递归函数的使用介绍

    下面我们就做一个10以内的阶乘试试看吧: js中递归函数的使用 function f(num){ if(num alert("10!的结果为:"+f(10)); [Ctrl+A 全选 注:如需引入外部Js需刷新才能执行] 递归函数的调用就说这么多了 js递归函数调用自身时的保险方式. 来自js高级程序设计 一个典型阶乘递归函数: 复制代码 代码如下: function fact(num){ if (num<=1){ return 1; }else{ return num*fact

  • javaScript数组迭代方法详解

    本文为大家介绍了javaScript数组迭代方法,供大家参考,具体内容如下 每个方法都接收两个参数:要在每一项上运行的函数  和  (可选的)运行该函数的作用域对象. 传入这些方法中的函数会接收三个参数:数组项的值,该项在数组中的位置,数组对象本身. forEach()  对数组中的每一项运行 给定函数.该方法没有返回值. every()  对数组中的每一项运行 给定函数,如果数组的每一项都返回true,则返回true. some()  对数组中的每一项运行 给定函数,如果数组的任意一项返回tr

  • 浅谈javascript 迭代方法

    五个迭代方法 都接受两个参数:要在每一项上运行的函数 和 运行该函数的作用域(可选) every():对数组中的每一项运行给定函数.如果函数对每一项都返回true,则返回true.         filter():对数组中的每一项运行给定函数.返回该函数会返回true的项组成的数组.         forEach():对数组中每一项运行给定函数.该函数没有返回值.         map():对数组中每一项运行给定函数.返回每次函数调用的结果组成的函数.         some():对数组

  • JavaScript 语言的递归编程

    题目:从1累加一直加到100的和是多少? 非递归的循环写法: 复制代码 代码如下: 1run: function() { 2 var sum = 0; 3 for(var i=1;i<=100;i++) { 4 sum = sum + i; 5 } 6 console.log(sum); 7} 递归的写法: 复制代码 代码如下: var testCase = { sum: 0, run: function(n) { if(n>=100) { return 100; } else { sum =

  • JS 树形递归实例代码

    复制代码 代码如下: var l=json.length; var arr = []; for(var i = 0; i < l; i++){ (function(){ var jsonArray =arguments[0]; for(var k in jsonArray){ if(k.indexOf('children') != -1 && jsonArray[k] != null){ arguments.callee(jsonArray[k]); } else{ if(k ==

  • JavaScript中的迭代器和生成器详解

    处理集合里的每一项是一个非常普通的操作,JavaScript提供了许多方法来迭代一个集合,从简单的for和for each循环到 map(),filter() 和 array comprehensions(数组推导式).在JavaScript 1.7中,迭代器和生成器在JavaScript核心语法中带来了新的迭代机制,而且还提供了定制 for-in 和 for each 循环行为的机制. 迭代器 迭代器是一个每次访问集合序列中一个元素的对象,并跟踪该序列中迭代的当前位置.在JavaScript中

  • js 数组实现一个类似ruby的迭代器

    分为如下几节: ·基本实现 ·在迭代中引用原来的对象,或者直接改变数组的值而不是返回一个新数组 ·向迭代传入无限多的参数 ·基本实现 今天突然发现js的数组处理起来真是麻烦,代码一些就是一大堆,相比起ruby的迭代器来真是逊色不少,主要是要写的代码太多了,也许是js有特殊的处理数组的方式,真是我不知道而已,但是我真的想自己给js实现一个类似ruby的迭代器的东东,而且实现起来也不难,那就开始动手吧. 真的应该庆幸js是动态语言啊,如果是静态语言,实现起来很不方便(别说要我重新定义一个继承自arr

  • JavaScript的递归之递归与循环示例介绍

    递归与循环 对于不同类型的需要重复计算的问题,循环和递归两种方法各有所长,能给出更直观简单的方案.另一方面,循环和递归的方法可以互相转换.任何一个循环的代码都可以用递归改写,实现相同的功能:反之亦然.在不失去其普遍性的前提下,可以把循环和递归分别用下列伪代码概括. 伪代码格式说明:循环采用while形式:变量不加定义:赋值用:=:条件表达式和执行的语句都写成函数的形式,圆括号内写上相关的值.其他语法方面,尽量接近Javascript的规范. 复制代码 代码如下: //pseudo code of

  • JavaScript Array Flatten 与递归使用介绍

    如何用 JavaScript 将 [1,2,3,[4,5, [6,7]], [[[8]]]] 这样一个 Array 变成 [1,2,3,4,5, 6,7,8] 呢?传说中的 Array Flatten. 处理这种问题,通常我们会需要递归,来让程序自己按照一种算法去循环.在某书说写着,"递归是一种强大的编程技术",好吧,她不仅仅属于 JavaScript.递归可以很难,也可以比较简单(总得来说还是比较难).处理上面这个问题,用递归来解决,应该是比较适合的.之前工友这样实现了,算是一个简单

  • JS中递归函数

    编程语言中,函数Func(Type a,--)直接或间接调用函数本身,则该函数称为递归函数.递归函数不能定义为内联函数. 递归函数: function factorical(num){ if(num<=1){ return 1; } else{ return num*factorical(num-1); } } factorial(2)//2 这个递归函数就是用函数来调用函数本身,但是这样真的好吗,好 接下来看这里 var another=factorical; factorical=null;

  • js数组的五种迭代方法及两种归并方法(推荐)

    js数组的五种迭代方法及两种归并方法(推荐) <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta ht

随机推荐