Javascript 高性能之遞歸，迭代，查表法詳解及實(shí)例

更新時(shí)間：2017年01月08日 14:49:03 作者：gccll

這篇文章主要介紹了Javascript 高性能之遞歸，迭代，查表法詳解及實(shí)例的相關(guān)資料,需要的朋友可以參考下

Javascript 高性能之遞歸，迭代，查表法詳解

遞歸

概念：函數(shù)通過(guò)直接調(diào)用自身，或者兩個(gè)函數(shù)之間的互相調(diào)用，來(lái)達(dá)到一定的目的，比如排序，階乘等

簡(jiǎn)單的遞歸

階乘

function factorial(n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

遞歸實(shí)現(xiàn)排序

/*
  排序且合并數(shù)組
 */
function myMerge(left, right) {
  // 保存最后結(jié)果的數(shù)組
  var res = [];

  // 有一個(gè)數(shù)組結(jié)束了就結(jié)束排序，一般情況下，兩個(gè)數(shù)組長(zhǎng)度應(yīng)該保持一樣
  while (left.length > 0 && right.length > 0) {
    if ( left[0] < right[0] ) {
      // 把left第一個(gè)成員刪除，存儲(chǔ)到新數(shù)組res中
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }

  // 如果還有剩余直接合并到新數(shù)組
  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), // 取數(shù)組前半部分
    right = items.slice(middle);  // 取數(shù)組后半部分

  // 遞歸排序
  return myMerge(recursion(left), recursion(right));
}

迭代

每個(gè)瀏覽器對(duì)遞歸都有調(diào)用棧上限的問(wèn)題，且如果不小心使用也很容易造成死循環(huán)導(dǎo)致程序崩潰。如果考慮到性能問(wèn)題，可以使用迭代來(lái)代替遞歸，因?yàn)檫\(yùn)行循環(huán)總比反復(fù)調(diào)用函數(shù)的開(kāi)銷(xiāo)少很多

/*
  迭代方式，不使用遞歸，可以避免出現(xiàn)棧溢出問(wèn)題
 */

function iteration(items) {
  if (items.length == 1) {
    return items;
  }

  var work = [];

  // 將items成員全部轉(zhuǎn)化成數(shù)組，保存到數(shù)組中
  for (var i = 0, len = items.length; i < len; i++) {
    work.push([items[i]]);
  }
  work.push([]); // 數(shù)組長(zhǎng)度為奇數(shù)時(shí)

  // 迭代
  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] = [];  // 數(shù)組長(zhǎng)度為奇數(shù)時(shí)
  }

  return work[0];
}

/* 迭代過(guò)程分析
  假設(shè)： 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]
    > 在后面添加個(gè)空數(shù)組是為了數(shù)組長(zhǎng)度為奇數(shù)時(shí)的情況，能有個(gè)對(duì)象做比較，否則會(huì)出現(xiàn)越界錯(cuò)誤
  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]
    > 最后一個(gè)[]會(huì)被myMerge函數(shù)給合并，所以不用擔(dān)心添加的空數(shù)組對(duì)后續(xù)產(chǎn)生影響
  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]
    > 至此排序整個(gè)過(guò)程全部完成

  // 關(guān)鍵點(diǎn)
  a) 將數(shù)組中的每個(gè)元素?cái)?shù)組化，以便后續(xù)存放已經(jīng)排好序的元素
  b) k的取值，k+=2, 每次取兩個(gè)數(shù)組進(jìn)行比較，形成一個(gè)新的數(shù)組
  c) 一定要在比較完之后附加空數(shù)組，否則會(huì)在數(shù)組個(gè)數(shù)為奇數(shù)個(gè)的時(shí)候出現(xiàn)訪問(wèn)越界錯(cuò)誤
  d) 最外層循環(huán)的lim的取值, lim = (lim + 1) / 2即原數(shù)組長(zhǎng)度的一半，作為內(nèi)循環(huán)終止的條件


*/

遞歸優(yōu)化，查表法-Memoization(記憶): 函數(shù)可以用對(duì)象去記住先前操縱的成果，從而能避免無(wú)謂的運(yùn)算

避免重復(fù)工作，將執(zhí)行過(guò)的運(yùn)算或操作，緩存起來(lái)，如果后續(xù)有相同的操作可直接從緩存中查找，沒(méi)有則進(jìn)行遞歸，可大大減少遞歸的工作量，提高性能。

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);
// >>>>> 結(jié)果是函數(shù)被調(diào)用了：18次

/*
  遞歸優(yōu)化：查表法，通過(guò)緩存
 */
function memFactorial(n) {

  console.log("memFactorial count = " + count++);

  // JS中函數(shù)即可視為一個(gè)對(duì)象，所以可以直接通過(guò)函數(shù)名＋點(diǎn)語(yǔ)法給此對(duì)象添加屬性
  if (!memFactorial.cache) { 
    memFactorial.cache = {
      "0": 1,
      "1": 1
    };
  }

  // hasOwnProperty(n)可以判斷對(duì)象中是否存在該屬性，不會(huì)查找原型（但是"in"會(huì)先查實(shí)例再原型）
  if (!memFactorial.cache.hasOwnProperty(n)) {
    // 緩存中不存在的情況下再進(jìn)行遞歸，并且將新數(shù)組緩存起來(lái)
    memFactorial.cache[n] = n * memFactorial(n - 1);
  }

  // 最終數(shù)據(jù)都可以在緩存中找到
  return memFactorial.cache[n];
}


var f1 = memFactorial(6);
var f2 = memFactorial(5);
var f3 = memFactorial(4);

// >>>>> 結(jié)果是函數(shù)被調(diào)用了：只有8次，大大的減少了函數(shù)被調(diào)用的次數(shù)

Memoization通用版，但不建議使用，建議自己手動(dòng)在普通版中實(shí)現(xiàn)函數(shù)內(nèi)容

通用版需要緩存特定參數(shù)的函數(shù)調(diào)用結(jié)果，即，傳入的參數(shù)不同，調(diào)用函數(shù)的時(shí)候，其結(jié)果需要緩存起來(lái)

/*
  遞歸優(yōu)化通用版，性能不如普通版，需要緩存每次調(diào)用結(jié)果, 即內(nèi)部函數(shù)  
 */ 
function memoize(func, cache) {
  // 緩存池
  cache = cache || {};  // 沒(méi)有則新建

  var result = function(arg) {
    // console.log("memoize count = " + count++);
    if (!cache.hasOwnProperty(arg)) {
      cache[arg] = func(arg);
    }
  };

  return result;
}  

// 使用
// 將階乘函數(shù)緩存起來(lái)
// 只是優(yōu)化了cache的通用性，但損失了一部分性能
var memOpfactorial = memoize(factorial, {"0": 1, "1": 1});

var f1 = memOpfactorial(6);
var f2 = memOpfactorial(5);
var f3 = memOpfactorial(4);

// 結(jié)果次數(shù)依舊是：18次。因此不推薦使用

總結(jié)