论高性能数组去重
数组去重是一个老生常谈的问题，网络中也有对于去重的各种各样的解答方法。
为了测试解法性能，写了一个简易测试模板，用于测试各种去重方法的耗费时间。
测试模板
// distinct
let arr1 = Array.from(new Array(10000),(_,index)=>index)
let arr2 = Array.from(new Array(10000),(_,index)=>index * 2)
console.log('开始去重')
console.time('去重时间：')
let distinct = (arr1,arr2)=>{
// 去重函数
}
console.log(`去重后数组长度：${distinct(arr1,arr2).length}`)
console.timeEnd('去重时间：')
console.log('去重结束')
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
此处分别创建了两个长度为10W和5W的数组
通过distinct()方法合并两数组，并去除重复项
嵌套for循环
最基本的方法，外层循环遍历元素，内层循环检查是否存在重复项。
当存在重复项时，可通过push()或者splice()进行操作
let distinct = (arr1,arr2)=>{
let arr = [...arr1,...arr2]
for(let i=0,len=arr.length;i<len;i++) {
for(let j=i+1;j<len;j++) {
if(arr[i] === arr[j]) {
arr.splice(j,1)
// splice 会改变数组长度，因此将数组长度 len 和下标 j 减1
len--
j--
}
}
}
return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
这种方法内存使用率较高，效率较低。
Array.filter() + indexOf
利用ES6中的Array.filter()遍历数组，结合indexOf来排除重复项。
let distinct = (arr1,arr2)=>{
let arr = [...arr1,...arr2]
return arr.filter((item,index,array)=>array.indexOf(item) === index)
}
1
2
3
4
2
3
4
尽管代码简洁，但是实际性能却并不高。
for...of + includes()
嵌套for循环的升级版，外层采用for...of语句替换for循环，把内层循环改为includes()
先创建一个空数组，当includes()返回false的时候，就将该元素push到空数组中
类似的，还可以将includes()替换成indexOf()
let distinct = (arr1,arr2)=>{
let arr = [...arr1,...arr2]
let result = []
for(const i of arr) {
!result.includes(i) && result.push(i)
}
return result
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
此方法与filter()+indexOf()类似，因此耗时也相近
Array.sort()
利用sort()函数进行排序，然后比较相邻元素是否相等，从而排除重复项。
let distinct = (arr1,arr2)=>{
let arr = [...arr1,...arr2]
arr.sort()
let result = [arr[0]]
for(let i=1;i<arr.length;i++) {
arr[i] !== arr[i-1] && result.push(arr[i])
}
return result
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
由于此方法只做了一次排序和一次遍历，因此效率要比上述方法高
new Set()
ES6新增了Set这一数据结构，类似于数组，但Set成员具有唯一性
基于此特性，可以直接进行数组去重
let distinct = (arr1,arr2)=>{
let arr = [...arr1,...arr2]
return [...new Set(arr)]
}
1
2
3
4
2
3
4
15W的数据仅需要30ms，效率算得上很高了
for...of + Object
首先创建空对象，然后进行for循环遍历
利用__对象的属性不会重复__这一特性，校验数组元素是否重复
let distinct = (arr1,arr2)=>{
let arr = [...arr1,...arr2]
let obj = {}
let result = []
for(let i of arr) {
if(!obj[i]) {
result.push(i)
obj[i] = 1
}
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
此方法比Set()效率更高
