JavaScript 数组高性能去重 千万级数据去重效率测试 高效去重详解

引言

  网上能搜出一堆关于数据去重的例子，以及测试效率耗时都不尽相同。然而却没给出必要的解释，为什么不同人测试出来的效率不一样呢？本文就详细通过大量测试探索一下，去重效率损耗主要在哪儿？不一样的数据为什么用不同去重方案测试效率耗时不一样?给千万级的数据去重该选用哪种去重方法?

测试前提

1.测试工具 chrome浏览器
2.测试电脑配置 小米笔记本 i7-8500U 16GB
3.系统 windows10 64位

测试准备

  分别创建一个1万、10万、100万、1000万的简单数据，这里我们不取随机数，创建固定重复的量的数据（分别重复20%，50%，80%）。并使重复数据平均分布，测试各种常用去重方法效率。

// distinctTest.js
var myriad = [];
// 代码就写一个1万的例子，避免篇幅过长。
[2, 5, 8].map(item => {
  myriad.push(Array.from(new Array(10000), function (item2, i) {
    return i % 10 < item || Math.random();
  }))
  // 可在此处添加十万、百万.. 数据
})

function distinct(arr) {
    // 此处为去重代码
  return arr;
}

myriad.forEach(item => {
  var length = item.length;
  console.log(`数据长度：${item.length}`)
  console.time("耗时")
  var newArr = distinct(item)
  console.timeEnd("耗时")
  console.log(`数据重复量：${length - newArr.length}`)
  console.log('————————————————————————————————————————————')
})
123456789101112131415161718192021222324

测试效率

1.双重for循环 + splice / flag

方法解释：
  第一种在元素重复时删除重复的元素，剩余的元素就是去重后的数据。splice会改变原数组，如果不想更改，可以用concat复制一份，如：var newArr = arr.concat()不传入数据相当于复刻一份。
  第二种就是用flag标记，新数组中存在相同数据就不往新数组插入当前数据。
去重代码：

// 使用splice删除
function distinct(arr) {
  for (var i = 0, len = arr.length; i < len; i++) {
    for (var i2 = i + 1; i2 < len; i2++) {
      if (arr[i] === arr[i2]) { 
        arr.splice(i2, 1); // 删除重复的数据
        i2--; // 删除数据后index需要前移一位
        len = arr.length; // 删除数据后重新获取数组长度
      }
    }
  }
  return arr;
}

// 使用flag标记
function distinct(arr) {
  var newArr = []
  for (var i = 0, len = arr.length; i < len; i++) {
    var flag = true
    for (var i2 = 0; i2 < newArr.length; i2++) {
      if (arr[i] === newArr[i2]) { 
        flag = false
        break;
      }
    }
    flag && newArr.push(arr[i])
  }
  return newArr;
}

123456789101112131415161718192021222324252627282930

测试结果：
splice
测试结果图
flag

`数据长度：10000`             | `数据长度：100000`             | `数据长度：1000000`
数据重复量：1999              | 数据重复量：19999             | 页面崩溃
耗时: 98.783935546875ms         | 耗时: 9475.10009765625ms     | 
——————————————————————————     | ——————————————————————————     |
数据重复量：4999              | 数据重复量：49999             |
耗时: 46.31298828125ms         | 耗时: 3659.33984375ms        | 
——————————————————————————     | ——————————————-———————————    | 
数据重复量：7999              | 数据重复量：79999             | 
耗时: 7.68310546875ms         | 耗时: 587.00927734375ms        | 
123456789

结果描述：
  双重循环去重，使用splice，会更改原来数组数据，在数据不到1万时，处理效率还可接受。达到10万时需要10多秒，达到100万页面直接崩溃。使用flag判断稍快于上方，而且重复数据越多，耗时差异越大。

方法效率分析：
  1.splice删除数据元素，100万条数据都删除，耗时在8秒（8000ms）左右，波动幅度较大，根据重复量多少，效率损耗有明显差异。
  2. 1万条平均分布的数据，重复20%，需要循环3千多万次，重复50%，需要循环1千多万次，重复80%，需要循环2百多万次。而十万条数据在此之上翻了100倍，从以上1万数据与10万数据耗时也能看出，时长比超过100倍。因循环次数的急剧增多，耗时也100倍增长。

2.for 循环加 indexOf / includes

方法解释：
  此方法通过判断新数组中是否存在当前循环到的元素，如果没有就把当前循环到的元素插入新数组。

去重代码：

function distinct(arr) {
  var newArray = [];
  for (let i = 0, len = arr.length; i < len; i++) {
    newArray.indexOf(arr[i]) === -1 && newArray.push(arr[i])
    // !newArray.includes(arr[i]) && newArray.push(arr[i])
  }
  return newArray;
}
12345678

测试结果：
测试结果图
结果描述：
  for 也可以替换为 for of，虽然for of循环比for慢，但是for of直接返回元素本身，而不需要通过下标取数组数据，for in就不需要考虑了，同样返回下标，却比for慢了将近1万倍。不过for in可以遍历对象，这是其他循环比不了的。

  处理1万以内数据效率很高，10万条时，就需要几秒了。百万页面虽未直接崩溃，等待几分钟还未出结果，不过比上面双重循环效率高。indexOf与includes效率相同，只是返回值不一样。考虑到indexOf兼容性强于includes，推荐使用indexOf，当然写法上includes更加简洁。其实这种方法和上方的双重循环是一样的，因为indexOf和includes都是内部循环从数据下标0处开始循环查询，数据越靠数组后方，查询耗时越长，因为循环次数越多。

方法效率分析：
  1.经测试，indexOf和includes效率比的for循环判断值快了一倍左右，所以虽然实际上都是双重循环，但是整体效率高于双重for循环。
  2.即使在千万级的数据下循环加push耗时也不多，2千万次循环加push耗时不超过200毫秒。
  3.主要耗时还是在indexOf与includes判断数据是否重复这一点上，千万级的数据，如果要判断数据是否重复，不重复的数据要从头循环到尾，耗时非常明显。重复数据越少，耗时越多。

3.filter 加 indexOf

方法解释：
  通过indexOf判断此元素第一次出现的位置与当前的元素的index是否相同来去重。

去重代码：

function distinct(arr) {
  return arr.filter((item, i) => {
    return arr.indexOf(item) === i
  });
}
12345

测试结果：
测试结果图
结果描述：
  在效率稍上低于for加indexOf的方法，数据量重复较少的情况与for 加indexOf处理效率上差不多，但数据量多的时候效率就有了明显的差别，同样在千万级的数据下无法处理。

方法效率分析：
  1.此方法本质上与上述两种一样，都是双重循环，同样使用了indexOf，主要的效率损耗就在个上面。
  2.经测试filter都返回false比都返回true要快，也就是重复越多越快，这就引起我们猜想，返回true类似于push了新数据到新数组。
  3.重复量越大，与for加indexOf去重差距就越明显，数组filter方法效率明显要低于for循环（最后有纯粹的循环效率耗时对比）。

4.使用sort排序后去重

方法解释：
  利用sort排序，使相同元素相邻排列，通过判断当前下标与前一个下标元素是否相同从而插入新数据。我见过有人用当前下标与下一个下标元素判断，但是那种方法最后一个元素是undefined时，会造成undefined无法被判断为不重复的元素，要解决这个问题就会造成多的判断，以至于效率下降。sort排序会更改原数组，如果不想更改可以用concat()拷贝一份，如：var newArr = arr.concat()原为数组拼接，不传入数据相当于复刻一份。

去重代码：

function distinct(arr) {
  arr.sort((a, b) => a - b)
  var arrry = [arr[0]];
  for (var i = 1, len = arr.length; i < len; i++) {
    if (arr[i] !== arr[i - 1]) {
      arrry.push(arr[i]);
    }
  }
  return arrry;
}
12345678910

测试结果：
测试结果图
结果描述：
  使用sort排序后去重效率有了显著的提升，数据1百万也能在1秒内处理完。即使1千万也能勉强处理。不过当前配置电脑处理超过2千万的数据，会进入断点提示Paused before potential out-of-memory crash（在潜在的内存不足崩溃之前暂停）。在去重数值类型数据上sort排序去重效率有很大提升。
方法效率分析：
  1.利用了sort排序，主要计算时间就在排序上。如果是顺序的数值类型数组，在sort排序上所需时间就极少，经测试，这种数据即使1千万条、重复20%，也能在1秒内处理完。
  2. 这种方法也能去重其他类型数据，只需要把sort排序传入的函数去掉就行。不过在数据处理的效率上就比较差了，10万数据时就已经接近1秒钟了，100万也只能勉强处理，千万就需要用分钟计算了。

5.sort 加 reduce

方法解释：
  使用sort排序后，利用reduce特性，对比新数组最后一个元素与循环到的当前元素是否相等，不相等就插入数据。

去重代码：

function distinct(arr) {
  arr.sort((a, b) => a - b)
  return arr.reduce((newArr, current) => {
    if (newArr[newArr.length - 1] !== current) {
      newArr.push(current);
    }
    return newArr;
  }, [arr[0]]);
}
123456789

测试结果：
测试结果图
结果描述：
  此方法与上面一种方法效率相似，数据较小时（10万以内），差异并不大，数据较大时能看出差异。同样当前配置电脑处理超过2千万的数据，会进入断点提示Paused before potential out-of-memory crash（在潜在的内存不足崩溃之前暂停）。

方法效率分析：
  1.与上一个方法一样利用了sort排序，主要计算时间就在排序上。
  2.此方法与上面相比差异不大，虽然reduce循环比for循环慢（后面有纯粹循环耗时排行），但在取值对比上面稍快。

6.利用对象key唯一(hasOwnProperty)

方法解释：
  对象key具有唯一性，通过给对象key赋值、取值判断元素是否重复，不重复就push数据到新数组，重复就跳过。

去重代码：

function distinct(arr) {
  var newArrry = [];
  var obj = {};
  for (var i = 0, len = arr.length; i < len; i++) {
    if (obj[arr[i]] !== 1) { // obj.hasOwnProperty(arr[i]) 也可以
      newArrry.push(arr[i])
      obj[arr[i]] = 1
    }
  }
  return newArrry;
}
1234567891011

测试结果：
测试结果图
结果描述：
  此方法计算速度还不错，与sort排序后去重效率相当，同样是超过2千万数据后会进入断点（同上）。不过对象属性不重复有比较大的问题就是
  1.true 和"true"在设为对象key时，值是一样的。（解决方法 使用 typeof+key）
  2.无法设置复杂类型数据为key，结果key只能为[object Object]（解决方法 使用 typeof+toString）
处理的方法过多会造成效率的下降，因此不再此方法上多下功夫，如果数据类型明确，也可以使用这种方法。

方法效率分析：
  1.对象属性的存取需要消耗比较多的时间(利用hasOwnProperty判断属性是否存在效率也是一样)。
  2.剩余少部分时间消耗在循环和push数据上。
  3.数据是短字符串的情况下，此方法效率还能提升5倍左右。

7.使用Map数据结构

方法解释：
  与对象key唯一去重方法一致，也是通过get、set数据判断元素是否重复，也可以使用has判断。

去重代码：

function distinct(arr) {
  const newArray = [];
  const newMap = new Map();
  for (let i = 0, len = arr.length; i < len; i++) {
    if (!newMap.get(arr[i])) { // newMap.has(arr[i])
      newMap.set(arr[i], 1);
      newArray.push(arr[i]);
    }
  }
  return newArray;
}
1234567891011

测试结果：
测试结果图
结果描述：
  利用Map数据结构不重复，处理效率还不错，目前效率最高的一种去重方案，不会打乱数据，不会因数据类型问题不好处理。目前只测试到1千万数据，2千万开始本机配置极易进入断点（同上）

方法效率分析：
  1.此方法时间也主要损耗在Map数据的存与取上面，不过效率比对象存取要高。

8.使用Set

方法解释：
  最简单的方法，通过new 一个 Set对象（只能存不同数据），放入重复数据的数组，再解构出来。

去重代码：

function distinct(arr) {
  return [...new Set(arr)];
}
123

测试结果：
测试结果图
结果描述：
  es6 提供的Set使用方法最简单，达到的效果也很喜人，目前效率与利用Map去重效率相当，不过考虑到Set兼容性，只能兼容到IE11，并且IE11不支持Array.from，以及解构。在不考虑IE兼容的情况下推荐使用Set。

方法效率分析：
  Set去重方法，全部由Set数据结构不重复特性处理，没有具体耗时地方，整个方法就是耗时处。

总结推荐

  1.首先在不考虑IE兼容的情况下推荐使用Set去重，可以看到每个去重方法具体效率都跟数据量、重复量相关。当然有的也跟数据类型相关，比如使用sort排序去重，2.如果是有序的数值，sort排序去重无疑是最快的，兼容性也很好。如果能确定需要3.去重的数据类型是简单字符串，推荐使用对象key唯一去重，经测试，在数据是短字符串的情况下，对象key唯一的去重方式在效率上还能提升5倍以上。如果数据类型比较复杂，而又不需要兼容IE10以下，4.推荐使用Map数据唯一去重。以上所有测试结果都能看到，重复量越大，处理速度越快，反而重复得越少，需要处理的时间就越长。选择去重方案也需要考虑当前项目中是否有使用babel工具，即使用了兼容性不好的Set、Map方法，babel也会打包为ES5语法。然而并不知道具体会打包成怎样去重，所以上诉方法都请视项目情况使用。

循环效率排行

  只论循环效率，不考虑内容，看看循环具体排行如何。

var arr = Array.from(new Array(10000000)); // 创建1千万条数据的数组

console.time('耗时')
// 循环体
console.timeEnd('耗时')

for         // 耗时: 6.65283203125ms - 7.085205078125ms
while         // 耗时：19.105712890625ms - 19.453857421875ms
do while    // 耗时：18.89697265625ms - 19.087890625ms
for of         // 耗时：102.4921875ms - 103.44921875ms
forEach()     // 耗时：103.834228515625ms - 104.614990234375ms
filter()    // 耗时：109.2978515625ms - 114.50390625ms
reduce()     // 耗时：113.99609375ms - 116.65625ms
map()         // 耗时：140.9560546875ms - 143.347900390625ms
for in         // 耗时：2094.56201171875ms - 2811.3017578125ms

12345678910111213141516

数组的方法还有很多就不一一列出来了
可以去此处参考数组对象方法
Array 对象

结语

  说实话，网上虽说js去重方法一大堆，但是不管怎么拼凑其实就那几种类型。也见过用递归方式去重的方法，不过效率实在太差，数据量稍微大一点就报错。以上所有数据与测试皆是本人实测，在不同电脑、系统、浏览器上会有明显差异。

看在花了大量时间测试的情况下，可以点个赞哦，如果错误欢迎指出。

Last modification：June 8, 2023
© From the Internet
If you think my article is useful to you, please feel free to appreciate