- 相關(guān)推薦
算法的力量
李開復(fù)：算法的力量
算法是計算機科學(xué)領(lǐng)域最重要的基石之一，但卻受到了國內(nèi)一些程序員的冷落。許多學(xué)生看到一些公司在招聘時要求的編程語言五花八門就產(chǎn)生了一種誤解，認(rèn)為學(xué)計算機就是學(xué)各種編程語言，或者認(rèn)為，學(xué)習(xí)最新的語言、技術(shù)、標(biāo)準(zhǔn)就是最好的鋪路方法。其實大家都被這些公司誤導(dǎo)了。編程語言雖然該學(xué)，但是學(xué)習(xí)計算機算法和理論更重要，因為計算機算法和理論更重要，因為計算機語言和開發(fā)平臺日新月異，但萬變不離其宗的是那些算法和理論，例如數(shù)據(jù)結(jié)構(gòu)、算法、編譯原理、計算機體系結(jié)構(gòu)、關(guān)系型數(shù)據(jù)庫原理等等。在“開復(fù)學(xué)生網(wǎng)”上，有位同學(xué)生動地把這些基礎(chǔ)課程比擬為“內(nèi)功”，把新的語言、技術(shù)、標(biāo)準(zhǔn)比擬為“外功”。整天趕時髦的人最后只懂得招式，沒有功力，是不可能成為高手的。
算法與我
當(dāng)我在1980年轉(zhuǎn)入計算機科學(xué)系時，還沒有多少人的專業(yè)方向是計算機科學(xué)。有許多其他系的人嘲笑我們說：“知道為什么只有你們系要加一個‘科學(xué)’，而沒有‘物理科學(xué)系’或‘化學(xué)科學(xué)系’嗎？因為人家是真的科學(xué)，不需要畫蛇添足，而你們自己心虛，生怕不‘科學(xué)’，才這樣欲蓋彌彰�！逼鋵崳@點他們徹底弄錯了。真正學(xué)懂計算機的人（不是“編程匠”）都對數(shù)學(xué)有相當(dāng)?shù)脑煸�，既能用科學(xué)家的嚴(yán)謹(jǐn)思維來求證，也能用工程師的務(wù)實手段來解決問題——而這種思維和手段的最佳演繹就是“算法”。
記得我讀博時寫的Othello對弈軟件獲得了世界冠軍。當(dāng)時，得第二名的人認(rèn)為我是靠僥幸才打贏他，不服氣地問我的程序平均每秒能搜索多少步棋，當(dāng)他發(fā)現(xiàn)我的軟件在搜索效率上比他快60多倍時，才徹底服輸。為什么在同樣的機器上，我可以多做60倍的工作呢？這是因為我用了一個最新的算法，能夠把一個指數(shù)函數(shù)轉(zhuǎn)換成四個近似的表，只要用常數(shù)時間就可得到近似的答案。在這個例子中，是否用對算法才是能否贏得世界冠軍的關(guān)鍵。
還記得1988年貝爾實驗室副總裁親自來訪問我的學(xué)校，目的就是為了想了解為什么他們的語音識別系統(tǒng)比我開發(fā)的慢幾十倍，而且，在擴大至大詞匯系統(tǒng)后，速度差異更有幾百倍之多。他們雖然買了幾臺超級計算機，勉強讓系統(tǒng)跑了起來，但這么貴的計算資源讓他們的產(chǎn)品部門很反感，因為“昂貴”的技術(shù)是沒有應(yīng)用前景的。在與他們探討的過程中，我驚訝地發(fā)現(xiàn)一個O(n*m)的動態(tài)規(guī)劃(dynamicprogramming)居然被他們做成了O(n*n*m)。更驚訝的是，他們還為此發(fā)表了不少文章，甚至為自己的算法起了一個很特別的名字，并將算法提名到一個科學(xué)會議里，希望能得到大獎。當(dāng)時，貝爾實驗室的研究員當(dāng)然絕頂聰明，但他們?nèi)际菍W(xué)數(shù)學(xué)、物理或電機出身，從未學(xué)過計算機科學(xué)或算法，才犯了這么基本的錯誤。我想那些人以后再也不會嘲笑學(xué)計算機科學(xué)的人了吧！
網(wǎng)絡(luò)時代的算法
有人也許會說：“今天計算機這么快，算法還重要嗎？”其實永遠(yuǎn)不會有太快計算機，因為我們總會想出新的應(yīng)用。雖然在摩爾定律的作用下，計算機的計算能力每年都在飛快增長，價格也在不斷下降�？晌覀儾灰洠枰幚淼男畔⒘扛浅手笖�(shù)級的增長�，F(xiàn)在每人每天都會創(chuàng)造出大量數(shù)據(jù)（照片，視頻，語音，文本等等）。日益先進(jìn)的紀(jì)錄和存儲手段使我們每個人的信息量都在爆炸式的增長。互聯(lián)網(wǎng)的信息流量和日志容量也在飛快增長。在科學(xué)研究方面，隨著研究手段的進(jìn)步，數(shù)據(jù)量更是達(dá)到了前所未有的程度。無論是三維圖形、海量數(shù)據(jù)處理、機器學(xué)習(xí)、語音識別，都需要極大的計算量。在網(wǎng)絡(luò)時代，越來越多的挑戰(zhàn)需要靠卓越的算法來解決。
再舉另一個網(wǎng)絡(luò)時代的例子。在互聯(lián)網(wǎng)和手機搜索，如果要找附近的咖啡店，那么搜索引擎該怎么處理這個請求呢？最簡單的辦法就是把整個城市的咖啡館都找出來，然后計算出它們的所在位置與你之間的距離，再進(jìn)行排序，然后返回最近的結(jié)果。但該如何計算距離呢？圖論里有不少算法可以解決這個問題。
這么做也許是最直觀的，但絕對不是最迅速的。如果一個城市只有為數(shù)不多的咖啡館，那么這么做應(yīng)該沒什么問題，反正計算量不大。但如果一個城市里有很多咖啡館，又有很多用戶都需要類似的搜索，那么服務(wù)器所承受的壓力就大多了。在這種情況下，我們該怎樣優(yōu)化算法呢？
首先，我們可以把整個城市的咖啡館做一次“預(yù)處理”。比如，把一個城市分成若干個“格子(grid)”，然后根據(jù)用戶所在的位置把他放到某一個格子里，只對格子里的咖啡館進(jìn)行距離排序。
問題又來了，如果格子大小一樣，那么絕大多數(shù)結(jié)果都可能出現(xiàn)在市中心的一個格子里，而郊區(qū)的格里只有極少的結(jié)果。在這種情況下，我們應(yīng)該把市中心多分出幾個格子。更進(jìn)一步，格子應(yīng)該是一個“樹結(jié)構(gòu)”，最頂層是一個大格——整個城市，然后逐層下降，格子越來越小，這樣有利于用戶進(jìn)行精確搜索——如果在最底層的格子里搜索結(jié)果不多，用戶可以逐級上升，放大搜索范圍。
上述算法對咖啡館的例子很實用，但是它具有通用性嗎？答案是否定的。把咖啡館抽象一下，它是一個“點”，如果要搜索一個“面”該怎么辦呢？比如，用戶想去一個水庫玩，而一個水庫有好幾個入口，那么哪一個離用戶最近呢？這個時候，上述“樹結(jié)構(gòu)”就要改成“r-tree”，因為樹中間的每一個節(jié)點都是一個范圍，一個有邊界的范圍（參考:http://www.cs.umd.edu/~hjs/rtrees/）。
通過這個小例子，我們看到，應(yīng)用程序的要求千變?nèi)f化，很多時候需要把一個復(fù)雜的問題分解成若干簡單的小問題，然后再選用合適的算法和數(shù)據(jù)結(jié)構(gòu)。
并行算法：Google的核心優(yōu)勢
上面的例子在Google里就要算是小case了！每天Google的網(wǎng)站要處理十億個以上的搜索，GMail要儲存幾千萬用戶的2G郵箱，GoogleEarth要讓數(shù)十萬用戶同時在整個地球上遨游，并將合適的圖片經(jīng)過互聯(lián)網(wǎng)提交給每個用戶。如果沒有好的算法，這些應(yīng)用都無法成為現(xiàn)實。
在這些的應(yīng)用中，哪怕是最基本的問題都會給傳統(tǒng)的計算帶來很大的挑戰(zhàn)。例如，每天都有十億以上的用戶訪問Google的網(wǎng)站，使用Google的服務(wù)，也產(chǎn)生很多很多的日志(Log)。因為Log每份每秒都在飛速增加我們必須有聰明的辦法來進(jìn)行處理。我曾經(jīng)在面試中問過關(guān)于如何對Log進(jìn)行一些分析處理的問題，有很多面試者的回答雖然在邏輯上正確，但是實際應(yīng)用中是幾乎不可行的。按照它們的算法，即便用上幾萬臺機器，我們的處理速度都根不上數(shù)據(jù)產(chǎn)生的速度。
那么Google是如何解決這些問題的？
首先，在網(wǎng)絡(luò)時代，就算有最好的算法，也要能在并行計算的環(huán)境下執(zhí)行。在Google的數(shù)據(jù)中心，我們使用的是超大的并行計算機。但傳統(tǒng)的并行算法運行時，效率會在增加機器數(shù)量后迅速降低，也就是說，十臺機器如果有五倍的效果，增加到一千臺時也許就只有幾十倍的效果。這種事半功倍的代價是沒有哪家公司可以負(fù)擔(dān)得起的。而且，在許多并行算法中，只要一個結(jié)點犯錯誤，所有計算都會前功盡棄。
那么Google是如何開發(fā)出既有效率又能容錯的并行計算的呢？
Google最資深的計算機科學(xué)家JeffDean認(rèn)識到，Google所需的絕大部分?jǐn)?shù)據(jù)處理都可以歸結(jié)為一個簡單的并行算法：MapandReduce（http://labs.google.com/papers/mapreduce.html）。這個算法能夠在很多種計算中達(dá)到相當(dāng)高的效率，而且是可擴展的（也就是說，一千臺機器就算不能達(dá)到一千倍的效果，至少也可以達(dá)到幾百倍的效果）。MapandReduce的另外一大特色是它可以利用大批廉價的機器組成功能強大的serverfarm。最后，它的容錯性能異常出色，就算一個serverfarm宕掉一半，整個fram依然能夠運行。正是因為這個天才的認(rèn)識，才有了MapandReduce算法。借助該算法，Google幾乎能無限地增加計算量，與日新月的互聯(lián)網(wǎng)應(yīng)用一同成長。
算法并不局限于計算機和網(wǎng)絡(luò)
舉一個計算機領(lǐng)域外的例子：在高能物理研究方面，很多實驗每秒鐘都能幾個TB的數(shù)據(jù)量。但因為處理能力和存儲能力的不足，科學(xué)家不得不把絕大部分未經(jīng)處理的數(shù)據(jù)丟棄掉�？纱蠹乙溃略氐男畔⒑苡锌赡芫筒卦谖覀儊聿患疤幚淼臄�(shù)據(jù)里面。同樣的，在其他任何領(lǐng)域里，算法可以改變?nèi)祟惖纳�。例如人類基因的研究，就可能因為算法而發(fā)明新的醫(yī)療方式。在國家安全領(lǐng)域，有效的算法可能避免下一個911的發(fā)生。在氣象方面，算法可以更好地預(yù)測未來天災(zāi)的發(fā)生，以拯救生命。
所以，如果你把計算機的發(fā)展放到應(yīng)用和數(shù)據(jù)飛速增長的大環(huán)境下，你一定會發(fā)現(xiàn)；算法的重要性不是在日益減小，而是在日益加強。
【算法的力量】相關(guān)文章：
心算法04-30
數(shù)學(xué)算法04-28
蟻群算法04-27
參數(shù)Kleene系統(tǒng)的三Ⅰ算法與反向三Ⅰ支持算法04-30
SSDA的改進(jìn)算法04-26
空間測邊交會解析算法與迭代算法的綜合應(yīng)用05-02
區(qū)間精細(xì)算法與長效精細(xì)算法的對比研究04-30