JavaScript数组去重由慢到快由繁到简(优化篇)
JavaScript数组去重由慢到快由繁到简(优化篇)
发布时间:2016-12-30 来源:查字典编辑
摘要:在进行数组操作时往往会遇到去掉重复项的问题,下面简单介绍下数组去重的方法。indexOf去重Array.prototype.unique1=...

在进行数组操作时往往会遇到去掉重复项的问题,下面简单介绍下数组去重的方法。

indexOf去重

Array.prototype.unique1 = function() { var arr = []; for (var i = 0; i < this.length; i++) { var item = this[i]; if (arr.indexOf(item) === -1) { arr.push(item); } } return arr; } [1,2,3,'4',3,4,3,1,'34',2].unique1(); //[1, 2, 3, "4", 4, "34"]

不过,在 IE6-8 下,数组的 indexOf 方法还不存在(虽然这已经算有点古老的话题了O(∩_∩)O~),但是,程序员就要写一个indexOf方法:

var indexOf = [].indexOf ? function(arr, item) { return arr.indexOf(item); } : function indexOf(arr, item) { for (var i = 0; i < arr.length; i++) { if (arr[i] === item) { return i; } } return -1; } Array.prototype.unique2 = function() { var arr = []; for (var i = 0; i < this.length; i++) { var item = this[i]; if (arr.indexOf(item) === -1) { arr.push(item); } } return arr; } [1,2,3,'4',3,4,3,1,'34',2].unique2(); //[1, 2, 3, "4", 4, "34"]

indexOf还可以以这样的去重思路:

Array.prototype.unique3 = function(){ var arr = [this[0]]; for(var i = 1; i < this.length; i++) { if (this.indexOf(this[i]) == i){ arr.push(this[i]); } } return arr; } [1,2,3,'4',3,4,3,1,'34',2].unique3(); //[1, 2, 3, "4", 4, "34"]

hash去重

以上indexOf正确性没问题,但性能上,两重循环会降低性能。那我们就用hash。

Array.prototype.unique4 = function() { var arr = []; var hash = {}; for (var i = 0; i < this.length; i++) { var item = this[i]; var key = typeof(item) + item if (hash[key] !== 1) { arr.push(item); hash[key] = 1; } } return arr; } [1,2,3,'4',3,4,3,1,'34',2].unique4(); //[1, 2, 3, "4", 4, "34"]

核心是构建了一个 hash 对象来替代 indexOf。空间换时间。注意在 JavaScript 里,对象的键值只能是字符串(当然,ES6提供了Map数据结构。它类似于对象,也是键值对的集合,但是“键”的范围不限于字符串,各种类型的值(包括对象)都可以当作键。也就是说,Object结构提供了“字符串—值”的对应,Map结构提供了“值—值”的对应,是一种更完善的Hash结构现。),因此需要var key = typeof(item) + item 来区分数值 1 和字符串 '1' 等情况。

那如果你想要'4' 和 4 被认为是相同的话(其他方法同理)

Array.prototype.unique5 = function(){ var arr=[]; var hash={}; for(var i=0,len=this.length;i<len;i++){ if(!hash[this[i]]){ arr.push(this[i]); hash[this[i]]=true; } } return arr; } [1,2,3,'4',3,4,3,1,'34',2].unique5(); //[1, 2, 3, "4", "34"]

排序后去重

Array.prototype.unique6 = function(){ this.sort(); var arr = [this[0]]; for(var i = 1; i < this.length; i++){ if( this[i] !== arr[arr.length-1]){ arr.push(this[i]); } } return arr; } [1,2,3,'4',3,4,3,1,'34',2].unique6(); //[1, 2, 3, "34", "4", 4]

先把数组排序,然后比较相邻的两个值,排序的时候用的JS原生的sort方法,所以非常快。而这个方法的缺陷只有一点,比较字符时按照字符编码的顺序进行排序。所以会看到10排在2前面这种情况。不过在去重中不影响。不过,解决sort的这个问题,是sort方法接受一个参数,这个参数是一个方法:

function compare(value1,value2) { if (value1 < value2) { return -1; } else if (value1 > value2) { return 1; } else { return 0; } } [1,2,5,2,10,3,20].sort(compare); //[1, 2, 2, 3, 5, 10, 20]

Set去重

ES6提供了新的数据结构Set。它类似于数组,但是成员的值都是唯一的,没有重复的值。现在浏览器正在全面支持,服务端的node也已经支持。

Array.prototype.unique7 = function(){ return Array.from(new Set(this)); } [1,2,3,'4',3,4,3,1,'34',2].unique7(); //[1, 2, 3, "4", 4, "34"]

方法库

推荐一个方法库Underscore.js,在node或浏览器js中都很受欢迎。

const _ = require('underscore'); _.uniq([1, 2, 1, 3, 1, 4]); //[1, 2, 3, 4]

测试时间

以上方法均可以用一个简单的方法去测试一下所耗费的时间,然后对各个方法做比较择优:

console.time("test"); [1,2,3,'4',3,4,3,1,'34',2].unique7(); console.timeEnd("test"); ==> VM314:3 test: 0.378ms

让数据变得大一点,就随机创建100万个数:

var arr = []; var num = 0; for(var i = 0; i < 1000000; i++){ num = Math.floor(Math.random()*100); arr.push(num); } console.time("test"); arr.unique7(); console.timeEnd("test");

以上所述是小编给大家介绍的JavaScript数组去重由慢到快由繁到简,希望对大家有所帮助,如果大家有任何疑问请给我们留言,小编会及时回复大家的。在此也非常感谢大家对查字典教程网的支持!

推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关阅读
网友关注
最新Javascript教程学习
热门Javascript教程学习
编程开发子分类