PTT推薦

Re: [討論] 技術總監有可能不懂BFS嗎??

看板Soft_Job標題Re: [討論] 技術總監有可能不懂BFS嗎??作者
leviliang
(慕尼黑林志穎)
時間推噓 6 推:7 噓:1 →:44

來單純技術討論一下好了

其實 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 等其他技術,目前尚未實作於 Standard Library 裡,所以有需求的話要自行實作。
3. Bloom Filters 可以解放傳統 HashSet 儲存空間帶來的限制,原理很簡單,如果不太清楚請中文維基就可以輕鬆看懂(一般大學的分散式系統課程也都會教到)。


--

※ PTT 留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 138.246.3.10 (德國)
PTT 網址
※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 04:36:07

plsmaop04/23 06:02通常效能的差異不在於 hash ,而是不需要一直分配新的記

plsmaop04/23 06:02憶體

感謝提醒 我居然忽略了這最重要的一環

previa04/23 08:11主要差異就是在整個解法能不能scale 而已

這也是一個很棒的考量點!

ku39999904/23 08:15陣列如果資料一直往後放不排序 查詢速度就是n 如果要排

ku39999904/23 08:17序就要移動大量資料 即使不用分配也快不到哪吧

等等 一般的做法是一個布林陣列然後 node tag 當做 index 因此找 visited node 就是 O(1) 我其實沒很仔細看 Nic 怎麼實作 還是他的實作是你說的方式!?

※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 08:42:54

s06yji304/23 08:44陣列是固定size的東西。如果紀錄的東西是整數,可以直接

s06yji304/23 08:44把他當作陣列的index,搜尋就是O(1)

s06yji304/23 08:45Nic作法是O(n) XD

s06yji304/23 08:45但是後來換成用Set了

peter9804/23 11:43用hash不代表要一直分配新的記憶體

peter9804/23 11:43一直動態分配記憶體的不是hash 兩者關係並不大

s06yji304/23 12:38嚴格來說你要講HashSet才對。

NTHUlagka04/23 15:30樓上你hash不動態分配記憶體 那新的值進來你要怎辦 你

NTHUlagka04/23 15:30一開始不知道要開多大的Hash吧

NTHUlagka04/23 15:43還是其實C++hash背後也是vector 那就沒事了

a123456728904/23 15:51hashmap/set都會牽涉到Load factor 當現在容器裡裝

a123456728904/23 15:51了超過一定比例的數量就會自動擴容 但確實hash與否

a123456728904/23 15:51和是否動態配置記憶體是兩回事 此外本文的方法一

a123456728904/23 15:51也可以視為是一種hashset

a123456728904/23 15:52以上自動擴容我講的是現今大多數語言的實作

peter9804/23 19:43額 s06yji3 看來你真的不董hash用到的vector其動態配置

peter9804/23 19:43的做法&時機點 建議你找一本簡單的演算法課本讀一下 = =

peter9804/23 19:44hash會用到動態配置 但是hash如果遇到效能問題 問題根

peter9804/23 19:45源不是在動態配置 這是兩回事 每次都用動態配置會造成

peter9804/23 19:45效能問題沒錯 但問題是hash不會出現老是一直需要動態配

peter9804/23 19:45置 去把大三演算法課本拿出來複習一下 = = 肯定有教

peter9804/23 19:47靠 at錯人 是NTHUlagka可以去讀一下演算法

peter9804/23 19:48兩件事 loading factor + 類似exp backoff的作法

peter9804/23 19:48並不會讓hash有動態配置造成的效能問題

saladim04/23 20:30Hash還有一些簿記的overhead, 而且長的也有80分像array

saladim04/23 20:31若是在都要traversal近乎全部的狀況 或許考慮的是nodeId

saladim04/23 20:32的分布狀況 阿 話說回來 不連續也能弄成連續的 純array

saladim04/23 20:32還是有其優勢在

NTHUlagka04/23 20:40喔喔我知道啊 所以我想說如果hash背後是vector的那種

NTHUlagka04/23 20:40方式擴充就沒事了

NTHUlagka04/23 20:42是你講的好像沒用到動態配置我才提出疑問怎可能沒用到

NTHUlagka04/23 20:42 實際上是有用到但瓶頸不是在那邊你這樣講不就好了

NTHUlagka04/23 20:44喔喔沒有是我搞錯少看到一直 當小丑了 抱歉

peter9804/23 20:50hash背後即使不是vector 也不會有動態配置造成效能瓶頸

peter9804/23 20:50的問題 現在論文再解決hash效能時 可以看到從來不是在

peter9804/23 20:51管記憶體配置 極大程度代表動態配置的影響根本微乎其微

peter9804/23 20:51真正的效能在於hash的設計 以及其查找的方法 最經典的

peter9804/23 20:51例子就是bloom filter

peter9804/23 20:52看來NTHU大大是認真討論 我道歉~對不起~剛推文太邱~

NTHUlagka04/23 20:58我的錯沒看仔細 抱歉 所以瓶頸是在collision 那現在Ha

NTHUlagka04/23 20:58sh的Hash function都是以bloom filter嗎?還是有更新

NTHUlagka04/23 20:58

peter9804/23 20:59更正: "從來不是"在管記憶體配置 --> "很少"在管

NTHUlagka04/23 21:06喔喔原來是另一種有別於hash table的資料結構 genius

NTHUlagka04/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

Lordaeron04/24 20:23https://github.com/terrylao/PascalContainer 這有你

Lordaeron04/24 20:24們討論的東西的參考。他實作這麼多了,該做總統了....