• QQ咨詢:4001806960
  • 咨詢熱線:400-180-6960

如何利用 JS 的 Set 對象讓你的代碼運行的更快

作者:日期:2019-04-20 15:05:59 點擊:273 set的用法,set優勢

我堅信很多開發者依舊與這些基本的全局對象打交道:numbers,strings,objects,arrays 和 booleans。

大部分業務場景,以上這些已經夠用了。但是,如果你想讓你的代碼運行的盡可能快、可擴展性盡可能的好,那麽這些基本類型並不夠優秀。

在這篇文章,我們將要討論如何利用 JS 的 Set 對象讓你的代碼運行的更快——尤其是在它所處理的數據量大的時候。Array 和 Set 在處理數據時,兩則有太多的相似。但是使用 Set 所帶來的運行時優勢,是 Array 無法完成的。

Set 有何不同?

根本的區別就是 Array 是 索引集合(index collection)。這意味著,數據的值是以 索引(index) 排序的。


const arr = [A, B, C, D];
console.log(arr.indexOf(A));// Result: 0
console.log(arr.indexOf(C));// Result: 2

而 Set 則是 鍵集合(keyed collection)。相比使用 索引,Set 使用 鍵 來組織它的數據。一個 Set 中所有項都是按插入順序可叠代的,它不會有重複值。換句話說,Set 中的每一項都是獨一無二的。

最主要的收益是什麽?

Set 相比 Array 有些優勢,特別是考慮到需要更快的運行時間:

  • 查找項: 使用 indexOf() 或 includes() 去檢查一個項是否在數組中很慢。
  • 刪除項: 在 Set 中,你可以使用 值 去刪除一項。而在 Array 中,相同的功能需要使用項的 索引 使用 splice()方法。使用 索引 是很慢的
  • 插入項: 在 Set 中新增一項比 Array 使用 push() 或者 unshift() 等方法新增一項要快的多。
  • 排序NaN值: 你無法使用 Array 的 indexOf() 或者 includes() 去定位 NaN 值,但是 Set 可以並且能夠存儲這個值
  • 去重: Set 對象只存儲獨一無二的值,如果你想避免儲存重複值,這是比 Array 更好的選擇,因爲使用 Array,你需要使用額外的代碼去處理這種情況。
Note: 更多 Set 內置方法,請查閱 MDN Web Docs

什麽是時間複雜度?

使用 Array 去查找是一個爲 O(N) 的線性時間複雜度。換句話說,隨著數據量的提高,運行時間隨著增加。

相比而言,使用 Set 去查找,不管是刪除還是插入的時間複雜度都僅僅是 O(1)——這意味著,運行時間不隨著數量的提高而增加。

那麽 Set 究竟有多快呢?

雖然運行時間受使用的操作系統、數據的大小和其它的一些變量的影響,我希望我的測試結果能讓你對 Set 的速度有個直觀的感受。

准備測試

在開始運行之前,我們簡單的將 Array 和 Set 填充 1000000 個值(0~999999)


let arr = [], set = new Set(), n = 1000000;
for(let i = 0; i < n; i++){
arr.push(i);
set.add(i);
}

測試1:查找

查找值 123123:


let result;
console.time('Array');
result = arr.indexOf(123123) !== -1;
console.timeEnd('Array');
console.time('Set');
rusult = set.has(123123);
console.timeEnd('Set');
  • Array: 0.173ms
  • Set: 0.023ms
  • Set 快了 7.54 倍

測試2: 新增

新增一個值,變量爲 n:


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:刪除

最後,我們刪除一項(就刪除我們剛新增的)。因爲 Array 沒有原生刪除方法,我們寫一個 helper 來完成這個功能:


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 相比 Array 優勢巨大。現在我們來看看 Set 的一些實踐:

用例1: 數組去重

如果你想要在 Array 中快速去重,你可以將它轉爲 Set。這是目前爲止最簡潔的方法。


const duplicateCollection = ['A','B','B','C',''D','B','E'];
//如果你想把 Array 轉成 Set
let uniqueCollection = new Set(duplicateCollection);
console.log(uniqueCollection) //Set(4) {"A","B","C","D"};
//如果你想讓你的值仍是`Array`
let uniqueCollection = [...new Set(duplicateCollection)];
console.log(uniqueCollection)//["A","B","C","D"]

用例2:谷歌面試題

在我的另一篇文章中,我爲谷歌面試官的一個問題討論了一些解決方案。面試是使用 C++,但是如果是 JS,Set 會是最終解決方案的關鍵點。

如果你想要更深入了解這些解決方案,我推薦閱讀原文,但是這裏,我簡單的介紹一下解決方案。

問題是這樣的

給一個未排序的整數數組和一個值 sum,如果數組中任意兩項相加等于 sum,則返回 true,否則返回 false。

如給定數組 [3, 5, 1, 4] 和值 9,我們的方法應該返回 true,因爲 4 + 5 = 9。


這裏解釋思路,不翻譯了,看代碼就能懂。

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) => ((set => n => set.has(n) || !set.add(sum - n))(new set));

因爲 Set.prototype.has() 時間複雜度只有 O(1), 使用 Set 存儲數據,結合 Array 的循環,我們最終的時間複雜度爲 O(N)。

如果我們依賴 Array.prototype.indexOf() 或 Array.prototype.includes(),而兩者的時間複雜度都是 O(N), 我們最終的時間複雜度會達到 O(N²)。太慢了!

希望本文對你有所幫助

上一篇: 彎道超車,5分鍾快速理解構造器函數與原型對象之間的關系

下一篇: 站內信最佳通信方案:WebSocket