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; }