数组去重方法对比

技术博客 (196) 2024-01-02 18:01:01

数组去重方法对比

  • 方法一 双重for循环
  • 方法二 双重for循环2
  • 方法三 Array.filter()+indexOf的方法
  • 方法四 Array.map()+Array.filter()
  • 方法五 for..of+includes()
  • 方法六 Array.sort()+for循环
  • 方法七 new Set()
  • 方法八 for循环+Object
  • 总结

模拟了以下两个数组,一个数组长度100000 另一个长度为50000
下面的方法都是针对这两个数组来做的测试
数组长度越长 速度差异会越大

let arr1 = Array.from(new Array(100000), (x, index) => { 
   
   return index;
});
let arr2 = Array.from(new Array(50000), (x, index) => { 
   
    return index + index;
});

方法一 双重for循环

//计算耗时
let start = new Date().getTime();//开始时间
console.log("双重for循环 开始数组去重");
//去重方法
function distinct(a,b){ 
   
	let arr = a.concat(b);//先将两个数组组成一个数组 然后再去重
	let len = arr.length;
	for(let i=0;i<len ;i++){ 
   
		for(let j=i+1;j<len ;j++){ 
   
			if(arr[i]===arr[j]){ 
   
				arr.splice(i,1);
				//splice会改变原数组的长度 此处len和下标j必须减一
				len--;
				j--;
			}
		}
	}
	return arr;
}
console.log('去重后的长度', distinct(arr1, arr2).length); 
let end = new Date().getTime();//结束时间
 console.log("结束数组去重 耗时:", end - start);

打印结果如下

双重for循环 开始数组去重
去重后的长度 100000
结束数组去重 耗时: 22349

两个数组合并之后再for循环嵌套 逻辑好理解 但是 耗时太久 而且会导致页面假死状态 无法操作其他逻辑 性能差 体验差 不推荐此方法

方法二 双重for循环2

function distinct(a,b){ 
   
	for(let i=0;i<a.length ;i++){ 
   
		for(let j=0;j<b.length ;j++){ 
   
			if(a[i]===b[j]){ 
   
				b.splice(j,1);
				j--;		
			}
		}
	}
	let arr = a.concat(b);//先去重在重组
	return arr;
}

打印如下,

结束数组去重 耗时: 6890

时间少很多 但是有限制,必须原数组中没有重复的才能用这个方法 不能完全去重 性能也是比较差 不推荐使用

方法三 Array.filter()+indexOf的方法

直接上代码

function distinct(a,b){ 
   
	let arr = a.concat(b);
	return arr.filter((item,index)=>{ 
   
		//遍历整个数组 返回indexOF之后的下标和实际下标一致的数据
		//(如果有重复的 indexOf返回的是找到的第一个值的下标 和实际的index下标不会相等)
		return arr.indexOf(item)===index;
	})
}

打印如下

结束数组去重 耗时: 9593

filter() 方法会创建一个新的数组,新数组中的元素是通过检查指定数组中符合条件的所有元素。
filter() 判断计算条件 返回的还是之前的数组元素 filter不会改变原素组
这个方法会全部遍历一遍 去重也比较彻底 但是耗时还是比较久

方法四 Array.map()+Array.filter()

function distinct(a, b) { 
   
	let arr = a.concat(b);
	let newArr= arr.map((item, index) => { 
   
		if(arr.indexOf(item) === index){ 
   //判断条件
			return item;	
		}
	});
	//newArr的长度还是两个数组的长度之和 只是不符合条件的值变成了undefined
	return newArr.filter((itemx,idx)=>{ 
   
		return itemx!==undefined;	//过滤掉undefined的值
	});
}

执行打印如下

结束数组去重 耗时: 9658

map() 方法返回一个新数组,数组中的元素为原始数组元素调用函数处理后的值。
map() 方法按照原始数组元素顺序依次处理元素。 map也不改变原数组
但是上述代码执行map之后 数组长度还是150000 只是重复值的地方的值变成了undefined,依旧占了数组的位置 还需要再调一次filter去掉数组里面的undefined 逻辑相对比较复杂 还不如直接调一次filter的方法 耗时也比较久

方法五 for…of+includes()

function distinct(a,b){ 
   
	var arr = a.concat(b);
	let resultArr = [];
	for(let i of arr){ 
   
		if(!resultArr.includes(arr[i])){ 
   //不包含在新数组里面的话 就加进入
			resultArr.push(arr[i]);
		}
	}
}

打印如下

结束数组去重 耗时: 9547

includes() 方法用来判断一个数组是否包含一个指定的值,如果是返回 true,否则false。
这种方法和filter()+indexOf()的逻辑是一样的 只是将filter的内部逻辑用for循环显示出来了 indexOf和includes同样都是用来条件判断的 耗时也差不多

方法六 Array.sort()+for循环

function distinct(a,b){ 
   
	let arr = a.concat(b);
	arr = arr.sort();
	let result = [arr[0]];
	for(let i=1;i<arr.length;i++){ 
   
		if(arr[i]!=arr[i-1]){ 
   
			result.push(arr[i]);
		}
	}
	return result;
}

打印耗时:

结束数组去重 耗时: 18

惊呆了 竟然只用了18ms 比上面的快太多了 逻辑也比较简单
Array.sort() 可以传参也可以不传 如果没有使用参数,将按字母顺序对数组中的元素进行排序,说得更精确点,是按照字符编码的顺序进行排序。要实现这一点,如有必要 首先应把数组的元素都转换成字符串,然后再进行比较
排序之后就只需要比较当前元素和前一个元素是否一样就行了

方法七 new Set()

function distinct(a,b){ 
   
	var arr = a.concat(b);
	return Array.from(new Set([...a,...b]));
}

打印耗时如下:

结束数组去重 耗时: 17

这个方法也是非常的快,逻辑也就一两行 非常的简单 Set是ES6提供的新的数据结构
Set 对象允许你存储任何类型的唯一值,无论是原始值或者是对象引用。
根据Set对象 元素的唯一性 就能直接处理数组去重

方法八 for循环+Object

function distinct(a,b){ 
   
	let arr = a.concat(b);
	let obj = { 
   };
	let result = [];
	for(let i of arr){ 
   
		if(!obj[i]){ 
   //对象属性唯一
			result.push(arr[i]);
			obj[i] = 1;
		}
	}
	return result;
}

打印耗时如下:

结束数组去重 耗时: 11

测试的几种方法中耗时最短的,数组长度越长 效果越明显
首先创建一个空对象,然后用 for 循环遍历 不重复的加入对象里面
利用对象的属性不会重复这一特性,校验数组元素是否重复

总结

前面几种方法耗时太久不推荐,后三种耗时差不多,那究竟那种方法耗时最优呢,我们将数组改造下
(前面几种方法就不做数组长度加长的测试了 会直接卡死动不了。。。。。要等很久很久。。。)

let arr1 = Array.from(new Array(1000000), (x, index) => { 
   
   return index;
});
let arr2 = Array.from(new Array(500000), (x, index) => { 
   
    return index + index;
});

两个数组的长度分别*10倍,数组长度变成100万和50万 然后执行后三种方法,可以得到大概这样的打印

Array.sort()+for循环 耗时:127
new Set()  耗时: 159
for循环+Object  耗时: 71

继续加大数组长度*100倍, 数组长度变成1000万和500万 然后执行后三种方法,可以得到大概这样的打印

Array.sort()+for循环 耗时:1196
new Set()  耗时: 2834
for循环+Object  耗时: 714

千万级的数据 处理时间也不到1s Object的这个方法的确是最优的
综上所有的方法 推荐使用最后这三种方法来实现数组去重的目的,最推荐Object的方法 速度会快很多

想法是很久以前在一篇面试文中见过的,具体代码整理是自己整理的
若哪里有不妥 欢迎指正

THE END

发表回复