回看板
Disp BBS
作者 leviliang (慕尼黑林志穎)
標題 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 的討論：
1. 就 C++ Standard Library 對於 HashMap/HashSet 的實作，一開始會先分配一定數量
的 buckets，後續如果超過 loading factor（預設 1.0）,再動態增加（vecotor 的實作
一般是加倍）。

2. 關於 Exponential Backoff 與 Bloom Filters，目前尚未實作於 Standard Library
裡，所以有需求的話要自己實作。


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 138.246.3.10 (德國)
※ 作者: leviliang 2023-04-23 04:31:46
※ 文章代碼(AID): #1aH4Gq6u (Soft_Job)
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1682195508.A.1B8.html
※ 同主題文章:
[討論] 技術總監有可能不懂BFS嗎??
04-20 21:17 LinuxKernel
Re: [討論] 技術總監有可能不懂BFS嗎??
04-22 09:09 stevekevin10
Re: [討論] 技術總監有可能不懂BFS嗎??
04-23 03:27 ripple0129
Re: [討論] 技術總監有可能不懂BFS嗎??
04-23 04:31 leviliang
Re: [討論] 技術總監有可能不懂BFS嗎??
04-23 12:17 BeardSmallGG
Re: [討論] 技術總監有可能不懂BFS嗎??
04-23 13:59 ripple0129
Re: [討論] 技術總監有可能不懂BFS嗎??
04-26 09:05 cateran
※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 04:36:07
推 plsmaop: 通常效能的差異不在於 hash ，而是不需要一直分配新的記憶體1F 04/23 06:02
感謝提醒 我居然忽略了這最重要的一環
→ previa: 主要差異就是在整個解法能不能scale 而已3F 04/23 08:11
這也是一個很棒的考量點！
→ ku399999: 陣列如果資料一直往後放不排序 查詢速度就是n 如果要排序就要移動大量資料 即使不用分配也快不到哪吧4F 04/23 08:15
等等 一般的做法是一個布林陣列然後 node tag 當做 index
因此找 visited node 就是 O(1)
我其實沒很仔細看 Nic 怎麼實作
還是他的實作是你說的方式！？
※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 08:42:54
推 s06yji3: 陣列是固定size的東西。如果紀錄的東西是整數，可以直接把他當作陣列的index，搜尋就是O(1)
Nic作法是O(n) XD
但是後來換成用Set了6F 04/23 08:44
噓 peter98: 用hash不代表要一直分配新的記憶體
一直動態分配記憶體的不是hash  兩者關係並不大10F 04/23 11:43
推 s06yji3: 嚴格來說你要講HashSet才對。12F 04/23 12:38
→ NTHUlagka: 樓上你hash不動態分配記憶體 那新的值進來你要怎辦 你一開始不知道要開多大的Hash吧
還是其實C++hash背後也是vector 那就沒事了13F 04/23 15:30
推 a1234567289: hashmap/set都會牽涉到Load factor 當現在容器裡裝了超過一定比例的數量就會自動擴容 但確實hash與否和是否動態配置記憶體是兩回事   此外本文的方法一也可以視為是一種hashset
以上自動擴容我講的是現今大多數語言的實作16F 04/23 15:51
→ peter98: 額  s06yji3  看來你真的不董hash用到的vector其動態配置的做法&時機點  建議你找一本簡單的演算法課本讀一下 = =hash會用到動態配置  但是hash如果遇到效能問題  問題根源不是在動態配置  這是兩回事  每次都用動態配置會造成效能問題沒錯  但問題是hash不會出現老是一直需要動態配置  去把大三演算法課本拿出來複習一下 = =  肯定有教
靠  at錯人  是NTHUlagka可以去讀一下演算法
兩件事 loading factor + 類似exp backoff的作法
並不會讓hash有動態配置造成的效能問題21F 04/23 19:43
→ saladim: Hash還有一些簿記的overhead, 而且長的也有80分像array若是在都要traversal近乎全部的狀況 或許考慮的是nodeId的分布狀況  阿 話說回來 不連續也能弄成連續的 純array還是有其優勢在30F 04/23 20:30
推 NTHUlagka: 喔喔我知道啊 所以我想說如果hash背後是vector的那種方式擴充就沒事了
是你講的好像沒用到動態配置我才提出疑問怎可能沒用到 實際上是有用到但瓶頸不是在那邊你這樣講不就好了
喔喔沒有是我搞錯少看到一直 當小丑了 抱歉34F 04/23 20:40
→ peter98: hash背後即使不是vector  也不會有動態配置造成效能瓶頸的問題  現在論文再解決hash效能時  可以看到從來不是在管記憶體配置  極大程度代表動態配置的影響根本微乎其微真正的效能在於hash的設計  以及其查找的方法  最經典的例子就是bloom filter
看來NTHU大大是認真討論  我道歉~對不起~剛推文太邱~39F 04/23 20:50
推 NTHUlagka: 我的錯沒看仔細 抱歉 所以瓶頸是在collision 那現在Hash的Hash function都是以bloom filter嗎？還是有更新的45F 04/23 20:58
→ peter98: 更正: "從來不是"在管記憶體配置  --> "很少"在管48F 04/23 20:59
→ NTHUlagka: 喔喔原來是另一種有別於hash table的資料結構 genius感謝49F 04/23 21:06
感謝各位的討論與分享
資訊量很大我一起整理到本文中
順便把名詞打清楚
※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 23:09:39
--
作者 leviliang 的最新發文:
點此顯示更多發文記錄