[心得] 圖解演算法 Hash Search有這麼快？

看板Tech_Job作者 (pcman)時間5年前 (2020/11/24 16:07), 5年前編輯推噓11(18推 7噓 31→)
留言56則, 24人參與, 5年前最新討論串1/1
【圖解演算法教學】 還在用古老的二元搜尋法？是時候跟上「Hash Search」 的車尾燈了！ 封面圖：https://imgur.com/8GfYiTO
架構圖：https://imgur.com/SbC5IKY
在我們還沒學資料結構前，通常都用Linear Search找東西。 之後，我們學了二元樹，開始利用二元搜尋法，大幅提升搜尋效能。 然而，在演算法的世界中： 還有比Binary Search還快的東西，即是這次要介紹的「Hash Search」！ 影片連結：https://bit.ly/2Uv2sBf 影片章節含有： 00:00 開頭 00:02 Linear Search 00:58 Binary Search 02:38 Hash Search 04:38 結尾 [更新2020.11.25] 感謝版友們提供的建議，的確有地方我可以改進，這邊直接幫大家整理出重要內容： Linear Search : BigO(n) Binary Search : BigO(n) ~ BigO(log(n)) Hash Seach : BigO(n) ~ BigO(1) 可以看到，在最佳狀況下，Hash Search的效率是最快的，一步到位。 而之所以可以做到這樣的效能，是因為Hash Seach是by Index的搜尋方式。 比如說將 29 這個數字 經過hash之後： 9 = hash(29) 就能拿到 index 9 ，我們只要去查 array[9] == 29 是否正確，就能拿到結果。 當然，現實上沒這麼理想，會遇到「碰撞」，也就是不同來源數字hash到同一個index 這部分將在後續實作中介紹，這次主要是幫大家抓到使用「Hash Search」的誘因。 最後補充，Binary Search由於會先將資料排序，所以更適合用在「範圍搜尋」。 以上內容為影片重點萃取，有需要可以進一步參考影片完整介紹，感謝各位的建議！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.110.156 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Tech_Job/M.1606205251.A.88E.html
推
11/24 16:11, 5年前 , 1F
空間換時間，跟我們肝換錢一樣
11/24 16:11, 1F
噓
11/24 16:16, 5年前 , 2F
std都寫好寫滿了
11/24 16:16, 2F
→
11/24 16:32, 5年前 , 3F
講的沒有很深，建議看 wiki
11/24 16:32, 3F
推
11/24 17:19, 5年前 , 4F
unordered_map :
11/24 17:19, 4F
推
11/24 17:28, 5年前 , 5F
感謝分享 做的很好懂 很棒
11/24 17:28, 5F
推
11/24 18:17, 5年前 , 6F
讚 訂閱 分享
11/24 18:17, 6F
噓
11/24 18:51, 5年前 , 7F
搜尋了id,相似東西一直重複po,洗文章?
11/24 18:51, 7F
推
11/24 20:14, 5年前 , 8F
奇怪 有人願意分享 不想看也不必要噓吧 是生活很不順嗎?
11/24 20:14, 8F
→
11/24 20:26, 5年前 , 9F
想來這騙流量膩 可惜我一次都沒點進去過
11/24 20:26, 9F
推
11/24 21:02, 5年前 , 10F
即使洗流量也無所謂，這種東西可以作為科普的入門阿，
11/24 21:02, 10F
→
11/24 21:02, 5年前 , 11F
如果什麼東西都說一次就會了，老師存在的價值就沒那麼
11/24 21:02, 11F
→
11/24 21:02, 5年前 , 12F
重要
11/24 21:02, 12F
推
11/24 21:17, 5年前 , 13F
上面真的一堆自覺很懂就不想複習的人呢
11/24 21:17, 13F
推
11/24 21:55, 5年前 , 14F
科普的東西很好啊 多讓台灣人瞭解科普知識是好事。 點一
11/24 21:55, 14F
→
11/24 21:55, 5年前 , 15F
次人家也賺不到0.1元
11/24 21:55, 15F
噓
11/24 22:03, 5年前 , 16F
有人家裡不順就說人不順，家裡有人掛了嗎？
11/24 22:03, 16F
→
11/24 23:24, 5年前 , 17F
如果要傳遞知識，為什麼不把內容直接放在這篇文章，最後再
11/24 23:24, 17F
→
11/24 23:24, 5年前 , 18F
補充連結，達到傳遞與導流雙重目的。而是這篇只作為導流，
11/24 23:24, 18F
→
11/24 23:24, 5年前 , 19F
不順便放知識呢。建議原PO思考一下，達到目的有時有更好的
11/24 23:24, 19F
→
11/24 23:24, 5年前 , 20F
方法。不要只學那些低級的導流方法。
11/24 23:24, 20F
→
11/24 23:26, 5年前 , 21F
另外binary search與hash適用時機不同，標題過度誇張，講
11/24 23:26, 21F
→
11/24 23:26, 5年前 , 22F
的好像binary search很落後一樣，也讓人有不專業，或只為
11/24 23:26, 22F
→
11/24 23:26, 5年前 , 23F
了賺錢的觀感。建議以後也可更聰明的表達，讓自己更專業。
11/24 23:26, 23F
→
11/24 23:28, 5年前 , 24F
總覺得這些教學文用意良好，只是被一些低級的媒體影響了傳
11/24 23:28, 24F
→
11/24 23:28, 5年前 , 25F
遞知識的方式，蠻可惜的。
11/24 23:28, 25F
→
11/24 23:34, 5年前 , 26F
最後讀者的定位也很重要，想清楚這些內容誰看，自己與讀者
11/24 23:34, 26F
→
11/24 23:34, 5年前 , 27F
的價值會最大化呢。這時候內容的品質，以及引流的channel
11/24 23:34, 27F
→
11/24 23:34, 5年前 , 28F
會更精準，少了很多負面觀感。
11/24 23:34, 28F
→
11/24 23:41, 5年前 , 29F
期待更好的內容，真的。
11/24 23:41, 29F
推
11/25 02:14, 5年前 , 30F
有辦法用正反器兜出來
11/25 02:14, 30F
推
11/25 02:17, 5年前 , 31F
有時候做影片比較好懂 文字沒這麼好懂 這種艱澀知識類的
11/25 02:17, 31F
→
11/25 02:17, 5年前 , 32F
根本賺不到錢 真的沒必要這麼嚴苛 台灣網紅一堆垃圾影
11/25 02:17, 32F
→
11/25 02:17, 5年前 , 33F
片都幾百萬點閱 不是對台灣更糟嗎
11/25 02:17, 33F
→
11/25 02:20, 5年前 , 34F
樓上說奶台是垃圾？？？？
11/25 02:20, 34F
推
11/25 04:29, 5年前 , 35F
........ 有個彈鋼琴沒露臉的居然1200萬點閱...
11/25 04:29, 35F
※ 編輯: uopsdod (101.10.110.156 臺灣), 11/25/2020 07:04:10 ※ 編輯: uopsdod (101.10.110.156 臺灣), 11/25/2020 07:04:52 ※ 編輯: uopsdod (101.10.110.156 臺灣), 11/25/2020 07:05:56
→
11/25 09:43, 5年前 , 36F
感謝原PO,的站內信回覆，真的是有心吧事情做得更好的人，
11/25 09:43, 36F
→
11/25 09:43, 5年前 , 37F
謝謝
11/25 09:43, 37F
推
11/25 10:09, 5年前 , 38F
推
11/25 10:09, 38F
推
11/25 12:01, 5年前 , 39F
噓的有什麼問題？不想看就滾
11/25 12:01, 39F
推
11/25 12:37, 5年前 , 40F
下這個標題大概不知道codeforces有很多題目
11/25 12:37, 40F
→
11/25 12:37, 5年前 , 41F
用hashmap會 timeout 用treemap反而可以AC
11/25 12:37, 41F
推
11/25 15:32, 5年前 , 42F
這個去軟體版比較合適吧
11/25 15:32, 42F
噓
11/25 16:09, 5年前 , 43F
很簡單啊，因為這版叫tech job版，不是soft job 也不
11/25 16:09, 43F
→
11/25 16:09, 5年前 , 44F
是 student 版
11/25 16:09, 44F
→
11/25 16:10, 5年前 , 45F
發錯位置當然要噓
11/25 16:10, 45F
推
11/25 17:41, 5年前 , 46F
map: 紅黑樹（二元搜尋樹的一種特例
11/25 17:41, 46F
→
11/25 17:42, 5年前 , 47F
unordered_map: hash,使用上不需要知道次序的建議選第二
11/25 17:42, 47F
→
11/25 17:42, 5年前 , 48F
種
11/25 17:42, 48F
→
11/25 17:43, 5年前 , 49F
第一種比較快但佔空間
11/25 17:43, 49F
→
11/25 20:15, 5年前 , 50F
說真的 講的太淺 大概是給高中生認識計概的程度
11/25 20:15, 50F
噓
11/26 00:18, 5年前 , 51F
衝流量啊嘻嘻
11/26 00:18, 51F
噓
11/26 06:55, 5年前 , 52F
板主不處理這種和本板無關的文，到時候就一堆商業心得
11/26 06:55, 52F
→
11/26 06:55, 5年前 , 53F
分享廣告文洗板
11/26 06:55, 53F
噓
11/26 07:06, 5年前 , 54F
你要創業那就po在創業板，po在這是在欠噓？
11/26 07:06, 54F
推
11/26 10:30, 5年前 , 55F
難得看到教學型文章，給推
11/26 10:30, 55F
推
11/26 18:00, 5年前 , 56F
這裡是半導體板
11/26 18:00, 56F
‣ 更多 uopsdod 的文章
文章代碼(AID): #1VlBz3YE (Tech_Job)