JS數(shù)組關(guān)聯(lián)查找的性能優(yōu)化

Stardustsky 發(fā)布于2019-08-23 12:11 / 1480人閱讀

摘要：傳統(tǒng)個數(shù)組的嵌套查詢一般通過兩個循環(huán)體嵌套實現(xiàn)，時間復(fù)雜度為而通過建立索引對象的形式的時間復(fù)雜度為這種犧牲內(nèi)存來達(dá)到復(fù)雜度降冪的的方法能提高多少性能呢下面是以數(shù)組長度為數(shù)組為的亂序數(shù)組進行測試的測試結(jié)果。

傳統(tǒng)2個數(shù)組的嵌套查詢一般通過兩個循環(huán)體嵌套實現(xiàn)，時間復(fù)雜度為:n^2;
 而通過建立索引對象的形式的時間復(fù)雜度為：n;這種犧牲內(nèi)存來達(dá)到復(fù)雜度降冪的的方法能提高多少性能呢？

下面是以數(shù)組1長度為10000；數(shù)組2為50000的亂序數(shù)組進行測試的測試結(jié)果。(測試結(jié)果的單位都是ms)

Firefox測試結(jié)果: 平均快48倍

// 第一次
傳統(tǒng)的嵌套循環(huán):1479
建立索引:30
// 第二次
傳統(tǒng)的嵌套循環(huán):1852
建立索引:36
// 第三次
傳統(tǒng)的嵌套循環(huán):1754
建立索引:38

Chrome測試結(jié)果: 平均快64倍

// 第一次
傳統(tǒng)的嵌套循環(huán):1800
建立索引:26
// 第二次
傳統(tǒng)的嵌套循環(huán):1297
建立索引:35
// 第三次
傳統(tǒng)的嵌套循環(huán):2522
建立索引:27

IE11測試結(jié)果：平均快11倍

// 第一次
傳統(tǒng)的嵌套循環(huán):110431
建立索引:616
// 第二次
傳統(tǒng)的嵌套循環(huán):7172
建立索引:689
// 第三次
傳統(tǒng)的嵌套循環(huán):7310
建立索引:686

完整的代碼（實際使用中請考慮數(shù)據(jù)類型校驗和是否為空判斷）

// 情景：從數(shù)組arr1的id拿到數(shù)組arr2中的所有記錄，統(tǒng)計急了num的總和寫回到arr1中

// 模擬2個數(shù)組
var start = 1000000
// 定義模擬2個數(shù)組的方法；count: arr1的長度值；n: 為arr2為arr1的長度的多少倍
function getArr(count, n) {
  var o = {
    arr1: [],
    arr2: []
  }
  for(var i = 0; i
核心代碼：
// 使用降冪算法
// arr2進行分組，建立以id值為key的對象
function getArrGroup(arr, id) {
  var o = {}
  var len = arr.length
  var index
  for(var i = 0; i < len; i++){
    index = arr[i][id]
    // 建立索引，防止覆蓋
    if(o[index]===undefined){
      o[index] = [arr[i]]
    } else {
      o[index].push(arr[i])
    }
  }
  return o
}
// 給arr1項的count賦值
function setArrCount(arr, o, id, fn) {
  var len = arr.length
  for(var i = 0; i < len; i++) {
    arr[i] = fn(arr, o, i)// fn定義處理邏輯
  }
  console.log(arr)
  return arr
}