Re: [討論] 技術總監有可能不懂BFS嗎??
來單純技術討論一下好了
其實 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 儲存空間帶來的限制，原理很簡單，如果不太清楚請中文維基就可以輕鬆看懂（一般大學的分散式系統課程也都會教到）。
--
通常效能的差異不在於 hash ，而是不需要一直分配新的記
憶體
感謝提醒 我居然忽略了這最重要的一環
主要差異就是在整個解法能不能scale 而已
這也是一個很棒的考量點！
陣列如果資料一直往後放不排序 查詢速度就是n 如果要排
序就要移動大量資料 即使不用分配也快不到哪吧
等等 一般的做法是一個布林陣列然後 node tag 當做 index 因此找 visited node 就是 O(1) 我其實沒很仔細看 Nic 怎麼實作 還是他的實作是你說的方式！？
※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 08:42:54陣列是固定size的東西。如果紀錄的東西是整數，可以直接
把他當作陣列的index，搜尋就是O(1)
Nic作法是O(n) XD
但是後來換成用Set了
用hash不代表要一直分配新的記憶體
一直動態分配記憶體的不是hash 兩者關係並不大
嚴格來說你要講HashSet才對。
樓上你hash不動態分配記憶體 那新的值進來你要怎辦 你
一開始不知道要開多大的Hash吧
還是其實C++hash背後也是vector 那就沒事了
hashmap/set都會牽涉到Load factor 當現在容器裡裝
了超過一定比例的數量就會自動擴容 但確實hash與否
和是否動態配置記憶體是兩回事 此外本文的方法一
也可以視為是一種hashset
以上自動擴容我講的是現今大多數語言的實作
額 s06yji3 看來你真的不董hash用到的vector其動態配置
的做法&時機點 建議你找一本簡單的演算法課本讀一下 = =
hash會用到動態配置 但是hash如果遇到效能問題 問題根
源不是在動態配置 這是兩回事 每次都用動態配置會造成
效能問題沒錯 但問題是hash不會出現老是一直需要動態配
置 去把大三演算法課本拿出來複習一下 = = 肯定有教
靠 at錯人 是NTHUlagka可以去讀一下演算法
兩件事 loading factor + 類似exp backoff的作法
並不會讓hash有動態配置造成的效能問題
Hash還有一些簿記的overhead, 而且長的也有80分像array
若是在都要traversal近乎全部的狀況 或許考慮的是nodeId
的分布狀況 阿 話說回來 不連續也能弄成連續的 純array
還是有其優勢在
喔喔我知道啊 所以我想說如果hash背後是vector的那種
方式擴充就沒事了
是你講的好像沒用到動態配置我才提出疑問怎可能沒用到
實際上是有用到但瓶頸不是在那邊你這樣講不就好了
喔喔沒有是我搞錯少看到一直 當小丑了 抱歉
hash背後即使不是vector 也不會有動態配置造成效能瓶頸
的問題 現在論文再解決hash效能時 可以看到從來不是在
管記憶體配置 極大程度代表動態配置的影響根本微乎其微
真正的效能在於hash的設計 以及其查找的方法 最經典的
例子就是bloom filter
看來NTHU大大是認真討論 我道歉~對不起~剛推文太邱~
我的錯沒看仔細 抱歉 所以瓶頸是在collision 那現在Ha
sh的Hash function都是以bloom filter嗎？還是有更新
的
更正: "從來不是"在管記憶體配置 --> "很少"在管
喔喔原來是另一種有別於hash table的資料結構 genius
感謝
感謝各位的討論與分享 資訊量很大我一起整理到本文中 順便把名詞打清楚
※ 編輯: leviliang (138.246.3.10 德國), 04/23/2023 23:09:39 ※ 編輯: leviliang (138.246.3.10 德國), 04/24/2023 03:48:50們討論的東西的參考。他實作這麼多了，該做總統了....
爆
首Po剛看到這個 YT 影片，不喜勿點 在地上滾的工程師 aka Nic aka 工程技術總監 合拍了一個 coding interview 影片 一開始還想說應該是反串吧![[討論] 技術總監有可能不懂BFS嗎??](https://img.youtube.com/vi/BkszA-MvjXA/mqdefault.jpg "[討論] 技術總監有可能不懂BFS嗎??")
21
想問是不是我們程式猴子們都喜歡互相diss呀... YT們拍片基本上都有劇本吧 而且Terry一直以來拍片風格都北爛北爛的 卻一堆留言在說這怎可能是演的 這也太廢24
大概是這樣評估啦 年薪50萬以下的通常不太在意技術 年薪50-100萬的通常會很重視技術 年薪100萬-150萬的會覺得技術才是王道 年薪150萬-300萬的會覺得有比技術更重要的東西15
Big O就像前面某版友推文的比喻 就算不是加減乘除 也是九九乘法表等級 這能忘？ 阿茲海默了嗎？ 不要隨便亂類比成技術 什麼500萬+ 哪個人 說出名字X
欸不是 就寫個大概而已 你怎麼這麼認真 又不是說是絕對的 你是不是100萬-150萬？
看到這個可以聊一下big O notation，很多人在面試的時候可能會回答/或聽到面試官說「big O notation是一個評估演算法效能的方式」 …..其實並不是的哦~ big O notation在數學上是用來描述一個函數的參數在趨近於特定值或無限時的行為表達方式。在computer science領域則是在看「當input size趨於無限時，函數行為為何」的「分類方式」，和效能沒有直接關係。 舉個例子，例如今天有解同一個問題的兩個演算法，一個分析出來其時間複雜度為10^100*x，另一個分析出來時間複雜度是10^(-100)*x^1.1。則前者的big O notation為O(x)，後者為O(x^1.1)，明顯前者更加，但在實務上，當然大家應該會選擇後者的演算法。因此big O notation基本上是一個在分析層面的工具更多一些，在效能評比上可以當作理論分析用，但不是全部，實際開發時還是要透過benchmark才能得到最正確的結論。 因此，不管你是面試官或面試者，只要你聽到有人說big O notation是能拿評估演算法效能的，勇敢嗆回去吧XDDDD![Re: [討論] 技術總監有可能不懂BFS嗎??](https://i.imgur.com/nx3bNOQb.jpg "Re: [討論] 技術總監有可能不懂BFS嗎??")
20
我沒看影片 純就標題其實BFS DFS有時候真的會搞錯 之前面試某小公司 就遇到一題用BFS解 但面試官叫我講解演算法 就一時頭昏說這是DFS 還有其他關都一些大大小小的錯誤
32
Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloudApple 設計這套系統的時候就考慮過有人會出來靠北隱私了 背景知識 - Hash 值: 每個檔案都有一個唯一的 Hash 值 (指紋的概念) 科學家用數學保證他幾乎不會重複 每個雲端空間基本上都會在你上傳檔案的時候計算 Hash 值 為了要避免他們儲存太多重複的檔案![Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloud](https://i.imgur.com/dYDZmnWb.jpg "Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloud")
24
[請益] 面試白板考題目的時間複雜度剛剛編輯文章按到復原草稿 插入很多不必要東西 但用Pitt沒辦法編輯 所以刪除重po不好意思 以下代之前社團認識的學妹代po詢問![[請益] 面試白板考題目的時間複雜度](https://www.facebook.com/images/fb_icon_325x325.png "[請益] 面試白板考題目的時間複雜度")
12
[心得] 圖解演算法 Hash Search有這麼快？(更新)【圖解演算法教學】 還在用古老的二元搜尋法？是時候跟上「Hash Search」 的車尾燈了！ 封面圖： 架構圖： 在我們還沒學資料結構前，通常都用Linear Search找東西。![[心得] 圖解演算法 Hash Search有這麼快？(更新)](https://i.imgur.com/8GfYiTOb.jpg "[心得] 圖解演算法 Hash Search有這麼快？(更新)")
16
[影音] Hash Swan -Silence of the REMHash Swan 1st LP "Silence of the REM" 發行日 2020.02.05 發行社 GENIE MUSIC, Stone Music Entertainment 企劃社 Ambition Musik![[影音] Hash Swan -Silence of the REM](https://i.imgur.com/JmRifFmb.jpg "[影音] Hash Swan -Silence of the REM")
13
Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloud用檔案 hash 比對圖片實在太不可靠了，改個 1 bit 資料就可以讓 hash 不同 我覺得蘋果不會做這種智障系統，否則這系統根本沒用 所以去翻了一下相關文件 看起來是用蘋果自己開發的新演算法 NeuralHash![Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloud](https://i.imgur.com/Iyu9H9Bb.png "Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloud")
12
[心得] 如何減少 GTA Online 70% 載入時間?(轉)原始文章: 如何減少 GTA Online 70% 載入時間? 作者覺得 GTA Online 載入時間機八久，因此想要一探究竟 首先作者做 benchmark 發現 Story mode load time: ~1m 10s![[心得] 如何減少 GTA Online 70% 載入時間?(轉)](https://i.imgur.com/ZHLlEDJb.png "[心得] 如何減少 GTA Online 70% 載入時間?(轉)")
4
[心得] 圖解演算法 Hash Search使用優勢與時機【圖解演算法教學】 還在用古老的二元搜尋法？是時候跟上「Hash Search」 的車尾燈了！ 封面圖： 架構圖： 在我們還沒學資料結構前，通常都用Linear Search找東西。5
Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloud六七年前在讀研究所的時候，因為主題是影像分析比對，所以有找了許多論文 我就看過幾篇google 發表的論文 透過快速比對 hash 值來快速搜尋圖片 論文中就提到他們把 原先比較距離使用的 兩個值相減平方 這類的概念 直接改成把所有資料簡化成0與1 利用 OR XOR 的方法 來高速比對 當然 論文中並沒有提到 google 是如何對圖片做hash的 或是 用什麼方法取特徵點的![Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloud](https://s4.itho.me/sites/default/files/field/image/fireshot_capture_707_-_image2.jpg_1182x367_-_1.bp_.blogspot.com_.jpg "Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloud")
2
[情報] Hash Swan-Drawing發行日 2020.11.20 發行社 GENIE MUSIC, Stone Music Entertainment 企劃社 Ambition Musik 類型 Rap / Hip-hop![[情報] Hash Swan-Drawing](https://i.imgur.com/tzP6v0Ab.jpg "[情報] Hash Swan-Drawing")
1
Re: [問卦] leetcode medium看完答案還是寫不出來千萬不要背的 原則上科技巨頭會避開網路上找得到的題目 之前被問的問題隔了五個月後才出現在leetcode 上面 要先熟悉基本的資料結構 hash map, stack, tree, trie,
![Re: [討論] 後端比前端工時更長嗎？](https://i.imgur.com/O5tUzAob.jpeg "Re: [討論] 後端比前端工時更長嗎？")