引子数组去重是一个老生常谈的话题,在面试中也经常会被问道。对于去重,有两种主流思想:先排序,线性遍历后去重,时间复杂度O(n*log2n);使用哈希,空间换时间,时间复杂度O(n);上一篇文章,我分析了underscore的函数是如何组织的,我们能够依照这种方法书写自己的函数库,这篇文章,来看看关于函数去重underscore是如何做的?Underscore的去重功能介绍underscore的去重是指数组(Arrays)中uniq函数,其API如下:uniq .uniq(array, [isSorted], [iteratee]) 别名: unique 说明:返回 array去重后的副本, 使用 === 做相等测试. 如果您确定 array 已经排序, 那么给 isSorted 参数传递 true值, 此函数将运行的更快的算法. 如果要处理对象元素, 传参 iterator 来获取要对比的属性.上述API主要想说明几点:返回数组副本,不影响原数组相等的标准是a===b,表明不仅要值相等,类型也需要相等如果数组是排序的,去重运算效率更高uniq也可以比较对象,前提是需要指定比较的对象属性我们简单使用以下.uniq(array, [isSorted], [iteratee]),如下: console.log(.uniq([1,4,2,2,3,3])); console.log(.uniq([1,2,2,2,3,3],true)); console.log(.uniq([{ name:1, gender:“male” },{ name:2, gender:“female” },{ name:2, gender:“male” },{ name:4, gender:“male” }],true,“gender”));结果如下:去重思想及实现underscore去重的核心思想:新建结果集数组res,遍历待去重数组,将每个遍历值在res数组中遍历检查,将不存在当前res中的遍历值压入res中,最后输出res数组。 function uniq(array){ var res = []; array.forEach(function(element) { if(res.indexOf(element)<0){ res.push(element); } }, this); return res; } console.log(uniq([1,4,2,2,3,3])); //[1,4,2,3]其中如果数组是排序的,去重运算效率更高,因为排序能够将相同的数排列在一起,方便前后比较。 function uniq(array, isSorted) { var res = []; var seen = null; array.forEach(function (element,index) { if (isSorted) { //当数组有序 if(!index || seen !== element) res.push(element); seen = element; } else { if (res.indexOf(element) < 0) { res.push(element); } } }, this); return res; } console.log(uniq([1,2,“2”,3,3,3,5],true)); //(5) [1, 2, “2”, 3, 5]对于对象的去重,我们知道{}==={}为false,所以使用===比较对象在实际场景中没有意义。 在这里我举个实际场景的例子:我要在小组中选择一名男生(male)和一名女生(female),小组组员情况如下:var array = [{ name:“Tom”, gender:“female”},{ name:“Lucy”, gender:“female”},{ name:“Edward”, gender:“male”},{ name:“Molly”, gender:“female”}] 我们修改上面的uniq: function uniq(array, isSorted, iteratee) { var res = []; var seen = []; array.forEach(function (element, index) { if (iteratee) { //判断iteratee是否存在,存在的话,取出真正要比较的属性 var computed = element[iteratee]; if (seen.indexOf(computed) < 0) { seen.push(computed); res.push(element); } } else if (isSorted) { //当数组有序 if (!index || seen !== element) res.push(element); seen = element; } else { if (res.indexOf(element) < 0) { res.push(element); } } }, this); return res; } console.log(uniq([{ name:“Tom”, gender:“female” },{ name:“Lucy”, gender:“female” },{ name:“Edward”, gender:“male” },{ name:“Molly”, gender:“female” }],true,“gender”)); 结果如下: underscore的uniq的实现,基本上使用的上述思想。在附录中我附上了源码和一些注释。关于去重的思考上述我分析了underscore的uniq函数实现,在这之前我也看过诸如《JavaScript去重的N种方法》…之类的文章,underscore中的uniq函数实现方法并不是最优解,至少从时间复杂度来讲不是最优。 那么为什么underscore不用Set对象来解决去重问题,使用indexof查找的时间复杂度是O(n),而hash查询是O(1)。 我个人认为Set是ES6中引的对象,underscore是为了考虑兼容性问题。 那为什么不用obj作为Set的替代方案呢? 这里我猜是underscore的设计者只想用自己内部实现的.indexOf函数。此处是我的猜测,大家如果有想法,欢迎大家留言! 下面我附上ES6的实现(大家最熟悉的):var a = [1,1,2,3,4,4];var res = […new Set(a)];再附上obj的实现: function uniq(array,iteratee){ var res = []; var obj = {}; array.forEach(function(element) { var computed = element; if(iteratee) computed = element[iteratee]; if(!obj.hasOwnProperty(computed)) obj[(typeof computed)+""+JSON.stringify(computed)] = element; }, this); for(var p in obj){ res.push(obj[p]); } return res; } uniq([1,“1”,2,3,4,4]);// (5) [1, “1”, 2, 3, 4]附录underscore的uniq函数源码及注释: .uniq = .unique = function(array, isSorted, iteratee, context) { if (array == null) return []; if (!.isBoolean(isSorted)) { //如果没有排序 context = iteratee; iteratee = isSorted; isSorted = false; } /** ** 此处.iteratee ** function (key){ * return function(obj){ * return obj[key]; * } ** } ** key就是这里的iteratee(对象的属性),这里使用了闭包 **/ if (iteratee != null) iteratee = .iteratee(iteratee, context); var result = [];//返回去重后的数组(副本) var seen = []; for (var i = 0, length = array.length; i < length; i++) { var value = array[i];//当前比较值 if (isSorted) { //如果i=0时,或者seen(上一个值)不等于当前值,放入去重数组中 if (!i || seen !== value) result.push(value); seen = value;//保存当前值,用于下一次比较 } else if (iteratee) { var computed = iteratee(value, i, array); if (.indexOf(seen, computed) < 0) { seen.push(computed); result.push(value); } } else if (.indexOf(result, value) < 0) { result.push(value); } } return result; };
...