看板Soft_Job
作者leviliang (慕尼黑林志穎)
標題Re: [討論] 技術總監有可能不懂BFS嗎??
時間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 儲存空間帶來的限制，原理很簡單，如果不太 清楚請中文維基就可以輕鬆看懂（一般大學的分散式系統課程也都會教到）。 -- ※ 發信站: 批踢踢實業坊(ptt-site.org.tw), 來自: 138.246.3.10 (德國) ※ 文章網址: https://ptt-site.org.tw/Soft_Job/M.1682195508.A.1B8 ※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 04:36:07
推 plsmaop: 通常效能的差異不在於 hash ，而是不需要一直分配新的記04/23 06:02
→ plsmaop: 憶體04/23 06:02
→ previa: 主要差異就是在整個解法能不能scale 而已04/23 08:11
→ ku399999: 陣列如果資料一直往後放不排序 查詢速度就是n 如果要排04/23 08:15
→ ku399999: 序就要移動大量資料 即使不用分配也快不到哪吧04/23 08:17
推 FishRoom: 真的有這麼多人在找包養嗎04/23 08:17
推 s06yji3: 陣列是固定size的東西。如果紀錄的東西是整數，可以直接04/23 08:44
→ s06yji3: 把他當作陣列的index，搜尋就是O(1)04/23 08:44
→ s06yji3: Nic作法是O(n) XD04/23 08:45
→ s06yji3: 但是後來換成用Set了04/23 08:45
噓 peter98: 用hash不代表要一直分配新的記憶體04/23 11:43
推 KsiR: 有人可以分析一下包養平台的差異嗎04/23 11:43
→ peter98: 一直動態分配記憶體的不是hash 兩者關係並不大04/23 11:43
推 s06yji3: 嚴格來說你要講HashSet才對。04/23 12:38
→ NTHUlagka: 樓上你hash不動態分配記憶體 那新的值進來你要怎辦 你04/23 15:30
→ NTHUlagka: 一開始不知道要開多大的Hash吧 04/23 15:30
→ NTHUlagka: 還是其實C++hash背後也是vector 那就沒事了04/23 15:43
推 peoples: 那個包養網人最多XD04/23 15:43
推 a1234567289: hashmap/set都會牽涉到Load factor 當現在容器裡裝 04/23 15:51
→ a1234567289: 了超過一定比例的數量就會自動擴容 但確實hash與否 04/23 15:51
→ a1234567289: 和是否動態配置記憶體是兩回事 此外本文的方法一04/23 15:51
→ a1234567289: 也可以視為是一種hashset 04/23 15:51
→ a1234567289: 以上自動擴容我講的是現今大多數語言的實作04/23 15:52
推 wilmer: 我妹上包養網被我發現= =04/23 15:52
→ peter98: 額 s06yji3 看來你真的不董hash用到的vector其動態配置 04/23 19:43
→ peter98: 的做法&時機點 建議你找一本簡單的演算法課本讀一下 = = 04/23 19:43
→ peter98: hash會用到動態配置 但是hash如果遇到效能問題 問題根04/23 19:44
→ peter98: 源不是在動態配置 這是兩回事 每次都用動態配置會造成04/23 19:45
→ peter98: 效能問題沒錯 但問題是hash不會出現老是一直需要動態配04/23 19:45
推 badlip: 隔壁桌的人竟然在討論包養...04/23 19:45
→ peter98: 置 去把大三演算法課本拿出來複習一下 = = 肯定有教04/23 19:45
→ peter98: 靠 at錯人 是NTHUlagka可以去讀一下演算法04/23 19:47
→ peter98: 兩件事 loading factor + 類似exp backoff的作法04/23 19:48
→ peter98: 並不會讓hash有動態配置造成的效能問題04/23 19:48
→ saladim: Hash還有一些簿記的overhead, 而且長的也有80分像array04/23 20:30
推 piggyoil: 樓上是不是被包養04/23 20:30
→ saladim: 若是在都要traversal近乎全部的狀況 或許考慮的是nodeId04/23 20:31
→ saladim: 的分布狀況 阿 話說回來 不連續也能弄成連續的 純array04/23 20:32
→ saladim: 還是有其優勢在04/23 20:32
推 NTHUlagka: 喔喔我知道啊 所以我想說如果hash背後是vector的那種04/23 20:40
→ NTHUlagka: 方式擴充就沒事了04/23 20:40
推 TwixBar: 未看先猜這包養網04/23 20:40
→ NTHUlagka: 是你講的好像沒用到動態配置我才提出疑問怎可能沒用到 04/23 20:42
→ NTHUlagka: 實際上是有用到但瓶頸不是在那邊你這樣講不就好了04/23 20:42
推 NTHUlagka: 喔喔沒有是我搞錯少看到一直 當小丑了 抱歉 04/23 20:44
→ peter98: hash背後即使不是vector 也不會有動態配置造成效能瓶頸 04/23 20:50
→ peter98: 的問題 現在論文再解決hash效能時 可以看到從來不是在04/23 20:50
推 boggicer: 一定又是這包養網04/23 20:50
→ peter98: 管記憶體配置 極大程度代表動態配置的影響根本微乎其微 04/23 20:51
→ peter98: 真正的效能在於hash的設計 以及其查找的方法 最經典的04/23 20:51
→ peter98: 例子就是bloom filter 04/23 20:51
→ peter98: 看來NTHU大大是認真討論 我道歉~對不起~剛推文太邱~ 04/23 20:52
推 NTHUlagka: 我的錯沒看仔細 抱歉 所以瓶頸是在collision 那現在Ha04/23 20:58
推 Chiason: 包養平台不意外04/23 20:58
→ NTHUlagka: sh的Hash function都是以bloom filter嗎？還是有更新04/23 20:58
→ NTHUlagka: 的04/23 20:58
→ peter98: 更正: "從來不是"在管記憶體配置 --> "很少"在管04/23 20:59
→ NTHUlagka: 喔喔原來是另一種有別於hash table的資料結構 genius04/23 21:06
→ NTHUlagka: 感謝04/23 21:06
推 Markell: 覺得包養網EY嗎04/23 21:06
→ Lordaeron: https://github.com/terrylao/PascalContainer 這有你 04/24 20:23
→ Lordaeron: 們討論的東西的參考。他實作這麼多了，該做總統了.... 04/24 20:24
→ superpandal: java的hash不是重點 重點它怎麼解決衝突 04/29 20:05
→ superpandal: 這種東西有碰到再研究也不是不可以 04/29 20:06