作者leviliang (慕尼黑林志穎)
看板Soft_Job
標題Re: [討論] 技術總監有可能不懂BFS嗎??
時間Sun Apr 23 04:31:46 2023
來單純技術討論一下好了
其實 Visit 也不用限制一定要用 HashMap/HashSet 做
Leetcode 上很多題目的 nodes tag 都是連續的數字或英文字母
這個時候用一般的 Array 效能就會比 HashMap/HashSet 好非常多：
1. 不需動態分配記憶體（感謝一樓提醒）
2. 不需進行 Hash 運算
但也正如同大多數大大所說
一般人的想像場景不會是連續的標籤
在 nodes tag 都不連續的情況下
例如：1, 100, 10000, 1000000, 100000000
這個時候用 Array 就是低能兒了
個人淺見如上
如有錯誤還請各位大大指正
補充 peter98 與 NTHUlagka 底下關於 Hash 的討論（小弟對於 C++ 只能算是略懂，如
果錯誤就再麻煩指正了）：
1. 就 C++ Standard Library 對於 HashMap/HashSet 的實作，一開始會先分配一定數量
的 buckets，後續如果超過 loading factor（預設 1.0）,再動態增加（std::vecotor
的實作上
一般是加倍）。
2. 關於 Exponential Backoff 與 Bloom Filters 等其他技術，目前尚未實作於 Standa
rd Library 裡，所以有需求的話要自行實作。
3. Bloom Filters 可以解放傳統 HashSet 儲存空間帶來的限制，原理很簡單，如果不太
清楚請中文維基就可以輕鬆看懂（一般大學的分散式系統課程也都會教到）。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 138.246.3.10 (德國)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Soft_Job/M.1682195508.A.1B8.html
※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 04:36:07
1F：推 plsmaop: 通常效能的差異不在於 hash ，而是不需要一直分配新的記04/23 06:02
2F：→ plsmaop: 憶體04/23 06:02
感謝提醒 我居然忽略了這最重要的一環
3F：→ previa: 主要差異就是在整個解法能不能scale 而已04/23 08:11
這也是一個很棒的考量點！
4F：→ ku399999: 陣列如果資料一直往後放不排序 查詢速度就是n 如果要排04/23 08:15
5F：→ ku399999: 序就要移動大量資料 即使不用分配也快不到哪吧04/23 08:17
等等 一般的做法是一個布林陣列然後 node tag 當做 index
因此找 visited node 就是 O(1)
我其實沒很仔細看 Nic 怎麼實作
還是他的實作是你說的方式！？
※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 08:42:54
6F：推 s06yji3: 陣列是固定size的東西。如果紀錄的東西是整數，可以直接04/23 08:44
7F：→ s06yji3: 把他當作陣列的index，搜尋就是O(1)04/23 08:44
8F：→ s06yji3: Nic作法是O(n) XD04/23 08:45
9F：→ s06yji3: 但是後來換成用Set了04/23 08:45
10F：噓 peter98: 用hash不代表要一直分配新的記憶體04/23 11:43
11F：→ peter98: 一直動態分配記憶體的不是hash 兩者關係並不大04/23 11:43
12F：推 s06yji3: 嚴格來說你要講HashSet才對。04/23 12:38
13F：→ NTHUlagka: 樓上你hash不動態分配記憶體 那新的值進來你要怎辦 你04/23 15:30
14F：→ NTHUlagka: 一開始不知道要開多大的Hash吧 04/23 15:30
15F：→ NTHUlagka: 還是其實C++hash背後也是vector 那就沒事了04/23 15:43
16F：推 a1234567289: hashmap/set都會牽涉到Load factor 當現在容器裡裝 04/23 15:51
17F：→ a1234567289: 了超過一定比例的數量就會自動擴容 但確實hash與否 04/23 15:51
18F：→ a1234567289: 和是否動態配置記憶體是兩回事 此外本文的方法一04/23 15:51
19F：→ a1234567289: 也可以視為是一種hashset 04/23 15:51
20F：→ a1234567289: 以上自動擴容我講的是現今大多數語言的實作04/23 15:52
21F：→ peter98: 額 s06yji3 看來你真的不董hash用到的vector其動態配置 04/23 19:43
22F：→ peter98: 的做法&時機點 建議你找一本簡單的演算法課本讀一下 = = 04/23 19:43
23F：→ peter98: hash會用到動態配置 但是hash如果遇到效能問題 問題根04/23 19:44
24F：→ peter98: 源不是在動態配置 這是兩回事 每次都用動態配置會造成04/23 19:45
25F：→ peter98: 效能問題沒錯 但問題是hash不會出現老是一直需要動態配04/23 19:45
26F：→ peter98: 置 去把大三演算法課本拿出來複習一下 = = 肯定有教04/23 19:45
27F：→ peter98: 靠 at錯人 是NTHUlagka可以去讀一下演算法04/23 19:47
28F：→ peter98: 兩件事 loading factor + 類似exp backoff的作法04/23 19:48
29F：→ peter98: 並不會讓hash有動態配置造成的效能問題04/23 19:48
30F：→ saladim: Hash還有一些簿記的overhead, 而且長的也有80分像array04/23 20:30
31F：→ saladim: 若是在都要traversal近乎全部的狀況 或許考慮的是nodeId04/23 20:31
32F：→ saladim: 的分布狀況 阿 話說回來 不連續也能弄成連續的 純array04/23 20:32
33F：→ saladim: 還是有其優勢在04/23 20:32
34F：推 NTHUlagka: 喔喔我知道啊 所以我想說如果hash背後是vector的那種04/23 20:40
35F：→ NTHUlagka: 方式擴充就沒事了04/23 20:40
36F：→ NTHUlagka: 是你講的好像沒用到動態配置我才提出疑問怎可能沒用到 04/23 20:42
37F：→ NTHUlagka: 實際上是有用到但瓶頸不是在那邊你這樣講不就好了04/23 20:42
38F：推 NTHUlagka: 喔喔沒有是我搞錯少看到一直 當小丑了 抱歉 04/23 20:44
39F：→ peter98: hash背後即使不是vector 也不會有動態配置造成效能瓶頸 04/23 20:50
40F：→ peter98: 的問題 現在論文再解決hash效能時 可以看到從來不是在04/23 20:50
41F：→ peter98: 管記憶體配置 極大程度代表動態配置的影響根本微乎其微 04/23 20:51
42F：→ peter98: 真正的效能在於hash的設計 以及其查找的方法 最經典的04/23 20:51
43F：→ peter98: 例子就是bloom filter 04/23 20:51
44F：→ peter98: 看來NTHU大大是認真討論 我道歉~對不起~剛推文太邱~ 04/23 20:52
45F：推 NTHUlagka: 我的錯沒看仔細 抱歉 所以瓶頸是在collision 那現在Ha04/23 20:58
46F：→ NTHUlagka: sh的Hash function都是以bloom filter嗎？還是有更新04/23 20:58
47F：→ NTHUlagka: 的04/23 20:58
48F：→ peter98: 更正: "從來不是"在管記憶體配置 --> "很少"在管04/23 20:59
49F：→ NTHUlagka: 喔喔原來是另一種有別於hash table的資料結構 genius04/23 21:06
50F：→ NTHUlagka: 感謝04/23 21:06
感謝各位的討論與分享
資訊量很大我一起整理到本文中
順便把名詞打清楚
※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 23:09:39
※ 編輯: leviliang (138.246.3.10 德國), 04/24/2023 03:48:50
52F：→ Lordaeron: 們討論的東西的參考。他實作這麼多了，該做總統了.... 04/24 20:24
53F：→ superpandal: java的hash不是重點 重點它怎麼解決衝突 04/29 20:05
54F：→ superpandal: 這種東西有碰到再研究也不是不可以 04/29 20:06