轉(zhuǎn)自：http://kaifu163tech.blog.163.com/blog/static/54381270200812041447221/

算法是計(jì)算機(jī)科學(xué)領(lǐng)域最重要的基石之一，但卻受到了國(guó)內(nèi)一些程序員的冷落。許多學(xué)生看到一些公司在招聘時(shí)要求的編程語(yǔ)言五花八門，就產(chǎn)生了一種誤解，認(rèn)為學(xué)計(jì)算機(jī)就是學(xué)各種編程語(yǔ)言，或者認(rèn)為，學(xué)習(xí)最新的語(yǔ)言、技術(shù)、標(biāo)準(zhǔn)就是最好的鋪路方法。其實(shí)，大家被這些公司誤導(dǎo)了。編程語(yǔ)言雖然該學(xué)，但是學(xué)習(xí)計(jì)算機(jī)算法和理論更重要，因?yàn)橛?jì)算機(jī)語(yǔ)言和開發(fā)平臺(tái)日新月異，但萬(wàn)變不離其宗的是那些算法和理論，例如數(shù)據(jù)結(jié)構(gòu)、算法、編譯原理、計(jì)算機(jī)體系結(jié)構(gòu)、關(guān)系型數(shù)據(jù)庫(kù)原理等等。在“開復(fù)學(xué)生網(wǎng)”上，有位同學(xué)生動(dòng)地把這些基礎(chǔ)課程比擬為“內(nèi)功”，把新的語(yǔ)言、技術(shù)、標(biāo)準(zhǔn)比擬為“外功”。整天趕時(shí)髦的人最后只懂得招式，沒(méi)有功力，是不可能成為高手的。

算法與我

當(dāng)我在1980年轉(zhuǎn)入計(jì)算機(jī)科學(xué)系時(shí)，還沒(méi)有多少人的專業(yè)方向是計(jì)算機(jī)科學(xué)。有許多其他系的人嘲笑我們說(shuō)：“知道為什么只有你們系要加一個(gè)‘科學(xué)’，而沒(méi)有‘物理科學(xué)系’或‘化學(xué)科學(xué)系’嗎？因?yàn)槿思沂钦娴目茖W(xué),不需要畫蛇添足，而你們自己心虛，生怕不‘科學(xué)’，才這樣欲蓋彌彰。” 其實(shí)，這點(diǎn)他們徹底弄錯(cuò)了。真正學(xué)懂計(jì)算機(jī)的人（不只是“編程匠”）都對(duì)數(shù)學(xué)有相當(dāng)?shù)脑煸劊饶苡每茖W(xué)家的嚴(yán)謹(jǐn)思維來(lái)求證，也能用工程師的務(wù)實(shí)手段來(lái)解決問(wèn)題——而這種思維和手段的最佳演繹就是“算法”。

記得我讀博時(shí)寫的Othello對(duì)弈軟件獲得了世界冠軍。當(dāng)時(shí)，得第二名的人認(rèn)為我是靠?jī)e幸才打贏他，不服氣地問(wèn)我的程序平均每秒能搜索多少步棋，當(dāng)他發(fā)現(xiàn)我的軟件在搜索效率上比他快60多倍時(shí)，才徹底服輸。為什么在同樣的機(jī)器上，我可以多做 60倍的工作呢？這是因?yàn)槲矣昧艘粋€(gè)最新的算法，能夠把一個(gè)指數(shù)函數(shù)轉(zhuǎn)換成四個(gè)近似的表，只要用常數(shù)時(shí)間就可得到近似的答案。在這個(gè)例子中，是否用對(duì)算法才是能否贏得世界冠軍的關(guān)鍵。

還記得1988年貝爾實(shí)驗(yàn)室副總裁親自來(lái)訪問(wèn)我的學(xué)校，目的就是為了想了解為什么他們的語(yǔ)音識(shí)別系統(tǒng)比我開發(fā)的慢幾十倍，而且，在擴(kuò)大至大詞匯系統(tǒng)后，速度差異更有幾百倍之多。他們雖然買了幾臺(tái)超級(jí)計(jì)算機(jī)，勉強(qiáng)讓系統(tǒng)跑了起來(lái)，但這么貴的計(jì)算資源讓他們的產(chǎn)品部門很反感，因?yàn)?#8220;昂貴”的技術(shù)是沒(méi)有應(yīng)用前景的。在與他們探討的過(guò)程中，我驚訝地發(fā)現(xiàn)一個(gè)O(n*m)的動(dòng)態(tài)規(guī)劃（dynamic programming）居然被他們做成了O(n*n*m)。更驚訝的是，他們還為此發(fā)表了不少文章，甚至為自己的算法起了一個(gè)很特別的名字，并將算法提名到一個(gè)科學(xué)會(huì)議里，希望能得到大獎(jiǎng)。當(dāng)時(shí)，貝爾實(shí)驗(yàn)室的研究員當(dāng)然絕頂聰明，但他們?nèi)际菍W(xué)數(shù)學(xué)、物理或電機(jī)出身，從未學(xué)過(guò)計(jì)算機(jī)科學(xué)或算法，才犯了這么基本的錯(cuò)誤。我想那些人以后再也不會(huì)嘲笑學(xué)計(jì)算機(jī)科學(xué)的人了吧!

網(wǎng)絡(luò)時(shí)代的算法

有人也許會(huì)說(shuō)：“今天計(jì)算機(jī)這么快，算法還重要嗎?”其實(shí)永遠(yuǎn)不會(huì)有太快的計(jì)算機(jī)，因?yàn)槲覀兛倳?huì)想出新的應(yīng)用。雖然在摩爾定律的作用下，計(jì)算機(jī)的計(jì)算能力每年都在飛快增長(zhǎng)，價(jià)格也在不斷下降。可我們不要忘記，需要處理的信息量更是呈指數(shù)級(jí)的增長(zhǎng)。現(xiàn)在每人每天都會(huì)創(chuàng)造出大量數(shù)據(jù)（照片，視頻，語(yǔ)音，文本等等）。日益先進(jìn)的記錄和存儲(chǔ)手段使我們每個(gè)人的信息量都在爆炸式的增長(zhǎng)。互聯(lián)網(wǎng)的信息流量和日志容量也在飛快增長(zhǎng)。在科學(xué)研究方面，隨著研究手段的進(jìn)步，數(shù)據(jù)量更是達(dá)到了前所未有的程度。無(wú)論是三維圖形、海量數(shù)據(jù)處理、機(jī)器學(xué)習(xí)、語(yǔ)音識(shí)別，都需要極大的計(jì)算量。在網(wǎng)絡(luò)時(shí)代，越來(lái)越多的挑戰(zhàn)需要靠卓越的算法來(lái)解決。

再舉另一個(gè)網(wǎng)絡(luò)時(shí)代的例子。在互聯(lián)網(wǎng)和手機(jī)搜索上，如果要找附近的咖啡店，那么搜索引擎該怎么處理這個(gè)請(qǐng)求呢?

最簡(jiǎn)單的辦法就是把整個(gè)城市的咖啡館都找出來(lái),然后計(jì)算出它們的所在位置與你之間的距離,再進(jìn)行排序,然后返回最近的結(jié)果。但該如何計(jì)算距離呢？圖論里有不少算法可以解決這個(gè)問(wèn)題。

這么做也許是最直觀的，但絕對(duì)不是最迅速的。如果一個(gè)城市只有為數(shù)不多的咖啡館,那這么做應(yīng)該沒(méi)什么問(wèn)題,反正計(jì)算量不大。但如果一個(gè)城市里有很多咖啡館,又有很多用戶都需要類似的搜索,那么服務(wù)器所承受的壓力就大多了。在這種情況下,我們?cè)撛鯓觾?yōu)化算法呢?

首先，我們可以把整個(gè)城市的咖啡館做一次“預(yù)處理”。比如，把一個(gè)城市分成若干個(gè)“格子(grid)”,然后根據(jù)用戶所在的位置把他放到某一個(gè)格子里，只對(duì)格子里的咖啡館進(jìn)行距離排序。

問(wèn)題又來(lái)了，如果格子大小一樣，那么絕大多數(shù)結(jié)果都可能出現(xiàn)在市中心的一個(gè)格子里，而郊區(qū)的格子里只有極少的結(jié)果。在這種情況下，我們應(yīng)該把市中心多分出幾個(gè)格子。更進(jìn)一步，格子應(yīng)該是一個(gè)“樹結(jié)構(gòu)”，最頂層是一個(gè)大格——整個(gè)城市，然后逐層下降，格子越來(lái)越小，這樣有利于用戶進(jìn)行精確搜索——如果在最底層的格子里搜索結(jié)果不多，用戶可以逐級(jí)上升，放大搜索范圍。

上述算法對(duì)咖啡館的例子很實(shí)用，但是它具有通用性嗎？答案是否定的。把咖啡館抽象一下，它是一個(gè)“點(diǎn)”，如果要搜索一個(gè)“面”該怎么辦呢？比如，用戶想去一個(gè)水庫(kù)玩，而一個(gè)水庫(kù)有好幾個(gè)入口，那么哪一個(gè)離用戶最近呢？這個(gè)時(shí)候，上述“樹結(jié)構(gòu)”就要改成“r-tree”,因?yàn)闃渲虚g的每一個(gè)節(jié)點(diǎn)都是一個(gè)范圍，一個(gè)有邊界的范圍（參考：http://www.cs.umd.edu/~hjs/rtrees/index.html）。

通過(guò)這個(gè)小例子，我們看到，應(yīng)用程序的要求千變?nèi)f化，很多時(shí)候需要把一個(gè)復(fù)雜的問(wèn)題分解成若干簡(jiǎn)單的小問(wèn)題，然后再選用合適的算法和數(shù)據(jù)結(jié)構(gòu)。

并行算法：Google的核心優(yōu)勢(shì)

上面的例子在Google里就要算是小case了！每天Google的網(wǎng)站要處理十億個(gè)以上的搜索，GMail要儲(chǔ)存幾千萬(wàn)用戶的2G郵箱，Google Earth要讓數(shù)十萬(wàn)用戶同時(shí)在整個(gè)地球上遨游，并將合適的圖片經(jīng)過(guò)互聯(lián)網(wǎng)提交給每個(gè)用戶。如果沒(méi)有好的算法，這些應(yīng)用都無(wú)法成為現(xiàn)實(shí)。

在這些的應(yīng)用中，哪怕是最基本的問(wèn)題都會(huì)給傳統(tǒng)的計(jì)算帶來(lái)很大的挑戰(zhàn)。例如，每天都有十億以上的用戶訪問(wèn)Google的網(wǎng)站，使用Google的服務(wù)，也產(chǎn)生很多很多的日志（Log）。因?yàn)長(zhǎng)og每分每秒都在飛速增加，我們必須有聰明的辦法來(lái)進(jìn)行處理。我曾經(jīng)在面試中問(wèn)過(guò)關(guān)于如何對(duì)log進(jìn)行一些分析處理的問(wèn)題，有很多面試者的回答雖然在邏輯上正確，但在實(shí)際應(yīng)用中是幾乎不可行的。按照他們的算法，即便用上幾萬(wàn)臺(tái)機(jī)器，我們的處理速度都跟不上數(shù)據(jù)產(chǎn)生的速度。

那么Google是如何解決這些問(wèn)題的呢？

首先，在網(wǎng)絡(luò)時(shí)代，就算有最好的算法，也要能在并行計(jì)算的環(huán)境下執(zhí)行。在Google的數(shù)據(jù)中心，我們使用的是超大的并行計(jì)算機(jī)。但傳統(tǒng)的并行算法運(yùn)行時(shí)，效率會(huì)在增加機(jī)器數(shù)量后迅速降低，也就是說(shuō)，十臺(tái)機(jī)器如果有五倍的效果，增加到一千臺(tái)時(shí)也許就只有幾十倍的效果。這種事倍功半的代價(jià)是沒(méi)有哪家公司可以負(fù)擔(dān)得起的。而且，在許多并行算法中，只要一個(gè)結(jié)點(diǎn)犯錯(cuò)誤，所有計(jì)算都會(huì)前功盡棄。

那么Google是如何開發(fā)出既有效率又能容錯(cuò)的并行計(jì)算的呢？

Google最資深的計(jì)算機(jī)科學(xué)家Jeff Dean認(rèn)識(shí)到， Google 所需的絕大部分?jǐn)?shù)據(jù)處理都可以歸結(jié)為一個(gè)簡(jiǎn)單的并行算法：Map and Reduce（http://labs.google.com/papers/mapreduce.html）。這個(gè)算法能夠在很多種計(jì)算中達(dá)到相當(dāng)高的效率，而且是可擴(kuò)展的（也就是說(shuō)，一千臺(tái)機(jī)器就算不能達(dá)到一千倍的效果，至少也可以達(dá)到幾百倍的效果）。Map and Reduce的另外一大特色是它可以利用大批廉價(jià)的機(jī)器組成功能強(qiáng)大的server farm。最后，它的容錯(cuò)性能異常出色，就算一個(gè)server farm里面的機(jī)器down掉一半，整個(gè)farm依然能夠運(yùn)行。正是因?yàn)檫@個(gè)天才的認(rèn)識(shí),才有了Map and Reduce算法。借助該算法，Google幾乎能無(wú)限地增加計(jì)算量，與日新月異的互聯(lián)網(wǎng)應(yīng)用一同成長(zhǎng)。

算法并不局限于計(jì)算機(jī)和網(wǎng)絡(luò)

舉一個(gè)計(jì)算機(jī)領(lǐng)域外的例子：在高能物理研究方面，很多實(shí)驗(yàn)每秒鐘都產(chǎn)生幾個(gè)TB的數(shù)據(jù)量。但因?yàn)樘幚砟芰痛鎯?chǔ)能力的不足，科學(xué)家不得不把絕大部分未經(jīng)處理的數(shù)據(jù)丟棄掉。可大家要知道，新元素的信息很有可能就藏在我們來(lái)不及處理的數(shù)據(jù)里面。同樣的，在其他任何領(lǐng)域里，算法都可以改變?nèi)祟惖纳睢＠缛祟惢虻难芯浚涂赡芤驗(yàn)樗惴ǘl(fā)明新的醫(yī)療方式。在國(guó)家安全領(lǐng)域，有效的算法可能避免下一個(gè) 911的發(fā)生。在氣象方面，算法可以更好地預(yù)測(cè)未來(lái)天災(zāi)的發(fā)生，以拯救生命。

所以，如果你把計(jì)算機(jī)的發(fā)展放到應(yīng)用和數(shù)據(jù)飛速增長(zhǎng)的大環(huán)境下，你一定會(huì)發(fā)現(xiàn)，算法的重要性不是在日益減小，而是在日益加強(qiáng)。

給程序員的七個(gè)建議

（1）練內(nèi)功。不要只花功夫?qū)W習(xí)各種流行的編程語(yǔ)言和工具，以及某些公司招聘廣告上要求的科目。要把數(shù)據(jù)結(jié)構(gòu)、算法、數(shù)據(jù)庫(kù)、操作系統(tǒng)原理、計(jì)算機(jī)體系結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)，離散數(shù)學(xué)等基礎(chǔ)課程學(xué)好。大家不妨試試高德納所著The Art of Computer Programming里的題目，如果你能夠解決其中的大部分題目，就說(shuō)明你在算法方面有一定的功力了。

（2）多實(shí)戰(zhàn)。通過(guò)編程的實(shí)戰(zhàn)積累經(jīng)驗(yàn)、鞏固知識(shí)。很多中國(guó)大學(xué)畢業(yè)生缺乏編程和調(diào)試經(jīng)驗(yàn)；學(xué)習(xí)C語(yǔ)言，考試過(guò)關(guān)就算學(xué)會(huì)了；課題項(xiàng)目中，只要程序能夠編譯，運(yùn)行，并且輸入輸出滿足要求就算了事。這些做法是不行的。寫程序的時(shí)候，大家必須多想想如何把程序?qū)懙酶泳珶挕⒏咝А⒏哔|(zhì)量。建議大家爭(zhēng)取在大學(xué)四年中積累編寫十萬(wàn)行代碼的經(jīng)驗(yàn)。我們必須明白的是：好程序員是寫出來(lái)的，不是學(xué)出來(lái)的。

（3）求實(shí)干。不要輕視任何實(shí)際工作，比如一些看似簡(jiǎn)單的編碼或測(cè)試。要不懈追求對(duì)細(xì)節(jié)一絲不茍的實(shí)干作風(fēng)與敬業(yè)精神。我發(fā)現(xiàn)不少程序員對(duì)于知識(shí)的掌握很膚淺，不求甚解，沒(méi)有好奇心，不會(huì)刨根問(wèn)底。比如，學(xué)會(huì)了C++，是否了解一個(gè)對(duì)象在編譯后，在匯編代碼中是如何被初始化的？這個(gè)對(duì)象的各個(gè)成員在內(nèi)存中是如何存放的？當(dāng)一個(gè)成員函數(shù)被調(diào)用時(shí)，編譯器在匯編代碼中加入了哪些額外的動(dòng)作？虛函數(shù)的調(diào)用是如何實(shí)現(xiàn)的? 這些東西恐怕在編程語(yǔ)言或編譯原理中都沒(méi)有詳細(xì)提到，只有通過(guò)踏實(shí)的實(shí)干才能真正掌握。

（4）重視數(shù)學(xué)學(xué)習(xí)。數(shù)學(xué)是思維的體操，數(shù)學(xué)無(wú)處不在。學(xué)計(jì)算機(jī)至少要學(xué)習(xí)離散數(shù)學(xué)、概率論、布爾代數(shù)、集合論和數(shù)理邏輯。這些知識(shí)并不難，但是對(duì)你未來(lái)的工作幫助會(huì)很大。 尤其當(dāng)你對(duì)一些“數(shù)學(xué)密集型”的領(lǐng)域如視頻、圖像處理等有興趣時(shí)，這些知識(shí)將成為你手中的利器。

（5）培養(yǎng)團(tuán)隊(duì)精神，學(xué)會(huì)與人合作。今天的軟件工程早已經(jīng)不是一個(gè)人可以單獨(dú)操作的，而必須靠團(tuán)隊(duì)合作才能成功。不懂得合作的人是不能成大器的。大家要多去尋找可以與人一起做項(xiàng)目的機(jī)會(huì)。

（6）激勵(lì)創(chuàng)新意識(shí)，培養(yǎng)好奇心，不要死記硬背。沒(méi)有掌握某種算法技術(shù)的根本原理，就不會(huì)有應(yīng)變和創(chuàng)新的能力。想成為一位好程序員（其實(shí)從事任何一個(gè)行業(yè)都是如此），重要的是要養(yǎng)成鉆研，好奇，創(chuàng)新，動(dòng)手，合作的優(yōu)秀習(xí)慣，不滿足于填鴨，不滿足于考試交差，不滿足于表象。這不是學(xué)幾門課能夠一蹴而就的。

（7）有策略地“打工”。在不影響學(xué)業(yè)的前提下，尋找真正有意義的暑期工作或兼職。去找一個(gè)重視技術(shù)的公司，在一個(gè)好的“老板”指導(dǎo)下完成真正會(huì)被用戶使用的程序。不要急于去一個(gè)要你做“頭”而獨(dú)擋一面的地方，因?yàn)橄騽e人學(xué)習(xí)才是你的目的。找工作也是一樣，不要只看待遇和職銜，要挑一個(gè)你能夠?qū)W習(xí)的環(huán)境，一個(gè)愿意培養(yǎng)員工的企業(yè)，一個(gè)重視你的專業(yè)的公司。最后，還要挑一個(gè)好老板。

希望大家都能把握機(jī)會(huì)，養(yǎng)成好的學(xué)習(xí)習(xí)慣，把算法學(xué)精學(xué)透；希望大家都能有一個(gè)美好的未來(lái)！