跟underscore一起学函数去重

发表于 | 分类于

引子

数组去重是一个老生常谈的话题，在面试中也经常会被问道。对于去重，有两种主流思想：

  1. 先排序，线性遍历后去重，时间复杂度O(n*log2n)；
  2. 使用哈希，空间换时间，时间复杂度O(n);

上一篇文章，我分析了underscore的函数是如何组织的，我们能够依照这种方法书写自己的函数库，这篇文章，来看看关于函数去重underscore是如何做的？

Underscore的去重

功能介绍

underscore的去重是指数组（Arrays）中uniq函数，其API如下：

uniq _.uniq(array, [isSorted], [iteratee]) 别名： unique
说明：返回 array去重后的副本, 使用 === 做相等测试. 如果您确定 array 已经排序, 那么给 isSorted 参数传递 true值, 此函数将运行的更快的算法. 如果要处理对象元素, 传参 iterator 来获取要对比的属性.

上述API主要想说明几点：

  1. 返回数组副本，不影响原数组
  2. 相等的标准是a===b,表明不仅要值相等，类型也需要相等
  3. 如果数组是排序的，去重运算效率更高
  4. uniq也可以比较对象，前提是需要指定比较的对象属性

我们简单使用以下_.uniq(array, [isSorted], [iteratee]),如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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数组。

1
2
3
4
5
6
7
8
9
10
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]

其中如果数组是排序的，去重运算效率更高，因为排序能够将相同的数排列在一起，方便前后比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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），小组组员情况如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
var array = [{
    name:"Tom",
    gender:"female"
},{
    name:"Lucy",
    gender:"female"
},{
    name:"Edward",
    gender:"male"
},{
    name:"Molly",
    gender:"female"
}]

我们修改上面的uniq：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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的实现（大家最熟悉的）：

1
2
var a = [1,1,2,3,4,4];
var res = [...new Set(a)];

再附上obj的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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函数源码及注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
  _.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;
};