JavaScript数组高性能去重解决方案

在大多数的人眼里，数组去重是一个很简单的课题，很多人甚至熟练掌握了多种数组去重的方法，然而大多时候，我们却忽略了数组去重所消耗的时间资源。譬如我们在做前端性能优化的时候，又有多少人会考虑JavaScript的运行性能。今天，我将通过一组测试数据来给大家展示高性能数组去重的必要性。当然以上仅针对像我这样的强迫症患者，。

先展示下结论，有些不喜欢看过程的同学可以直接拿去用，当然你也可以使用本人的高性能js工具集：npm i efficient-js

// 最高性能数组去重方法 10万数量级：3毫秒，100万数量级：6毫秒，1000万数量级36毫秒
Array.prototype.distinct = function () {
  var hash=[];
  var obj = {};
  for (i = 0; this[i] != null; i++) {
    if(!obj[this[i]]){
      hash.push(this[i]);
      obj[this[i]] = this[i];
    }
  }
  return hash;
}

一、收集数组去重的方法

1、遍历数组法：实现思路：新建一个数组，遍历去要重的数组，当值不在新数组的时候（indexOf为-1）就加入该新数组中；

2、数组下标判断法：实现思路：如果当前数组的第 i 项在当前数组中第一次出现的位置不是 i，那么表示第 i 项是重复的，忽略掉。否则存入结果数组。

3、排序后相邻去除法：实现思路：给传入的数组排序，排序后相同的值会相邻，然后遍历排序后数组时，新数组只加入不与前一值重复的值。

4、优化遍历数组法（推荐）：实现思路：双层循环，外循环表示从0到arr.length，内循环表示从i+1到arr.length，将没重复的右边值放入新数组。（检测到有重复值时终止当前循环同时进入外层循环的下一轮判断）

5、ES6实现：

a、实现思路：ES6提供了新的数据结构Set。它类似于数组，但是成员的值都是唯一的，没有重复的值。Set函数可以接受一个数组（或类似数组的对象）作为参数，用来初始化。

b、实现思路：Array.filter() + indexOf

6、双重 for 循环（最容易理解）：实现思路：外层循环遍历元素，内层循环检查是否重复，当有重复值的时候，可以使用 push()，也可以使用 splice()

7、for...of + includes() （双重for循环的升级版）：实现思路：外层用 for...of 语句替换 for 循环，把内层循环改为 includes()，先创建一个空数组，当 includes() 返回 false 的时候，就将该元素 push 到空数组中 ，类似的，还可以用 indexOf() 来替代 includes()

8、Array.sort()：实现思路：首先使用 sort() 将数组进行排序，然后比较相邻元素是否相等，从而排除重复项

9、for...of + Object： 实现思路：利用Object唯一key的特性来实现去重

以上的方法去重都没问题，都可以实现数组去重的目的，但是性能差距很大，可能处理10000条数据以内的表现不回太明显，但是无论哪个程序都是由很多很多的指令组成的，假如你不去关注每一条指令的优化，而想当然的想直接优化程序，那么你注定会失败。“毋以善小而不为”，虽然用在这里有些欠妥，但大体就是这个意思，一切都要从细节入手。我们先看看上面的去重方法，方法很多，我们需理一下，虽然上面的方法看起来思路不一样，但是可以分为两类：遍历数组和直接使用内置方法

然而遍历数组的方式有很多种，甚至不止上面的这些方法，我们首先对比遍历数组的方法的效率，然后在对比其他的

二、建立多维度的测试模板并验证

以下是测试结果的环境

首先我们列出所有的遍历数组的方法

function getRandomIntInclusive(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min; //The maximum is inclusive and the minimum is inclusive 
}
var orgArray = Array.from(new Array(100000), ()=>{
    return getRandomIntInclusive(1, 1000);
})

// 普通for循环
Array.prototype.distinct1 = function () {
  var hash=[];
  for (i = 0; i < this.length; i++) {
     if(hash.indexOf(this[i])==-1){
      hash.push(this[i]);
     }
  }
  return hash;
}
// 优化版for循环
Array.prototype.distinct2 = function () {
  var hash=[];
  for (i = 0, len = this.length; i < len; i++) {
     if(hash.indexOf(this[i])==-1){
      hash.push(this[i]);
     }
  }
  return hash;
}
// 弱化版for循环
Array.prototype.distinct3 = function () {
  var hash=[];
  for (i = 0; this[i] != null; i++) {
     if(hash.indexOf(this[i])==-1){
      hash.push(this[i]);
     }
  }
  return hash;
}
// foreach
Array.prototype.distinct4 = function () {
  var hash=[];
  this.forEach(item => {
    if(hash.indexOf(item)==-1){
      hash.push(item);
     }
  })
  return hash;
}
// foreach变种
Array.prototype.distinct5 = function () {
  var hash=[];
  Array.prototype.forEach.call(this, item => {
    if(hash.indexOf(item)==-1){
      hash.push(item);
     }
  })
  return hash;
}
// forin
Array.prototype.distinct6 = function () {
  var hash=[];
  for (key in this) {
　　　var item = this[key]
     if(hash.indexOf(item)==-1){
      hash.push(item);
     }
  }
  return hash;
}
// map
Array.prototype.distinct7 = function () {
  var hash=[];
  this.map(item => {
     if(hash.indexOf(item)==-1){
      hash.push(item);
     }
  });
  return hash;
}
// forof
Array.prototype.distinct8 = function () {
  var hash=[];
  for (let item of this) {
     if(hash.indexOf(item)==-1){
      hash.push(item);
     }
  }
  return hash;
}
var startTime,endTime, rtn;
function test(types) {
  types.forEach(type => {
    startTime = new Date();
    rtn = orgArray[type]();
    endTime = new Date();
    console.log(`数量级[${orgArray.length/10000}万]去重后数组长度为${rtn.length},使用${type}消耗时长${endTime - startTime}毫秒`)
    console.log('----------------------------------------------------------------------');
  })
}
var testArray = [];
for (i = 1; i <= 8;i++) {
  testArray.push('distinct' + i);
}
test(testArray)

输出结果：

　　把数据量级提高到100万、1000万，测试结果如下：

基于以上测试结果我们可以排除forin，但是其他的遍历数组的方法相差不到，我们取目前表现最好的弱化版for循环（其实针对我们的测试环境是强化版，哈哈）

(distinct6的去重后结果居然是1008，这个其实个for in的遍历机制有关，for in会遍历其原型链，所以for in不适合遍历数组，具体参考forin和forof的区别)

　　 上代码

function getRandomIntInclusive(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min; //The maximum is inclusive and the minimum is inclusive 
}
var orgArray = Array.from(new Array(100000), ()=>{
    return getRandomIntInclusive(1, 1000);
})


// indexOf
Array.prototype.distinct1 = function () {
  var hash=[];
  for (i = 0; this[i] != null; i++) {
     if(hash.indexOf(this[i])==-1){
      hash.push(this[i]);
     }
  }
  return hash;
}

// 数组下标判断法
Array.prototype.distinct2 = function () {
  var hash=[];
  for (i = 0; this[i] != null; i++) {
     if(this.indexOf(this[i])==i){
      hash.push(this[i]);
     }
  }
  return hash;
}

// includes
Array.prototype.distinct3 = function () {
  var hash=[];
  for (i = 0; this[i] != null; i++) {
     if(!hash.includes(this[i])){
      hash.push(this[i]);
     }
  }
  return hash;
}

// Object
Array.prototype.distinct4 = function () {
  var hash=[];
  var obj = {};
  for (i = 0; this[i] != null; i++) {
     if(!obj[i]){
      hash.push(this[i]);
      obj[i] = this[i];
     }
  }
  return hash;
}

var startTime,endTime, rtn;
function test(types) {
  types.forEach(type => {
    startTime = new Date();
    rtn = orgArray[type]();
    endTime = new Date();
    console.log(`数量级[${orgArray.length/10000}万]去重后数组长度为${rtn.length},使用${type}消耗时长${endTime - startTime}毫秒`)
    console.log('----------------------------------------------------------------------');
  })
}
var testArray = [];
for (i = 1; i <= 4;i++) {
  testArray.push('distinct' + i);
}
test(testArray)

　　测试结果如下

　　这个结果就拉开差距了，在看下100万和1000万的结果

　　结论很明确，数据量级呈线性增长，正常的遍历数组的方式中中用objec的方法效率大大领先其他方法，我们再次来回顾下object方法的实现思路，

　　利用Object唯一key的特性来实现去重　　

　　为了保证不漏掉，我们object的去重取执行所有的遍历方法

function getRandomIntInclusive(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min; //The maximum is inclusive and the minimum is inclusive 
}
var orgArray = Array.from(new Array(100000), ()=>{
    return getRandomIntInclusive(1, 1000);
})

// 普通for循环
Array.prototype.distinct1 = function () {
  var hash=[];
  var obj = {};
  for (i = 0; i < this.length; i++) {
    if(!obj[this[i]]){
      hash.push(this[i]);
      obj[this[i]] = this[i];
    }
  }
  return hash;
}
// 优化版for循环
Array.prototype.distinct2 = function () {
  var hash=[];
  var obj = {};
  for (i = 0, len = this.length; i < len; i++) {
    if(!obj[this[i]]){
      hash.push(this[i]);
      obj[this[i]] = this[i];
    }
  }
  return hash;
}
// 弱化版for循环
Array.prototype.distinct3 = function () {
  var hash=[];
  var obj = {};
  for (i = 0; this[i] != null; i++) {
    if(!obj[this[i]]){
      hash.push(this[i]);
      obj[this[i]] = this[i];
    }
  }
  return hash;
}
// foreach
Array.prototype.distinct4 = function () {
  var hash=[];
  var obj = {};
  this.forEach(item => {
    if(!obj[item]){
      hash.push(item);
      obj[item] = item;
    }
  })
  return hash;
}
// foreach变种
Array.prototype.distinct5 = function () {
  var hash=[];
  var obj = {};
  Array.prototype.forEach.call(this, item => {
    if(!obj[item]){
      hash.push(item);
      obj[item] = item;
    }
  })
  return hash;
}
// forin
Array.prototype.distinct6 = function () {
  var hash=[];
  var obj = {};
  for (key in this) {
　　var item = this[key];
    if(!obj[item]){
      hash.push(item);
      obj[item] = item;
    }
  }
  return hash;
}
// map
Array.prototype.distinct7 = function () {
  var hash=[];
  var obj = {};
  this.map(item => {
    if(!obj[item]){
      hash.push(item);
      obj[item] = item;
    }
  });
  return hash;
}
// forof
Array.prototype.distinct8 = function () {
  var hash=[];
  var obj = {};
  for (let item of this) {
    if(!obj[item]){
      hash.push(item);
      obj[item] = item;
    }
  }
  return hash;
}
var startTime,endTime, rtn;
function test(types) {
  types.forEach(type => {
    startTime = new Date();
    rtn = orgArray[type]();
    endTime = new Date();
    console.log(`数量级[${orgArray.length/10000}万]去重后数组长度为${rtn.length},使用${type}消耗时长${endTime - startTime}毫秒`)
    console.log('----------------------------------------------------------------------');
  })
}
var testArray = [];
for (i = 1; i <= 8;i++) {
  testArray.push('distinct' + i);
}
test(testArray)

　　结论如下

　　依然再次测试100万和1000万的，结果如下

　　可以得出结论，普通的for循环（优化版、弱化版）加上Object的组合在遍历数组的方法大幅领先其他方法，我们现在可以使用object与其他方法进行对比来

　　(distinct6的去重后结果居然是1008，这个其实个for in的遍历机制有关，for in会遍历其原型链，所以for in不适合遍历数组，具体参考forin和forof的区别)

function getRandomIntInclusive(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min; //The maximum is inclusive and the minimum is inclusive 
}
var orgArray = Array.from(new Array(100000), ()=>{
    return getRandomIntInclusive(1, 1000);
})

// 普通for循环
Array.prototype.distinct1 = function () {
  var hash=[];
  var obj = {};
  for (i = 0; i < this.length; i++) {
    if(!obj[this[i]]){
      hash.push(this[i]);
      obj[this[i]] = this[i];
    }
  }
  return hash;
}
// 优化版for循环
Array.prototype.distinct2 = function () {
  var hash=[];
  var obj = {};
  for (i = 0, len = this.length; i < len; i++) {
    if(!obj[this[i]]){
      hash.push(this[i]);
      obj[this[i]] = this[i];
    }
  }
  return hash;
}
// 弱化版for循环
Array.prototype.distinct3 = function () {
  var hash=[];
  var obj = {};
  for (i = 0; this[i] != null; i++) {
    if(!obj[this[i]]){
      hash.push(this[i]);
      obj[this[i]] = this[i];
    }
  }
  return hash;
}
// new Set() + [...]
Array.prototype.distinct4 = function () {
  return [...new Set(this)];
}
// new Set() + Array.from
Array.prototype.distinct5 = function () {
  return Array.from(new Set(this));
}
// Array.filter() + Object
Array.prototype.distinct6 = function () {
  var hash=[];
  var obj = {};
  return this.filter(item => {
    if (!obj[item]) {
      obj[item] = item;
      return true;
    }
  })
}
// 双重for循环
Array.prototype.distinct7 = function () {
  let arr = [...this];
  for (let i=0, len=arr.length; i {
    startTime = new Date();
    rtn = orgArray[type]();
    endTime = new Date();
    console.log(`数量级[${orgArray.length/10000}万]去重后数组长度为${rtn.length},使用${type}消耗时长${endTime - startTime}毫秒`)
    console.log('----------------------------------------------------------------------');
  })
}
var testArray = [];
for (i = 1; i <= 8;i++) {
  testArray.push('distinct' + i);
}
test(testArray)

　　结果如下

　　基本上可以去除双重for循环和Array.sort()，我们再次测试100万数量级别的

　　双重for循环执行挂掉了。。。看下30万的

　　我们去除双重for循环执行100万和1000万

　　很明显普通for循环（包含优化版和弱化版）+ Object遥遥领先。

三、给出测试结果报告

　　　通过多次执行普通for循环、优化版、弱化版，最终得出结论，效率：弱化版>普通版>优化版

　　弱化版可以更名特殊版，哈哈

// 最高性能数组去重方法 10万数量级：3毫秒，100万数量级：6毫秒，1000万数量级36毫秒
Array.prototype.distinct = function () {
  var hash=[];
  var obj = {};
  for (i = 0; this[i] != null; i++) {
    if(!obj[this[i]]){
      hash.push(this[i]);
      obj[this[i]] = this[i];
    }
  }
  return hash;
}