沒(méi)有算法功力，是不可能成為高手的

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

算法與我

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

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

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

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

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

再舉另一個(gè)網(wǎng)絡(luò )時(shí)代的例子。在互聯(lián)網(wǎng)和手機搜索，如果要找附近的咖啡店，那么搜索引擎該怎么處理這個(gè)請求呢？最簡(jiǎn)單的辦法就是把整個(gè)城市的咖啡館都找出來(lái)，然后計算出它們的所在位置與你之間的距離，再進(jìn)行排序，然后返回最近的結果。但該如何計算距離呢？圖論里有不少算法可以解決這個(gè)問(wèn)題。

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

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

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

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

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

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

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

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

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

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

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

Google最資深的計算機科學(xué)家Jeff Dean認識到，Google所需的絕大部分數據處理都可以歸結為一個(gè)簡(jiǎn)單的并行算法：Map and Reduce（）。這個(gè)算法能夠在很多種計算中達到相當高的效率，而且是可擴展的（也就是說(shuō)，一千臺機器就算不能達到一千倍的效果，至少也可以達到幾百倍的效果）。Map and Reduce的另外一大特色是它可以利用大批廉價(jià)的機器組成功能強大的server farm。最后，它的容錯性能異常出色，就算一個(gè)server farm宕掉一半，整個(gè)fram依然能夠運行。正是因為這個(gè)天才的認識，才有了Map and Reduce算法。借助該算法，Google幾乎能無(wú)限地增加計算量，與日新月異的互聯(lián)網(wǎng)應用一同成長(cháng)。

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

舉一個(gè)計算機領(lǐng)域外的例子：在高能物理研究方面，很多實(shí)驗每秒鐘都能有幾個(gè)TB的數據量。但因為處理能力和存儲能力的不足，科學(xué)家不得不把絕大部分未經(jīng)處理的數據丟棄掉?？纱蠹乙?，新元素的信息很有可能就藏在我們來(lái)不及處理的數據里面。同樣的，在其他任何領(lǐng)域里，算法可以改變人類(lèi)的生活。例如人類(lèi)基因的研究，就可能因為算法而發(fā)明新的醫療方式。在國家安全領(lǐng)域，有效的算法可能避免下一個(gè)911的發(fā)生。在氣象方面，算法可以更好地預測未來(lái)天災的發(fā)生，以拯救生命。

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