首页 > 编程语言 > 详细

数组的去重-----------------------来自大牛的讲解

时间:2017-02-24 12:16:41      阅读:181      评论:0      收藏:0      [点我收藏+]

NaN

初看NaN时,很容易把它当成和null、undefined一样的独立数据类型。但其实,它是数字类型。

//number
console.log(typeof  NaN);

根据规范,比较运算中只要有一个值为NaN,则比较结果为false,所以会有下面这些看起来略蛋疼的结论:

//全部是false
0<NaN
0>NaN
0==NaN
0===NaN

以最后一个表达式0 === NaN为例,在规范中有明确规定(http://www.ecma-international.org/ecma-262/6.0/#sec-strict-equality-comparison):

这意味着任何涉及到NaN的情况都不能简单地使用比较运算来判定是否相等。比较科学的方法只能是使用isNaN():

var a=NaN;
bar b=NaN;
//true
console.log(isNaN(a)  &&  isNaN(b));

原始值和包装对象

看完NaN是不是头都大了。好了,我们来轻松一下,看一看原始值和包装对象这一对冤家。

如果你研究过‘a‘.trim()这样的代码的话,不知道是否产生过这样的疑问:‘a‘明明是一个原始值(字符串),它为什么可以直接调用.trim()方法呢?当然,很可能你已经知道答案:因为JS在执行这样的代码的时候会对原始值做一次包装,让‘a‘变成一个字符串对象,然后执行这个对象的方法,执行完之后再把这个包装对象脱掉。可以用下面的代码来理解:

//‘a‘.trim();
var tmp=new String(‘a‘);
tmp.trim();

这段代码只是辅助我们理解的。但包装对象这个概念在JS中却是真实存在的。

var a=new String(‘a‘);
var b=‘b‘;

a即是一个包装对象,它和b一样,代表一个字符串。它们都可以使用字符串的各种方法(比如trim()),也可以参与字符串运算(+号连接等)。

但他们有一个关键的区别:类型不同!

typeof a;//object
typeof b;//string

在做字符串比较的时候,类型的不同会导致结果有一些出乎意料:

var a1=‘a‘;
var a2=new String(‘a‘);
var a3=new String(‘a‘);
a1==a2;//true
a1==a3;//true
a2==a3;//true

a1===a3;//false
a1===a2;//false
a2===a3;//false

同样是表示字符串a的变量,在使用严格比较时竟然不是相等的,在直觉上这是一件比较难接受的事情,在各种开发场景下,也非常容易忽略这些细节。 

对象和对象

在涉及比较的时候,还会碰到对象。具体而言,大致可以分为三种情况:纯对象、实例对象、其它类型的对象。

纯对象

纯对象(plain object)具体指什么并不是非常明确,为减少不必要的争议,下文中使用纯对象指代由字面量生成的、成员中不含函数和日期、正则表达式等类型的对象。 

如果直接拿两个对象进行比较,不管是==还是===,毫无疑问都是不相等的。但是在实际使用时,这样的规则是否一定满足我们的需求?举个例子,我们的应用中有两个配置项:

//原来有两个属性
//var prop1=1;
//var prop2=2;
//重构代码时两个属性被放到同一个对象中
var    config={
     prop1:1,
     prop2:2

};

假设在某些场景下,我们需要比较两次运行的配置项是否相同。在重构前,我们分别比较两次运行的prop1和prop2即可。而在重构后,我们可能需要比较config对象所代表的配置项是否一致。在这样的场景下,直接用==或者===来比较对象,得到的并不是我们期望的结果。

在这样的场景下,我们可能需要自定义一些方法来处理对象的比较。常见的可能是通过JSON.stringify()对对象进行序列化之后再比较字符串,当然这个过程并非完全可靠,只是一个思路。 

如果你觉得这个场景是无中生有的话,可以再回想一下断言库,同样是基于对象成员,判断结果是否和预期相符。

实例对象

实例对象主要指通过构造函数(类)生成的对象。这样的对象和纯对象一样,直接比较都是不等的,但也会碰到需要判断是否是同一对象的情况。一般而言,因为这种对象有比较复杂的内部结构(甚至有一部分数据在原型上),无法直接从外部比较是否相等。比较靠谱的判断方法是由构造函数(类)来提供静态方法或者实例方法来判断是否相等。

var a=Klass();
var b=Klass();
Klass.isEqual(a,b);

其它对象

其它对象主要指数组、日期、正则表达式等这类在Object基础上派生出来的对象。这类对象各有各的特殊性,一般需要根据场景来构造判断方法,决定两个对象是否相等。 

比如,日期对象,可能需要通过Date.prototype.getTime()方法获取时间戳来判断是否表示同一时刻。正则表达式可能需要通过toString()方法获取到原始字面量来判断是否是相同的正则表达式。

==和===

在一些文章中,看到某一些数组去重的方法,在判断元素是否相等时,使用的是==比较运算符。众所周知,这个运算符在比较前会先查看元素类型,当类型不一致时会做隐式类型转换。这其实是一种非常不严谨的做法。因为无法区分在做隐匿类型转换后值一样的元素,例如0、‘‘、false、null、undefined等。

同时,还有可能出现一些只能黑人问号的结果,例如:

[]==![];//true

Array.prototype.indexOf()

在一些版本的去重中,用到了Array.prototype.indexOf()方法:

function unique(arr){
  return arr.filter(function(item,index){
    //indexof返回第一个索引值
    //如果当前索引不是第一个索引,说明是重复值
    return  arr.indexof(item)===index;
})
}
function unique(arr){
   var  ret=[];
   arr.forEach(function(item){
       if(ret.indexof(item)===-1){
           ret.push(item);
       }
    });
    return ret;
}

既然==和===在元素相等的比较中是有巨大差别的,那么indexOf的情况又如何呢?大部分的文章都没有提及这点,于是只好求助规范。通过规范(http://www.ecma-international.org/ecma-262/6.0/#sec-array.prototype.indexof),我们知道了indexOf()使用的是严格比较,也就是===。

再次强调:按照前文所述,===不能处理NaN的相等性判断。 

Array.prototype.includes()

Array.prototype.includes()是ES2016中新增的方法,用于判断数组中是否包含某个元素,所以上面使用indexOf()方法的第二个版本可以改写成如下版本:

function unique(arr){
     var ret=[];
     arr.forEach(function(item){
           if(!ret.includes(item)){
                 ret.push(item);
           }
     })
     return ret;
}

那么,你猜猜,includes()又是用什么方法来比较的呢?如果想当然的话,会觉得肯定跟indexOf()一样喽。但是,程序员的世界里最怕想当然。翻一翻规范,发现它其实是使用的另一种比较方法,叫作“SameValueZero”比较(https://tc39.github.io/ecma262/2016/#sec-samevaluezero)。

注意2.a,如果x和y都是NaN,则返回true!也就是includes()是可以正确判断是否包含了NaN的。我们写一段代码验证一下:

var arr=[1,2,NaN];
arr.indexof(NaN);//-1
arr.includes(NaN);//true

可以看到indexOf()和includes()对待NaN的行为是完全不一样的。

一些方案

从上面的一大段文字中,我们可以看到,要判断两个元素是否相等(重复)并不是一件简单的事情。在了解了这个背景后,我们来看一些前面没有涉及到的去重方案。

遍历

双重遍历是最容易想到的去重方案:

function unique(arr){
        var ret=[];
        var len=arr.length;
        var isRepeat;
        for(var i=0;i<len;i++){
            isRepeat=false;
            for(var j=i+1;j<len;j++){
                if(arr[i]===arr[j]){
                    isRepeat=true;
                    break;
                }
            }
            if(!isRepeat){
                ret.push(arr[i]);
            }
        }
        return ret;
    }

双重遍历还有一个优化版本,但是原理和复杂度几乎完全一样:

function unique(arr){
        var ret=[];
        var len=arr.length;
        for(var i=0;i<len;i++){
            for(var j=i+1;j<len;j++){
                if(arr[i]===arr[j]){
                    j=++i;
                }
            }
            ret.push(arr[i]);
        }
        return ret;
    }

这种方案没什么大问题,用于去重的比较部分也是自己编写实现(arr[i] === arr[j]),所以相等性可以自己针对上文说到的各种情况加以特殊处理。唯一比较受诟病的是使用了双重循环,时间复杂度比较高,性能一般。

使用对象key来去重

function unique(arr){
        var ret=[];
        var len=arr.length;
        var tmp={};
        for(var i=0;i<len;i++){
            if(!tmp[arr[i]]){
                tmp[arr[i]]=1;
                ret.push(arr[i]);
            }
        }
        return ret;
    }

这种方法是利用了对象(tmp)的key不可以重复的特性来进行去重。但由于对象key只能为字符串,因此这种去重方法有许多局限性:

无法区分隐式类型转换成字符串后一样的值,比如1和‘1‘

无法处理复杂数据类型,比如对象(因为对象作为key会变成[object Object])

特殊数据,比如‘__proto__‘会挂掉,因为tmp对象的__proto__属性无法被重写

对于第一点,有人提出可以为对象的key增加一个类型,或者将类型放到对象的value中来解决:

    function unique(arr){
        var ret=[];
        var len=arr.length;
        var tmp={};
        var tmpKey;
        for(var i=0;i<len;i++){
            tmpKey=typeof arr[i] + arr[i];
            if(!tmp[tmpKey]){
                tmp[tmpKey]=1;
                ret.push(arr[i]);
            }
        }
        return ret;
    }

该方案也同时解决第三个问题。

而第二个问题,如果像上文所说,在允许对对象进行自定义的比较规则,也可以将对象序列化之后作为key来使用。这里为简单起见,使用JSON.stringify()进行序列化。

function unique(arr){
        var ret=[];
        var len=arr.length;
        var tmp={};
        var tmpKey;
        for(var i=0;i<len;i++){
            tmpKey=typeof arr[i] + JSON.stringify(arr[i]);
            if(!tmp[tmpKey]){
                tmp[tmpKey]=1;
                ret.push(arr[i]);
            }
        }
        return ret;
    }

Map Key

可以看到,使用对象key来处理数组去重的问题,其实是一件比较麻烦的事情,处理不好很容易导致结果不正确。而这些问题的根本原因就是因为key在使用时有限制。

那么,能不能有一种key使用没有限制的对象呢?答案是——真的有!那就是ES2015中的Map。

Map是一种新的数据类型,可以把它想象成key类型没有限制的对象。此外,它的存取使用单独的get()、set()接口。

 

数组的去重-----------------------来自大牛的讲解

原文:http://www.cnblogs.com/luxiaoxiao/p/6437864.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!