PTT職涯區 / Soft_Job (軟體人)

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

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