javascript 數(shù)組去重的6種思路

AlphaWallet 發(fā)布于2019-08-26 11:39 / 2281人閱讀

摘要：但是這并不妨礙我們從思維拓展的角度出發(fā)，看看去重可以用幾種思路去實(shí)現(xiàn)。首先是常規(guī)的雙層循環(huán)比對(duì)的思路實(shí)現(xiàn)定義一個(gè)變量表示當(dāng)前元素在中是否存在。依次對(duì)中的元素和原數(shù)組元素進(jìn)行比對(duì)。重點(diǎn)是保證碰撞的幾率小到比中大獎(jiǎng)還小就可以了。

前端在日常開發(fā)中或多或少都會(huì)碰到有對(duì)數(shù)據(jù)去重的需求，實(shí)際上，像是lodash這些工具庫已經(jīng)有成熟完備的實(shí)現(xiàn)，并且可以成熟地運(yùn)用于生產(chǎn)環(huán)境。但是這并不妨礙我們從思維拓展的角度出發(fā)，看看去重可以用幾種思路去實(shí)現(xiàn)。

首先是常規(guī)的雙層循環(huán)比對(duì)的思路實(shí)現(xiàn)

function doubleLoopUniq(arr) {
  let result = [];
  for (let i = 0, len = arr.length, isExist; i < len; i++) {
    // 定義一個(gè)變量表示當(dāng)前元素在 result 中是否存在。
    isExist = false;
    for (let j = 0, rLen = result.length; j < rLen; j++) {
      if (result[j] === arr[i]) {
        // 依次對(duì)result 中的元素 和 原數(shù)組元素進(jìn)行比對(duì)。
        isExist = true;
        break;
      }
    }
    // 最后判斷如果不存在，則將此元素插入result
    !isExist && result.push(arr[i]);
  }
  return result;
}

借助 js內(nèi)置的indexOf 進(jìn)行去重

function indexOfUniq(arr) {
  let result = [];
  for (let i = 0, len = arr.length; i < len; i++) {
    // 用indexOf 簡化了二層循環(huán)的流程
    if (result.indexOf(arr[i]) === -1) result.push(arr[i]);
  }
  return result;
}

排序后前后比對(duì)去重

function sortUniq(arr) {
  let result = [], last;
  // 這里解構(gòu)是為了不對(duì)原數(shù)組產(chǎn)生副作用
  [ ...arr ].sort().forEach(item => {
    if (item != last) {
      result.push(item);
      last = item;
    }
  });
  return result;
}

通過hashTable去重

function hashUniq(arr) {
  let hashTable = arr.reduce((result, curr, index, array) => {
    result[curr] = true;
    return result;
  }, {})
  return Object.keys(hashTable).map(item => parseInt(item, 10));
}

ES6 SET一行代碼實(shí)現(xiàn)去重

function toSetUniq(arr) {
  return Array.from(new Set(arr));
}

splice 去重（直接操作數(shù)組本身，帶副作用）

function inPlaceUniq(arr) {
  let idx = 0;
  while (idx < arr.length) {
    let compare = idx + 1;
    while (compare < arr.length) {
      if (arr[idx] == arr[compare]) {
        arr.splice(compare, 1);
        continue;
      }
      ++compare
    }
    ++idx;
  }
  return arr;
}

最后在nodejs下面簡單跑個(gè)測試，看看哪個(gè)效率高~

let data = [];
for (var i = 0; i < 100000; i++) {
  data.push(Math.random())
}

// 實(shí)現(xiàn)一個(gè)性能測試的裝飾器
function performanceTest(fn, descript) {
  var a = new Date().getTime();
  return function () {
    fn.apply(this, [].slice.call(arguments, 0));
    console.log(descript, new Date().getTime() - a)
  }
}

performanceTest(hashUniq, "hashTable")(data)
performanceTest(sortUniq, "sortUniq")(data)
performanceTest(toSetUniq, "toSetUniq")(data)
performanceTest(indexOfUniq, "indexOfUniq")(data)
performanceTest(doubleLoopUniq, "doubleLoopUniq")(data)
performanceTest(inPlaceUniq, "inPlaceUniq")(data)

結(jié)果如下

hashTable 168ms
sortUniq 332ms
toSetUniq 80ms
indexOfUniq 4280ms
doubleLoopUniq 13303ms
inPlaceUniq 9977ms

延伸思考：如果數(shù)組內(nèi)的元素是對(duì)象該怎么去重呢？

既然是引用類型，那么不免會(huì)使用到deepEqual，固然這種思路可以解答這道問題，但難免不夠高效。

從上面的測試中也可見通過new Set 和 hashTable 去重是最高效的。
所以毫無疑問，我們要基于這兩種方式去改造，我想用的是hashTable，
另一方面，為了降低深度比較帶來的耗時(shí)，我嘗試用JSON.stringify 將引用類型轉(zhuǎn)化為基本類型。

function collectionUniq(collection) {
  let hashTable = {};
  collection.forEach(item => {
    hashTable[JSON.stringify(item)] = true;
  })
  return Object.keys(hashTable).map(item => JSON.parse(item))
}

那么問題來了，我們都知道對(duì)象的屬性是無序的，假如數(shù)據(jù)是這種情況，那就GG了。

let collection = [ { a: 1, b: 2, c: 3 }, { b: 2, c: 3, a: 1 } ]

有一種toHash的思路，在對(duì)這個(gè)數(shù)組進(jìn)行一次基本的去重之后，為了保證準(zhǔn)確，
先遍歷JSON 字符串 =>
通過 charCodeAt()拿到每個(gè)字符串的 unicode 編碼 =>
相加得到一個(gè)總數(shù)，最后再兩兩進(jìn)行比較，數(shù)值相等的就是重復(fù)的，這樣就達(dá)到去重的效果了。

function toHash(obj) {
  let power = 1;
  let res = 0;
  const string = JSON.stringify(obj, null, 2);
  for (let i = 0, l = string.length; i < l; i++) {
    switch (string[i]) {
      case "{":
        power *= 2
        break
      case "}":
        power /= 2
        break
      case " ":
      case "
":
      case "
":
      case "	":
      break
      default:
        res += string[i].charCodeAt(0) * power
    }
  }
  return res
}

這只是一個(gè)實(shí)現(xiàn)基本的思路，有很大的改進(jìn)空間，為了減少hash碰撞的可能，可以對(duì)一些特殊字符進(jìn)行權(quán)重的增減。

重點(diǎn)是保證碰撞的幾率小到比中大獎(jiǎng)還小就可以了。

2018.2.8
上面是一個(gè)比較清奇的思路，常規(guī)的做法，實(shí)際上還是應(yīng)該從優(yōu)化深度比較的效率入手。
看到一個(gè)很好的實(shí)現(xiàn)思路，是一個(gè)優(yōu)先判錯(cuò)的思路，通過預(yù)設(shè)各種前置條件來避免高代價(jià)的循環(huán)，這種思路盡管在數(shù)據(jù)量小的時(shí)候因?yàn)榍爸门袛嗫赡苡幸恍┪⒑跗湮⒌男阅軗p耗，但是數(shù)據(jù)量越大，優(yōu)勢(shì)就越明顯了。感興趣的可以了解下。
https://github.com/epoberezki...