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

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

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

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

遞歸

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

簡單的遞歸

階乘

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

遞歸實現(xiàn)排序

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

  // 有一個數(shù)組結(jié)束了就結(jié)束排序，一般情況下，兩個數(shù)組長度應(yīng)該保持一樣
  while (left.length > 0 && right.length > 0) {
    if ( left[0] < right[0] ) {
      // 把left第一個成員刪除，存儲到新數(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));
}

迭代

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

/*
  迭代方式，不使用遞歸，可以避免出現(xià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ù)組長度為奇數(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ù)組長度為奇數(shù)時
  }

  return work[0];
}

/* 迭代過程分析
  假設(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]
    > 在后面添加個空數(shù)組是為了數(shù)組長度為奇數(shù)時的情況，能有個對象做比較，否則會出現(xiàn)越界錯誤
  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函數(shù)給合并，所以不用擔心添加的空數(shù)組對后續(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]
    > 至此排序整個過程全部完成

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


*/

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

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

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)化：查表法，通過緩存
 */
function memFactorial(n) {

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

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

  // hasOwnProperty(n)可以判斷對象中是否存在該屬性，不會查找原型（但是"in"會先查實例再原型）
  if (!memFactorial.cache.hasOwnProperty(n)) {
    // 緩存中不存在的情況下再進行遞歸，并且將新數(shù)組緩存起來
    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通用版，但不建議使用，建議自己手動在普通版中實現(xiàn)函數(shù)內(nèi)容

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

/*
  遞歸優(yōu)化通用版，性能不如普通版，需要緩存每次調(diào)用結(jié)果, 即內(nèi)部函數(shù)  
 */ 
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;
}  

// 使用
// 將階乘函數(shù)緩存起來
// 只是優(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é)