大數(shù)據(jù)時(shí)代 無(wú)處不在的算法應(yīng)用

能不能講講算法在工作中的運(yùn)用?你個(gè)人學(xué)習(xí)算法的過(guò)程是怎樣的?我對(duì)算法還是有點(diǎn)怕。除此之外，你認(rèn)為大學(xué)是應(yīng)該多花時(shí)間學(xué)應(yīng)用技術(shù)還是理論知識(shí)呢?

今天就來(lái)聊聊我自己學(xué)習(xí)算法的過(guò)程，以及算法在實(shí)際工作中的應(yīng)用。

以前，我們認(rèn)為大數(shù)據(jù)總是優(yōu)于好算法。也就是說(shuō)，只要數(shù)據(jù)量足夠大，即使算法沒(méi)有那么好，也會(huì)產(chǎn)生好的結(jié)果。

前一陣子“極客時(shí)間” App 發(fā)布了一條極客新聞：“算法比數(shù)據(jù)更重要，AlphaGo Zero 完勝舊版?！毙侣劦膬?nèi)容是谷歌人工智能團(tuán)隊(duì) DeepMind 發(fā)布了新版的 AlphaGo 計(jì)算機(jī)程序，名為 AlphaGo Zero。這款軟件能夠從空白狀態(tài)開(kāi)始，不需要人類輸入任何命令，便可以迅速自學(xué)圍棋，并以 100 比 0 的戰(zhàn)績(jī)擊敗了上一代 AlphaGo。

AlphaGo Zero 最大的突破在于實(shí)現(xiàn)了“白板理論”。白板理論認(rèn)為：嬰兒是一塊白板，可以通過(guò)后天學(xué)習(xí)和訓(xùn)練來(lái)提高智力。AI 的先驅(qū)圖靈認(rèn)為，只要能用機(jī)器制造一個(gè)類似于小孩的 AI，然后加以訓(xùn)練，就能得到一個(gè)近似成人智力，甚至超越人類智力的 AI。

自學(xué)成才的 AlphaGo Zero 正是實(shí)現(xiàn)了這一理論。AlphaGo 的首席研究員大衛(wèi)·席爾瓦(David Silver)認(rèn)為，從 AlphaGo Zero 中可以發(fā)現(xiàn)，算法比所謂的計(jì)算或數(shù)據(jù)量更為重要。事實(shí)上，AlphaGo Zero 使用的計(jì)算要比過(guò)去的版本少一個(gè)數(shù)量級(jí)，但是因?yàn)槭褂昧烁嘣砗退惴?，它的性能反而更加?qiáng)大。

由此可見(jiàn)，在大數(shù)據(jù)時(shí)代，算法的重要性日漸明晰。一個(gè)合格的程序員，必須掌握算法。

我不知道大家是怎樣一步步開(kāi)始精通算法和數(shù)據(jù)結(jié)構(gòu)的。大二時(shí)，我第一次接觸到了《數(shù)據(jù)結(jié)構(gòu)》，因?yàn)閺膩?lái)沒(méi)有過(guò)這方面的思維訓(xùn)練，當(dāng)時(shí)的我學(xué)習(xí)這門課比較費(fèi)力。那時(shí)候接觸到的編程比較少，所以并沒(méi)有很多實(shí)際經(jīng)驗(yàn)讓我欣賞和體味：一個(gè)好的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)到底 “美” 在哪里。

開(kāi)始學(xué)習(xí)的時(shí)候，我甚至有點(diǎn)死記硬背的感覺(jué)，我并不知道 “如果不這樣設(shè)計(jì)”，實(shí)際上會(huì)出現(xiàn)哪些問(wèn)題。各種時(shí)間和空間復(fù)雜度對(duì)我而言，也僅僅是一些不能融入到實(shí)際問(wèn)題的數(shù)學(xué)游戲。至于“每種最壞情況、平均情況的時(shí)間空間復(fù)雜度與各種排序”，這些內(nèi)容為什么那么重要，當(dāng)時(shí)我想，可能因?yàn)榭荚嚂?huì)考吧。

沒(méi)想到后來(lái)的時(shí)日，我又與算法重新結(jié)緣。可能是因?yàn)槿R斯大學(xué)給的獎(jiǎng)學(xué)金太高了，所以每個(gè)研究生需要無(wú)償當(dāng)五個(gè)學(xué)期的助教 。好巧不巧，我又被算法老師兩次挑中當(dāng)助教。所以，在命運(yùn)強(qiáng)制下，一本《算法導(dǎo)論》就這樣被我前前后后仔細(xì)學(xué)習(xí)了不下四遍。這樣的結(jié)果是，我基本做過(guò)整本書(shū)的習(xí)題，有些還不止做了一遍。我學(xué)習(xí)算法的過(guò)程，就是反復(fù)閱讀《算法導(dǎo)論》的過(guò)程。

那么，學(xué)習(xí)算法到底有什么用處呢?

首先，算法是面試的敲門磚國(guó)內(nèi)的情況我不太清楚，但就硅谷的 IT 公司而言，不但電話面試偏算法，現(xiàn)場(chǎng)面試至少有兩輪都是考算法和編程的。

大一些老一些的公司，像谷歌、Facebook、領(lǐng)英、Dropbox 等，都是直接在白板上寫(xiě)程序。小一些新一些的公司，如 Square、Airbnb 等，都是需要現(xiàn)場(chǎng)上機(jī)寫(xiě)出可運(yùn)行的程序。Twitter、Uber 等公司則是白板上機(jī)兼?zhèn)?，視情況而定。

雖說(shuō)還有其它考系統(tǒng)設(shè)計(jì)等部分，但如果算法沒(méi)有打好基礎(chǔ)，第一關(guān)就很難過(guò)，而且算法要熟悉到能夠現(xiàn)場(chǎng)短時(shí)間內(nèi)寫(xiě)出正解，所以很多人準(zhǔn)備面試前都需要刷題。

有一次我當(dāng)面試官，電話面試另外一個(gè)人，當(dāng)時(shí)是用 Codepad 共享的方式，讓對(duì)方寫(xiě)一個(gè)可運(yùn)行的正則表達(dá)式解析器。45 分鐘過(guò)去了，對(duì)方并沒(méi)有寫(xiě)出來(lái)。我就例行公事地問(wèn)：“你還有什么問(wèn)題想問(wèn)或者想了解么?” 對(duì)方估計(jì)因?yàn)閷?xiě)不出程序很有挫敗感，就反問(wèn)：“你們平時(shí)工作難道就是天天寫(xiě)正則表達(dá)式的解析器么?”

一瞬間，我竟無(wú)言以對(duì)。想了想，我回復(fù)說(shuō)：“不用天天寫(xiě)。那我再給你 15 分鐘，你證明給我看你還會(huì)什么，或者有什么理由讓我給你進(jìn)一步面試的機(jī)會(huì)?” 對(duì)方想了一會(huì)，默默掛掉了電話。

老實(shí)說(shuō)，我對(duì)目前面試中偏重算法的程度是持保留意見(jiàn)的。算法題答得好，并不能說(shuō)明你有多牛。牛人也有因?yàn)椴辉杆㈩}而馬失前蹄的時(shí)候。但是除了算法測(cè)試，顯然也沒(méi)有更好的方法佐證候選人的實(shí)力;然而怎樣才能最優(yōu)化面試流程，這也是個(gè)討論起來(lái)沒(méi)完的話題，并且每次討論必定無(wú)果而終。

其次，編程時(shí)用到的更多是算法思想，而不是寫(xiě)具體的算法說(shuō)到實(shí)際工作中真正需要使用算法的機(jī)會(huì)，讓我想一想 —— 這個(gè)范圍應(yīng)該在 10% 的附近游走。

有些朋友在工作中遇到算法場(chǎng)景多些，有的少些。更多的時(shí)候，是對(duì)業(yè)務(wù)邏輯的理解，對(duì)程序語(yǔ)言各種特性的熟練使用，對(duì)代碼風(fēng)格和模式的把握，各種同步異步的處理，包括代碼測(cè)試、系統(tǒng)部署是否正規(guī)化等等。需要設(shè)計(jì)甚至實(shí)現(xiàn)一個(gè)算法的機(jī)會(huì)確實(shí)很少，即使用到，現(xiàn)學(xué)可能都來(lái)得及。

但是熟悉基本算法的好處在于：如果工作需要讀的一段代碼中包含一些基本算法思想，你會(huì)比不懂算法的人理解代碼含義更快。讀到一段爛代碼，你知道為什么爛，爛在哪，怎么去優(yōu)化。

當(dāng)真的需要在程序中設(shè)計(jì)算法的時(shí)候，熟悉算法的你會(huì)給出一個(gè)更為完備的方案，對(duì)程序中出現(xiàn)的算法或比較復(fù)雜的時(shí)間復(fù)雜度問(wèn)題你會(huì)更有敏感性。熟悉算法你還可以成為一個(gè)更優(yōu)秀的面試官，可以和別的工程師聊天時(shí)候不被鄙視。

最后，不精通算法的工程師永遠(yuǎn)不是好工程師當(dāng)然，除了算法導(dǎo)論中那些已成為經(jīng)典的基本算法以及算法思想(Divide-and-conquer，Dynamic programming)等，其實(shí)我們每天接觸到的各種技術(shù)中，算法無(wú)處不在。

就拿人人都會(huì)接觸的存儲(chǔ)為例吧，各種不同的數(shù)據(jù)庫(kù)或者鍵值存儲(chǔ)的實(shí)現(xiàn)，就會(huì)涉及各種分片(Sharding)算法、緩存失敗(Cache Invalidation)算法、 鎖定(Locking)算法，包括各種容錯(cuò)算法(多復(fù)制的同步算法)。 雖然說(shuō)平時(shí)不太會(huì)去寫(xiě)這些算法 —— 除非你恰恰是做數(shù)據(jù)庫(kù)實(shí)現(xiàn)的 —— 但是真正做到了解這項(xiàng)技術(shù)的算法細(xì)節(jié)和實(shí)現(xiàn)細(xì)節(jié)，無(wú)論對(duì)于技術(shù)選型還是對(duì)自己程序的整體性能評(píng)估都是至關(guān)重要的。

舉個(gè)例子，當(dāng)你在系統(tǒng)里需要一個(gè)鍵值存儲(chǔ)方案的時(shí)候，面對(duì)可供選擇的各種備選方案，到底應(yīng)該選擇哪一種呢?

永遠(yuǎn)沒(méi)有一種方案在所有方面都是最佳的。就拿 Facebook 開(kāi)源的 RocksDB 來(lái)說(shuō)吧。了解它歷史的人都知道，RocksDB 是構(gòu)建在 LevelDB 之上的，可以在多 CPU 服務(wù)器上高效運(yùn)行的一種鍵值存儲(chǔ)。而 LevelDB 又是基于谷歌的 BigTable 數(shù)據(jù)庫(kù)系統(tǒng)概念設(shè)計(jì)的。

早在 2004 年，谷歌開(kāi)始開(kāi)發(fā) BigTable，其代碼大量的依賴谷歌內(nèi)部的代碼庫(kù)，雖然 BigTable 很牛，卻因此無(wú)法開(kāi)源。2011 年，谷歌的杰夫·迪恩和桑杰·格瑪沃爾特開(kāi)始基于 BigTable 的思想，重新開(kāi)發(fā)一個(gè)開(kāi)源的類似系統(tǒng)，并保證做到不用任何谷歌的代碼庫(kù)，于是就有了 LevelDB。這樣一個(gè)鍵值存儲(chǔ)的實(shí)現(xiàn)也用在了谷歌瀏覽器的 IndexedDB 中，對(duì)于谷歌瀏覽器的開(kāi)源也提供了一定的支持。

我曾經(jīng)在文章中提到過(guò) CockroachDB，其實(shí)又可以看作是基于 RocksDB 之上的一個(gè)分布式實(shí)現(xiàn)。從另一個(gè)層面上講，CockroachDB 又可以說(shuō)是 Spanner 的一個(gè)開(kāi)源實(shí)現(xiàn)。知道這些，就知道這些數(shù)據(jù)庫(kù)或鍵值存儲(chǔ)其實(shí)都同出一系。再來(lái)看看 LevelDB 底層的 SSTable 算法，就知道他們都是針對(duì)高吞吐量(high throughput)，順序讀 / 寫(xiě)工作負(fù)載(sequential read/write workloads)有效的存儲(chǔ)系統(tǒng)。

當(dāng)然，一個(gè)系統(tǒng)里除了最基本的算法，很多的實(shí)現(xiàn)細(xì)節(jié)和系統(tǒng)架構(gòu)都會(huì)對(duì)性能及應(yīng)用有很大的影響。然而，對(duì)算法本身的理解和把握，永遠(yuǎn)是深入了解系統(tǒng)不可或缺的一環(huán)。

類似的例子還有很多，比如日志分析、打車軟件的調(diào)度算法。

拿我比較熟悉的支付領(lǐng)域來(lái)說(shuō)吧，比如信用卡 BIN 參數(shù)的壓縮，從服務(wù)端到移動(dòng) App 的數(shù)據(jù)傳輸，為了讓傳輸數(shù)據(jù)足夠小，需要對(duì)數(shù)據(jù)進(jìn)行壓縮編碼。

每個(gè)國(guó)家，比如中國(guó)、韓國(guó)、墨西哥信用卡前綴格式都不一樣，如何盡量壓縮同時(shí)又不會(huì)太復(fù)雜，以至于影響移動(dòng) App 端的代碼復(fù)雜度，甚至形成 Bug 等，也需要對(duì)各種相關(guān)算法有詳盡地了解，才有可能做出最優(yōu)的方案。

關(guān)于算法我們來(lái)總結(jié)一下：

在大數(shù)據(jù)時(shí)代，數(shù)據(jù)和算法都同等重要，甚至算法比計(jì)算能力或數(shù)據(jù)量更為重要。

如何學(xué)習(xí)算法呢?讀經(jīng)典著作、做題，然后在實(shí)踐中閱讀和使用算法。

算法是面試的敲門磚，可以幫助你得到一份自己喜歡的工作。

寫(xiě)程序中用到的更多是算法思想，不是寫(xiě)具體的算法。

不精通算法的工程師永遠(yuǎn)不會(huì)是一個(gè)優(yōu)秀的工程師，只有對(duì)各種相關(guān)算法有詳盡理解，才有可能做出最優(yōu)的方案。