资讯专栏INFORMATION COLUMN

跟underscore一起学数组去重

flybywind / 2540人阅读

摘要:引子数组去重是一个老生常谈的话题,在面试中也经常会被问道。其中如果数组是排序的,去重运算效率更高,因为排序能够将相同的数排列在一起,方便前后比较。当数组有序对于对象的去重,我们知道为,所以使用比较对象在实际场景中没有意义。

引子

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

先排序,线性遍历后去重,时间复杂度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;
  };

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/102527.html

相关文章

  • JavaScript专题系列20篇正式完结!

    摘要:写在前面专题系列是我写的第二个系列,第一个系列是深入系列。专题系列自月日发布第一篇文章,到月日发布最后一篇,感谢各位朋友的收藏点赞,鼓励指正。 写在前面 JavaScript 专题系列是我写的第二个系列,第一个系列是 JavaScript 深入系列。 JavaScript 专题系列共计 20 篇,主要研究日常开发中一些功能点的实现,比如防抖、节流、去重、类型判断、拷贝、最值、扁平、柯里...

    sixleaves 评论0 收藏0
  • 也谈面试必备问题之 JavaScript 数组去重

    摘要:而数组元素去重是基于运算符的。而如果有迭代函数,则计算传入迭代函数后的值,对值去重,调用方法,而该方法的核心就是调用方法,和我们上面说的方法一异曲同工。 Why underscore (觉得这部分眼熟的可以直接跳到下一段了...) 最近开始看 underscore.js 源码,并将 underscore.js 源码解读 放在了我的 2016 计划中。 阅读一些著名框架类库的源码,就好像...

    Coly 评论0 收藏0
  • JavaScript专题系列文章

    摘要:专题系列共计篇,主要研究日常开发中一些功能点的实现,比如防抖节流去重类型判断拷贝最值扁平柯里递归乱序排序等,特点是研究专题之函数组合专题系列第十六篇,讲解函数组合,并且使用柯里化和函数组合实现模式需求我们需要写一个函数,输入,返回。 JavaScript 专题之从零实现 jQuery 的 extend JavaScritp 专题系列第七篇,讲解如何从零实现一个 jQuery 的 ext...

    Maxiye 评论0 收藏0
  • underscore一起如何写函数库

    摘要:支持两种不同风格的函数调用在中我们可以使用以下两种方式调用函数式的调用对象式调用在中,它们返回的结果都是相同的。 原文:https://zhehuaxuan.github.io/... 作者:zhehuaxuan 目的 Underscore 是一个 JavaScript 工具库,它提供了一整套函数式编程的实用功能,但是没有扩展任何 JavaScript 内置对象。 本文主要梳理und...

    ephererid 评论0 收藏0
  • JavaScript 数组展开以及 underscore 重要的内部方法 flatten 详解

    摘要:今天要讲的是数组展开以及和数组展开息息相关的一个重要的内部方法。也是个布尔值,当为并且也为时,能过滤参数元素中的非数组元素。首先并不需要对数组深度展开,其次传入的是数组,对于非数组元素可以直接忽略。 Why underscore (觉得这一段眼熟的童鞋可以直接跳到正文了...) 最近开始看 underscore.js 源码,并将 underscore.js 源码解读 放在了我的 201...

    binaryTree 评论0 收藏0

发表评论

0条评论

flybywind

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<