摘要:昨天在微博上看到一篇文章,也寫數組去重,主要推崇的方法是將利用數組元素當作對象來去重。我在微博轉發了用對象去重不是個好辦法然后作者問什么才是推薦的方法。實例對象實例對象主要指通過構造函數類生成的對象。
本文同時發布于個人博客https://www.toobug.net/articl...
JavaScript的數組去重是一個老生常談的話題了。隨便搜一搜就能找到非常多不同版本的解法。
昨天在微博上看到一篇文章,也寫數組去重,主要推崇的方法是將利用數組元素當作對象key來去重。我在微博轉發了“用對象key去重不是個好辦法…”然后作者問什么才是推薦的方法。
細想一下,這樣一個看似簡單的需求,如果要做到完備,涉及的知識和需要注意的地方著實不少,于是誕生此文。
定義重復(相等)要去重,首先得定義,什么叫作“重復”,即具體到代碼而言,兩個數據在什么情況下可以算是相等的。這并不是一個很容易的問題。
對于原始值而言,我們很容易想到1和1是相等的,"1"和"1"也是相等的。那么,1和"1"是相等的么?
如果這個問題還好說,只要回答“是”或者“不是”即可。那么下面這些情況就沒那么容易了。
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...):
If Type(x) is Number, then
If x is NaN, return false.
If y is NaN, return false.
If x is the same Number value as y, return true.
If x is +0 and y is ?0, return true.
If x is ?0 and y is +0, return true.
Return false.
這意味著任何涉及到NaN的情況都不能簡單地使用比較運算來判定是否相等。比較科學的方法只能是使用isNaN():
var a = NaN; var 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; // false a1 === a2; // false a1 === a3; // 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等。
同時,還有可能出現一些只能黑人問號的結果,例如:
[] == ![]; //trueArray.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...),我們知道了indexOf()使用的是嚴格比較,也就是===。
Array.prototype.includes()再次強調:按照前文所述,===不能處理NaN的相等性判斷。
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/ecma26...)。
If Type(x) is different from Type(y), return false.
If Type(x) is Number, then
If x is NaN and y is NaN, return true.
If x is +0 and y is -0, return true.
If x is -0 and y is +0, return true.
If x is the same Number value as y, return true.
Return false.
Return SameValueNonNumber(x, y).
注意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雙重遍歷還有一個優化版本,但是原理和復雜度幾乎完全一樣:
function unique(arr) { var ret = []; var len = arr.length; for(var i=0; i這種方案沒什么大問題,用于去重的比較部分也是自己編寫實現(arr[i] === arr[j]),所以相等性可以自己針對上文說到的各種情況加以特殊處理。唯一比較受詬病的是使用了雙重循環,時間復雜度比較高,性能一般。
使用對象key來去重function unique(arr) { var ret = []; var len = arr.length; var tmp = {}; for(var i=0; i這種方法是利用了對象(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該方案也同時解決第三個問題。
而第二個問題,如果像上文所說,在允許對對象進行自定義的比較規則,也可以將對象序列化之后作為key來使用。這里為簡單起見,使用JSON.stringify()進行序列化。
function unique(arr) { var ret = []; var len = arr.length; var tmp = {}; var tmpKey; for(var i=0; iMap Key 可以看到,使用對象key來處理數組去重的問題,其實是一件比較麻煩的事情,處理不好很容易導致結果不正確。而這些問題的根本原因就是因為key在使用時有限制。
那么,能不能有一種key使用沒有限制的對象呢?答案是——真的有!那就是ES2015中的Map。
Map是一種新的數據類型,可以把它想象成key類型沒有限制的對象。此外,它的存取使用多帶帶的get()、set()接口。
var tmp = new Map(); tmp.set(1, 1); tmp.get(1); // 1 tmp.set("2", 2); tmp.get("2"); // 2 tmp.set(true, 3); tmp.get(true); // 3 tmp.set(undefined, 4); tmp.get(undefined); // 4 tmp.set(NaN, 5); tmp.get(NaN); // 5 var arr = [], obj = {}; tmp.set(arr, 6); tmp.get(arr); // 6 tmp.set(obj, 7); tmp.get(obj); // 7由于Map使用多帶帶的接口來存取數據,所以不用擔心key會和內置屬性重名(如上文提到的__proto__)。使用Map改寫一下我們的去重方法:
function unique(arr) { var ret = []; var len = arr.length; var tmp = new Map(); for(var i=0; iSet 既然都用到了ES2015,數組這件事情不能再簡單一點么?當然可以。
除了Map以外,ES2015還引入了一種叫作Set的數據類型。顧名思義,Set就是集合的意思,它不允許重復元素出現,這一點和數學中對集合的定義還是比較像的。
var s = new Set(); s.add(1); s.add("1"); s.add(null); s.add(undefined); s.add(NaN); s.add(true); s.add([]); s.add({});如果你重復添加同一個元素的話,Set中只會存在一個。包括NaN也是這樣。于是我們想到,這么好的特性,要是能和數組互相轉換,不就可以去重了嗎?
function unique(arr){ var set = new Set(arr); return Array.from(set); }我們討論了這么久的事情,居然兩行代碼搞定了,簡直不可思議。
然而,不要只顧著高興了。有一句話是這么說的“不要因為走得太遠而忘了為什么出發”。我們為什么要為數組去重呢?因為我們想得到不重復的元素列表。而既然已經有Set了,我們為什么還要舍近求遠,使用數組呢?是不是在需要去重的情況下,直接使用Set就解決問題了?這個問題值得思考。
小結最后,用一個測試用例總結一下文中出現的各種去重方法:
var arr = [1,1,"1","1",0,0,"0","0",undefined,undefined,null,null,NaN,NaN,{},{},[],[],/a/,/a/] console.log(unique(arr));測試中沒有定義對象的比較方法,因此默認情況下,對象不去重是正確的結果,去重是不正確的結果。
方法 結果 說明 indexOf#1 NaN被去掉 indexOf#2 NaN重復 includes 正確 雙重循環#1 NaN重復 雙重循環#2 NaN重復 對象#1 字符串和數字無法區分,對象、數組、正則表達式被去重 對象#2 對象、數組、正則表達式被去重 對象#3 對象、數組被去重,正則表達式被消失 JSON.stringify(/a/)結果為{},和空對象一樣 Map 正確 Set 正確 最后的最后:任何脫離場景談技術都是妄談,本文也一樣。去重這道題,沒有正確答案,請根據場景選擇合適的去重方法。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/88088.html
摘要:而數組元素去重是基于運算符的。而如果有迭代函數,則計算傳入迭代函數后的值,對值去重,調用方法,而該方法的核心就是調用方法,和我們上面說的方法一異曲同工。 Why underscore (覺得這部分眼熟的可以直接跳到下一段了...) 最近開始看 underscore.js 源碼,并將 underscore.js 源碼解讀 放在了我的 2016 計劃中。 閱讀一些著名框架類庫的源碼,就好像...
摘要:同行這么做使用實現圓形進度條前端掘金在開發微信小程序的時候,遇到圓形進度條的需求。實現也談數組去重前端掘金的數組去重是一個老生常談的話題了。百度前端技術學院自定義前端掘金一標簽概念元素表示用戶界面中項目的標題。 閑話圖片上傳 - 掘金作者:孫輝,美團金融前端團隊成員。15年畢業加入美團,相信技術,更相信技術只是大千世界里知識的一種,個人博客: https://sunyuhui.com ...
摘要:同行這么做使用實現圓形進度條前端掘金在開發微信小程序的時候,遇到圓形進度條的需求。實現也談數組去重前端掘金的數組去重是一個老生常談的話題了。百度前端技術學院自定義前端掘金一標簽概念元素表示用戶界面中項目的標題。 閑話圖片上傳 - 掘金作者:孫輝,美團金融前端團隊成員。15年畢業加入美團,相信技術,更相信技術只是大千世界里知識的一種,個人博客: https://sunyuhui.com ...
摘要:返回值是一個新數組,思路也很清楚,對于已經排好序的數組,用后一個和前一個相比,不一樣就到中,對于沒有排好序的數組,要用到函數對是否包含元素進行判斷。 前面已經介紹過了,關于 _ 在內部是一個什么樣的情況,其實就是定義了一個名字叫做 _ 的函數,函數本身就是對象呀,就在 _ 上擴展了 100 多種方法。 showImg(https://segmentfault.com/img/remot...
摘要:看完部分的源碼,首先迫不及待想跟大家分享的正是本文主題數組亂序。這是一道經典的前端面試題,給你一個數組,將其打亂,返回新的數組,即為數組亂序,也稱為洗牌問題。關于數組亂序,正確的解法應該是,復雜度。 前言 終于可以開始 Collection Functions 部分了。 可能有的童鞋是第一次看樓主的系列文章,這里再做下簡單的介紹。樓主在閱讀 underscore.js 源碼的時候,學到...
閱讀 2511·2021-09-26 10:18
閱讀 3386·2021-09-22 10:02
閱讀 3183·2019-08-30 15:44
閱讀 3326·2019-08-30 15:44
閱讀 1831·2019-08-29 15:25
閱讀 2572·2019-08-26 14:04
閱讀 2035·2019-08-26 12:15
閱讀 2437·2019-08-26 11:43