摘要： 高效使用Set仁热！
- 作者：前端小智
- 原文：如何使用 Set 來提高代碼的性能
Fundebug經(jīng)授權(quán)轉(zhuǎn)載耙厚，版權(quán)歸原作者所有。
為了保證的可讀性仰楚，本文采用意譯而非直譯隆判。
我確信有很多開發(fā)人員堅(jiān)持使用基本的全局對象：數(shù)字犬庇，字符串，對象侨嘀，數(shù)組和布爾值臭挽。對于許多用例，這些都是需要的咬腕。 但是如果想讓你的代碼盡可能快速和可擴(kuò)展欢峰，那么這些基本類型并不總是足夠好。
在本文中涨共，我們將討論JS 中Set對象如何讓代碼更快—?特別擴(kuò)展性方便纽帖。 Array 和Set工作方式存在大量的交叉。但是使用Set會比Array在代碼運(yùn)行速度更有優(yōu)勢举反。
Set 有何不同
最根本的區(qū)別是數(shù)組是一個索引集合懊直，這說明數(shù)組中的數(shù)據(jù)值按索引排序。
const arr = [A, B, C, D];
console.log(arr.indexOf(A)); // Result: 0
console.log(arr.indexOf(C)); // Result: 2
相比之下火鼻，set是一個鍵的集合室囊。set不使用索引，而是使用鍵對數(shù)據(jù)排序魁索。set 中的元素按插入順序是可迭代的融撞，它不能包含任何重復(fù)的數(shù)據(jù)。換句話說粗蔚，set中的每一項(xiàng)都必須是惟一的尝偎。
主要的好處是什么
set 相對于數(shù)組有幾個優(yōu)勢，特別是在運(yùn)行時間方面：
-
查看元素：使用
indexOf()或includes()檢查數(shù)組中的項(xiàng)是否存在是比較慢的支鸡。 -
刪除元素:在
Set中，可以根據(jù)每項(xiàng)的的value來刪除該項(xiàng)趁窃。在數(shù)組中牧挣，等價的方法是使用基于元素的索引的splice()。與前一點(diǎn)一樣醒陆，依賴于索引的速度很慢瀑构。 -
保存 NaN：不能使用
indexOf()或includes()來查找值NaN，而Set可以保存此值刨摩。 -
刪除重復(fù)項(xiàng):
Set對象只存儲惟一的值,如果不想有重復(fù)項(xiàng)存在寺晌，相對于數(shù)組的一個顯著優(yōu)勢，因?yàn)閿?shù)組需要額外的代碼來處理重復(fù)澡刹。
時間復(fù)雜度呻征？
數(shù)組用來搜索元素的方法時間復(fù)雜度為0(N)。換句話說罢浇，運(yùn)行時間的增長速度與數(shù)據(jù)大小的增長速度相同陆赋。
相比之下沐祷，Set用于搜索、刪除和插入元素的方法的時間復(fù)雜度都只有O(1)攒岛，這意味著數(shù)據(jù)的大小實(shí)際上與這些方法的運(yùn)行時間無關(guān)赖临。
Set 究竟有多快？
雖然運(yùn)行時間可能會有很大差異灾锯，具體取決于所使用的系統(tǒng)兢榨，所提供數(shù)據(jù)的大小以及其他變量，但我希望我的測試結(jié)果能夠讓你真實(shí)地了解Set的速度顺饮。 我將分享三個簡單的測試和我得到的結(jié)果吵聪。
準(zhǔn)備測試
在運(yùn)行任何測試之前，創(chuàng)建一個數(shù)組和一個 Set领突，每個數(shù)組和 Set 都有100萬個元素暖璧。為了簡單起見，我從0開始君旦，一直數(shù)到999999澎办。
let arr = [], set = new Set(), n = 1000000;
for (let i = 0; i < n; i++) {
arr.push(i);
set.add(i);
}
測試1：查找元素
我們搜索數(shù)字123123
let result;
console.time('Array');
result = arr.indexOf(123123) !== -1;
console.timeEnd('Array');
console.time('Set');
result = set.has(123123);
console.timeEnd('Set');
- Array: 0.173ms
- Set: 0.023ms
Set 速度快了7.54倍
代碼部署后可能存在的BUG沒法實(shí)時知道，事后為了解決這些BUG金砍，花了大量的時間進(jìn)行l(wèi)og 調(diào)試局蚀，這邊順便給大家推薦一個好用的BUG監(jiān)控工具 Fundebug。
測試2：添加元素
console.time('Array');
arr.push(n);
console.timeEnd('Array');
console.time('Set');
set.add(n);
console.timeEnd('Set');
- Array: 0.018ms
- Set: 0.003ms
Set 速度快了6.73倍
測試3：刪除元素
最后恕稠，刪除一個元素琅绅，由于數(shù)組沒有內(nèi)置方法，首先先創(chuàng)建一個輔助函數(shù)：
const deleteFromArr = (arr, item) => {
let index = arr.indexOf(item);
return index !== -1 && arr.splice(index, 1);
};
這是測試的代碼：
console.time('Array');
deleteFromArr(arr, n);
console.timeEnd('Array');
console.time('Set');
set.delete(n);
console.timeEnd('Set');
- Array: 1.122ms
- Set: 0.015ms
Set 速度快了74.13倍
總的來說鹅巍，我們可以看到千扶，使用Set 極大地改善運(yùn)行時間。再來看看一些Set有用的實(shí)際例子骆捧。
案例1:從數(shù)組中刪除重復(fù)的值
如果想快速地從數(shù)組中刪除重復(fù)的值澎羞，可以將其轉(zhuǎn)換為一個 Set。這是迄今為止過濾惟一值最簡潔的方法:
const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
// 將數(shù)組轉(zhuǎn)換為 Set
let uniqueCollection = new Set(duplicateCollection);
console.log(uniqueCollection) // Result: Set(4) {"A", "B", "C", "D"}
// 值保存在數(shù)組中
let uniqueCollection = [...new Set(duplicateCollection)];
console.log(uniqueCollection) // Result: ["A", "B", "C", "D"]
案例2：谷歌面試問題
問題：
給定一個整數(shù)無序數(shù)組和變量 sum敛苇，如果存在數(shù)組中任意兩項(xiàng)和使等于 sum 的值妆绞，則返回true。否則,返回false枫攀。例如括饶，數(shù)組[3,5,1,4]和 sum = 9，函數(shù)應(yīng)該返回true来涨，因?yàn)?code>4 + 5 = 9图焰。
解答
解決這個問題的一個很好的方法是遍歷數(shù)組，創(chuàng)建 Set保存相對差值蹦掐。
當(dāng)我們遇到3時楞泼，我們可以把6加到Set中, 因?yàn)槲覀冎牢覀冃枰业?code>9的和驰徊。然后，每當(dāng)我們接觸到數(shù)組中的新值時堕阔，我們可以檢查它是否在 Set 中棍厂。當(dāng)遇到5時，在 Set 加上4超陆。最后牺弹，當(dāng)我們最終遇到4時，可以在Set中找到它时呀，就返回true张漂。
const findSum = (arr, val) => {
let searchValues = new Set();
searchValues.add(val - arr[0]);
for (let i = 1, length = arr.length; i < length; i++) {
let searchVal = val - arr[i];
if (searchValues.has(arr[i])) {
return true;
} else {
searchValues.add(searchVal);
}
};
return false;
};
簡潔的版本：
const findSum = (arr, sum) =>
arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));
因?yàn)?code>Set.prototype.has()的時間復(fù)雜度僅為O(1)，所以使用 Set 來代替數(shù)組谨娜，最終使整個解決方案的線性運(yùn)行時為O(N)航攒。
如果使用 Array.prototype.indexOf()或Array.prototype.includes()，它們的時間復(fù)雜度都為 O(N)趴梢，則總運(yùn)行時間將為O(N2)漠畜，慢得多！
參考
關(guān)于Fundebug
Fundebug專注于JavaScript坞靶、微信小程序憔狞、微信小游戲、支付寶小程序彰阴、React Native瘾敢、Node.js和Java線上應(yīng)用實(shí)時BUG監(jiān)控。 自從2016年雙十一正式上線尿这，F(xiàn)undebug累計(jì)處理了10億+錯誤事件簇抵，付費(fèi)客戶有陽光保險、核桃編程射众、荔枝FM碟摆、掌門1對1、微脈责球、青團(tuán)社等眾多品牌企業(yè)焦履。歡迎大家免費(fèi)試用拓劝！
