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

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

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

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

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

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

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

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

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

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

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

完整的代碼（實(shí)際使用中請(qǐng)考慮數(shù)據(jù)類(lèi)型校驗(yàn)和是否為空判斷）

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

// 模擬2個(gè)數(shù)組
var start = 1000000
// 定義模擬2個(gè)數(shù)組的方法；count: arr1的長(zhǎng)度值；n: 為arr2為arr1的長(zhǎng)度的多少倍
function getArr(count, n) {
  var o = {
    arr1: [],
    arr2: []
  }
  for(var i = 0; i
核心代碼：
// 使用降冪算法
// arr2進(jìn)行分組，建立以id值為key的對(duì)象
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項(xiàng)的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
}