歡迎光臨
每天分享高質量文章

演算法怎麼學?微博熱議

(給演算法愛好者加星標,修煉編程內功

作者:@jolestar

綜合整理:「演算法愛好者」(id: AlgorithmFans)已獲授權

一個剛畢業沒多久的朋友面試後,給我說面試官問了垃圾回收演算法相關的問題,他回答的不好。

 

我接著問了他幾個演算法相關問題,發現他回答的時候在努力回憶看過的書以及代碼細節,沒把握住關鍵點。

 

很多新手朋友都有這種問題,遇到演算法類的問題就覺得複雜,敬而怕之。實際上演算法就是解決問題的一系列可精確描述的步驟,日常生活中也遇到,只是要求沒那麼精確罷了。

 

比如垃圾回收的問題,你就假設自己要打掃房子,但房子里還有人活動,再不斷製造垃圾,你怎麼打掃?

 

最簡單粗暴的辦法就是把人趕出去,打掃完了再進來。這就是所謂的 stop world 樣式。如果你打掃的足夠快,這種辦法其實也可以用。

 

那如果房間比較大,垃圾比較多,這種辦法不可接受怎麼辦?你發現打掃衛生的時候時間耗費在判斷一個東西是不是垃圾上了。於是你想了個辦法,先把每個垃圾都打上標記,標記完了再 stop world,快速清理。這就是所謂的 Mark-Sweep。

 

那如果垃圾和有用的東西混雜在一起,即使清理完屋裡也亂糟糟的怎麼辦?那就順便整理下唄。先騰出一塊空間,把有用的東西搬到那邊整理好。其他的垃圾清理掉。這就是所謂的 Copying 整理演算法。

 

那如果空間本來就小,弄一塊空的空間不容易呢?那就把上面兩個辦法結合下唄,一遍標記一遍整理。就是所謂的 Mark-Compact 演算法。

 

再後面的優化就是能不能分成不同的區域用不同的演算法(分代)?如果你再請幾個幫手來一起打掃會如何進行(併發)?雖然越來越複雜,但理解了前面的問題,它的優化點也就容易理解。

 

所以要學習演算法,先要用平常心待之,以常識推理,前面這些演算法,你找個打掃衛生的阿姨,把場景描述清楚,她大概也能想出差不多的辦法吧。先用從簡單粗暴的方法入手,再進一步理解優化細節,不要一開始就陷入了細節中去。有的人能從解決純演算法問題中尋求到快感,還有一種人對純演算法問題無感(比如我),就要把演算法和真實問題場景結合起來,和實際應用結合起來。

 

網友評論

 

@平成最後的號 :我一個同事,進來的時候面試,其實他基本不懂GC演算法,當場硬是在我們PE的引導下自己幾乎造出來了generational GC的remembered sets

 

@工業聚:這事兒得看天分。生活中大多數人都是排序高手,冒泡排序,快速排序,插入排序,歸併排序按需靈活運用。但要變成代碼等形式化的、抽象表達的場景,其演算法能力難以啟動。正常人都理解如何下山,卻離理解機器學習里的梯度下降還很遠。我們都有智慧/內置演算法,但要將它們賦於機器/代碼,可不簡單

 

@但丁不淡定: 我倒是覺得因果反了。稍微學過點演算法的才有把現實世界的事務對應成流程的邏輯,而不是從現實的邏輯尋找演算法的靈感。舉個例子,你房間里椅子上的衣服,瞭解過 LRU 的才知道先從底部的清理起…

 

@鄧草原:在做 kesque 的 compaction,要充分利用記憶體,演算法是:先把有用的記錄複製到硬碟新空間,邊把記憶體中這些記錄的索引也轉指新空間,過程中不影響使用。最後要清理的垃圾,硬碟上的舊空間直接刪除,而記憶體索引還指向舊空間的,先 stop world,然後遍歷一遍移走。邊開車邊換輪胎。演算法是一次夢醒後確定的。

 

@AshleySean:我希望我有這樣的老師雖然我知道挑老師很不對 但我真的是那種會看老師學習的人 什麼時候才能改啊我的學習生涯什麼時候才能真正變得主動啊

    赞(0)

    分享創造快樂