PTT評價

[心得] 圖解演算法 Hash Search有這麼快?(更新)

看板Tech_Job標題[心得] 圖解演算法 Hash Search有這麼快?(更新)作者
uopsdod
(pcman)
時間推噓12 推:19 噓:7 →:31

【圖解演算法教學】

還在用古老的二元搜尋法?是時候跟上「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 留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.110.156 (臺灣)
PTT 網址

yuci11/24 16:11空間換時間,跟我們肝換錢一樣

louisnight11/24 16:16std都寫好寫滿了

ckvir11/24 16:32講的沒有很深,建議看 wiki

leo051911/24 17:19unordered_map :

Dukkha11/24 17:28感謝分享 做的很好懂 很棒

GGFACE11/24 18:17讚 訂閱 分享

zebracoco11/24 18:51搜尋了id,相似東西一直重複po,洗文章?

nikolas11/24 20:14奇怪 有人願意分享 不想看也不必要噓吧 是生活很不順嗎?

yolasiku11/24 20:26想來這騙流量膩 可惜我一次都沒點進去過

cytochrome11/24 21:02即使洗流量也無所謂,這種東西可以作為科普的入門阿,

cytochrome11/24 21:02如果什麼東西都說一次就會了,老師存在的價值就沒那麼

cytochrome11/24 21:02重要

MrBigTree11/24 21:17上面真的一堆自覺很懂就不想複習的人呢

Dukkha11/24 21:55科普的東西很好啊 多讓台灣人瞭解科普知識是好事。 點一

Dukkha11/24 21:55次人家也賺不到0.1元

zebracoco11/24 22:03有人家裡不順就說人不順,家裡有人掛了嗎?

DrTech11/24 23:24如果要傳遞知識,為什麼不把內容直接放在這篇文章,最後再

DrTech11/24 23:24補充連結,達到傳遞與導流雙重目的。而是這篇只作為導流,

DrTech11/24 23:24不順便放知識呢。建議原PO思考一下,達到目的有時有更好的

DrTech11/24 23:24方法。不要只學那些低級的導流方法。

DrTech11/24 23:26另外binary search與hash適用時機不同,標題過度誇張,講

DrTech11/24 23:26的好像binary search很落後一樣,也讓人有不專業,或只為

DrTech11/24 23:26了賺錢的觀感。建議以後也可更聰明的表達,讓自己更專業。

DrTech11/24 23:28總覺得這些教學文用意良好,只是被一些低級的媒體影響了傳

DrTech11/24 23:28遞知識的方式,蠻可惜的。

DrTech11/24 23:34最後讀者的定位也很重要,想清楚這些內容誰看,自己與讀者

DrTech11/24 23:34的價值會最大化呢。這時候內容的品質,以及引流的channel

DrTech11/24 23:34會更精準,少了很多負面觀感。

DrTech11/24 23:41期待更好的內容,真的。

labbat11/25 02:14有辦法用正反器兜出來

Dukkha11/25 02:17 有時候做影片比較好懂 文字沒這麼好懂 這種艱澀知識類的

Dukkha11/25 02:17 根本賺不到錢 真的沒必要這麼嚴苛 台灣網紅一堆垃圾影

Dukkha11/25 02:17片都幾百萬點閱 不是對台灣更糟嗎

loadingN11/25 02:20樓上說奶台是垃圾????

Dukkha11/25 04:29........ 有個彈鋼琴沒露臉的居然1200萬點閱...

※ 編輯: 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

DrTech11/25 09:43感謝原PO,的站內信回覆,真的是有心吧事情做得更好的人,

DrTech11/25 09:43謝謝

ken77120911/25 10:09

RedDracula11/25 12:01噓的有什麼問題?不想看就滾

jcaosola11/25 12:37下這個標題大概不知道codeforces有很多題目

jcaosola11/25 12:37用hashmap會 timeout 用treemap反而可以AC

stosto11/25 15:32這個去軟體版比較合適吧

jpopaholic11/25 16:09很簡單啊,因為這版叫tech job版,不是soft job 也不

jpopaholic11/25 16:09是 student 版

jpopaholic11/25 16:10發錯位置當然要噓

yamakazi11/25 17:41map: 紅黑樹(二元搜尋樹的一種特例

yamakazi11/25 17:42unordered_map: hash,使用上不需要知道次序的建議選第二

yamakazi11/25 17:42

yamakazi11/25 17:43第一種比較快但佔空間

bitcch11/25 20:15說真的 講的太淺 大概是給高中生認識計概的程度

j095832208011/26 00:18衝流量啊嘻嘻

zebracoco11/26 06:55板主不處理這種和本板無關的文,到時候就一堆商業心得

zebracoco11/26 06:55分享廣告文洗板

zebracoco11/26 07:06你要創業那就po在創業板,po在這是在欠噓?

arthas1111/26 10:30難得看到教學型文章,給推

new12285111/26 18:00這裡是半導體板

RestInPips11/30 23:10