iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 8
4
Software Development

前端工程師用 javaScript 學演算法系列 第 8

Array vs. Set

講完 Array 跟 Set 後,覺得他們似乎都專注在 value,而且基本上 Array 可以做的事 Set 也可以做? 那我們是不是可以完全用 Set 取代掉 Array 呢?
https://ithelp.ithome.com.tw/upload/images/20190909/20106426IJuhflsyNw.jpg
其實他們是完全不同的資料型態,我們需要根據不同的問題選擇要使用哪一個效率會比較好。


來比較吧!

內建方法

前幾篇已經介紹過 ArraySet 的 method,所以這邊只會列出比較

// 初始值,以下範例都會共用這個 
let arr = [1, 2, 3]
let map = new Map([1, 2, 3])

https://ithelp.ithome.com.tw/upload/images/20190909/20106426i27OsYBKgX.png
Array 比 Set 多出很多 method (map, reduce, filter ... 等等)

時間複雜度

Array Time Complexities

https://ithelp.ithome.com.tw/upload/images/20190909/201064269TZddSXqm2.png
(圖來自 adrianmejia)

push、pop 都是直接在最後一個元素做增減,所以時間複雜度是 Big O(1);
而 unshift、shift、splice、slice 基本上都會動到本來的元素的指引位置(index),所以是 Big O(n)。

什麼叫做會動到本來元素指引位置?
以 unshft() 為例,因為他要把原本元素都往後移一個位置然後把新元素插入最前面,所以時間複雜度是 Big O(n)

arr = [1, 2, 3] // 本來的 Array
arr.unshift(3); //[3,1,2,3]

// -- 以上是怎麼運作的呢
[1, 2, 3]
 0  1  2  // 這邊是 index 指引位置
 
[3, 1, 2, 3]  // 所有本來在 Array 裡元素都往後一格 index +1
 0  1  2  3

Set Time Complexities

https://ithelp.ithome.com.tw/upload/images/20190909/20106426TK57yyNeE2.png
(圖來自 adrianmejia)

Data Structure

Array 是 indexed collection 而 Set 是 keyed collection

Indexed collections” are collections of data which are ordered by an index value

Keyed collections” are collections which use keys; these contain elements which are iterable in the order of insertion.

結論

Set 並不能取代 Array。Set 的優勢就是 value 不能是重覆的,所以可以減少記憶體存取重覆值的浪費。另外尋找跟新增/刪除元素平均的時間複雜度都比 Array 好。
Array 的優勢因為資料是連續的,所以存取非常快速 O(1),需要順序性的問題用 Array 來解就很適合(例如 Binary Search)。並且他提供非常多內建方法可以使用(map、reduce、filter...等)


補充: Common JS Array built-in functions

https://ithelp.ithome.com.tw/upload/images/20190909/20106426CpiKkOomRM.png
(圖來自 adrianmejia)

參考資料

如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您
OS: 才第八天已覺得好累啊~~ 希望可以撐下去

歡迎追蹤我的部落格,除了技術文也會分享一些在矽谷工作的甘苦。


上一篇
集合 Set
下一篇
[LeetCode #217, #804] Set
系列文
前端工程師用 javaScript 學演算法32
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中
0
Tiger
iT邦新手 5 級 ‧ 2019-09-09 07:34:12

加油唷!覺得妳寫得很好、很清楚!

hannahpun iT邦新手 4 級 ‧ 2019-09-09 12:25:58 檢舉

謝謝~~ 有小孩真的挑戰難度加四倍啊

0
Taiming
iT邦新手 1 級 ‧ 2019-11-21 15:32:44

真心大推的好文系列!

隨手看到錯字:
(in 結論)
...所以存取非常快速 O(1),需要順序"姓"... <---- 性

0
iT邦新手 2 級 ‧ 2022-03-16 17:15:24

嗨,這裡有個小疑惑,
是不是有些地方的 Set 不小心寫成 Map 了?
例如初始化的地方。

我要留言

立即登入留言