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

作者: leviliang (levi)   2023-04-23 04:31:46
來單純技術討論一下好了
其實 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 儲存空間帶來的限制,原理很簡單,如果不太
清楚請中文維基就可以輕鬆看懂(一般大學的分散式系統課程也都會教到)。
作者: plsmaop (plsmaop)   2023-04-23 06:02:00
通常效能的差異不在於 hash ,而是不需要一直分配新的記憶體
作者: previa (.)   2023-04-23 08:11:00
主要差異就是在整個解法能不能scale 而已
作者: ku399999   2023-04-23 08:15:00
陣列如果資料一直往後放不排序 查詢速度就是n 如果要排序就要移動大量資料 即使不用分配也快不到哪吧
作者: s06yji3 (阿南)   2023-04-23 08:44:00
陣列是固定size的東西。如果紀錄的東西是整數,可以直接把他當作陣列的index,搜尋就是O(1)Nic作法是O(n) XD但是後來換成用Set了
作者: peter98 (新兵)   2023-04-23 11:43:00
用hash不代表要一直分配新的記憶體一直動態分配記憶體的不是hash 兩者關係並不大
作者: s06yji3 (阿南)   2023-04-23 12:38:00
嚴格來說你要講HashSet才對。
作者: NTHUlagka (拉卡)   2023-04-23 15:30:00
樓上你hash不動態分配記憶體 那新的值進來你要怎辦 你一開始不知道要開多大的Hash吧還是其實C++hash背後也是vector 那就沒事了
作者: a1234567289 (蛋包飯)   2023-04-23 15:51:00
hashmap/set都會牽涉到Load factor 當現在容器裡裝了超過一定比例的數量就會自動擴容 但確實hash與否和是否動態配置記憶體是兩回事 此外本文的方法一也可以視為是一種hashset以上自動擴容我講的是現今大多數語言的實作
作者: peter98 (新兵)   2023-04-23 19:43:00
額 s06yji3 看來你真的不董hash用到的vector其動態配置的做法&時機點 建議你找一本簡單的演算法課本讀一下 = =hash會用到動態配置 但是hash如果遇到效能問題 問題根源不是在動態配置 這是兩回事 每次都用動態配置會造成效能問題沒錯 但問題是hash不會出現老是一直需要動態配置 去把大三演算法課本拿出來複習一下 = = 肯定有教靠 at錯人 是NTHUlagka可以去讀一下演算法兩件事 loading factor + 類似exp backoff的作法並不會讓hash有動態配置造成的效能問題
作者: saladim (殺拉頂)   2023-04-23 20:30:00
Hash還有一些簿記的overhead, 而且長的也有80分像array若是在都要traversal近乎全部的狀況 或許考慮的是nodeId的分布狀況 阿 話說回來 不連續也能弄成連續的 純array還是有其優勢在
作者: NTHUlagka (拉卡)   2023-04-23 20:40:00
喔喔我知道啊 所以我想說如果hash背後是vector的那種方式擴充就沒事了是你講的好像沒用到動態配置我才提出疑問怎可能沒用到實際上是有用到但瓶頸不是在那邊你這樣講不就好了喔喔沒有是我搞錯少看到一直 當小丑了 抱歉
作者: peter98 (新兵)   2023-04-23 20:50:00
hash背後即使不是vector 也不會有動態配置造成效能瓶頸的問題 現在論文再解決hash效能時 可以看到從來不是在管記憶體配置 極大程度代表動態配置的影響根本微乎其微真正的效能在於hash的設計 以及其查找的方法 最經典的例子就是bloom filter看來NTHU大大是認真討論 我道歉~對不起~剛推文太邱~
作者: NTHUlagka (拉卡)   2023-04-23 20:58:00
我的錯沒看仔細 抱歉 所以瓶頸是在collision 那現在Hash的Hash function都是以bloom filter嗎?還是有更新的
作者: peter98 (新兵)   2023-04-23 20:59:00
更正: "從來不是"在管記憶體配置 --> "很少"在管
作者: NTHUlagka (拉卡)   2023-04-23 21:06:00
喔喔原來是另一種有別於hash table的資料結構 genius感謝
作者: Lordaeron (Terry)   2023-04-24 20:23:00
https://github.com/terrylao/PascalContainer 這有你們討論的東西的參考。他實作這麼多了,該做總統了....
作者: superpandal   2023-04-29 20:05:00
java的hash不是重點 重點它怎麼解決衝突這種東西有碰到再研究也不是不可以

Links booklink

Contact Us: admin [ a t ] ucptt.com