算法的力量

算法的力量

2006年5月 李開複

     算法是計算機科學領域最重要的基石之一，但卻受到了國内一些程式員的冷落。許多學生看到一些公司在招聘時要求的程式設計語言五花八門，就産生了一種誤解，認為學計算機就是學各種程式設計語言，或者認為，學習最新的語言、技術、标準就是最好的鋪路方法。其實，大家被這些公司誤導了。程式設計語言雖然該學，但是學習計算機算法和理論更重要，因為計算機語言和開發平台日新月異，但萬變不離其宗的是那些算法和理論，例如資料結構、算法、編譯原理、計算機體系結構、關系型資料庫原理等等。在“開複學生網”上，有位同學生動地把這些基礎課程比拟為“内功”，把新的語言、技術、标準比拟為“外功”。整天趕時髦的人最後隻懂得招式，沒有功力，是不可能成為高手的。

算法與我

     當我在1980年轉入計算機科學系時，還沒有多少人的專業方向是計算機科學。有許多其他系的人嘲笑我們說：“知道為什麼隻有你們系要加一個‘科學’，而沒有‘實體科學系’或‘化學科學系’嗎？因為人家是真的科學,不需要畫蛇添足，而你們自己心虛，生怕不‘科學’，才這樣欲蓋彌彰。” 其實，這點他們徹底弄錯了。真正學懂計算機的人（不隻是“程式設計匠”）都對數學有相當的造詣，既能用科學家的嚴謹思維來求證，也能用工程師的務實手段來解決問題——而這種思維和手段的最佳演繹就是“算法”。

     記得我讀博時寫的Othello對弈軟體獲得了世界冠軍。當時，得第二名的人認為我是靠僥幸才打赢他，不服氣地問我的程式平均每秒能搜尋多少步棋，當他發現我的軟體在搜尋效率上比他快60多倍時，才徹底服輸。為什麼在同樣的機器上，我可以多做60倍的工作呢？這是因為我用了一個最新的算法，能夠把一個指數函數轉換成四個近似的表，隻要用常數時間就可得到近似的答案。在這個例子中，是否用對算法才是能否赢得世界冠軍的關鍵。

     還記得1988年貝爾實驗室副總裁親自來通路我的學校，目的就是為了想了解為什麼他們的語音識别系統比我開發的慢幾十倍，而且，在擴大至大詞彙系統後，速度差異更有幾百倍之多。他們雖然買了幾台超級計算機，勉強讓系統跑了起來，但這麼貴的計算資源讓他們的産品部門很反感，因為“昂貴”的技術是沒有應用前景的。在與他們探讨的過程中，我驚訝地發現一個O(n*m)的動态規劃（dynamic programming）居然被他們做成了O(n*n*m)。更驚訝的是，他們還為此發表了不少文章，甚至為自己的算法起了一個很特别的名字，并将算法提名到一個科學會議裡，希望能得到大獎。當時，貝爾實驗室的研究員當然絕頂聰明，但他們全都是學數學、實體或電機出身，從未學過計算機科學或算法，才犯了這麼基本的錯誤。我想那些人以後再也不會嘲笑學計算機科學的人了吧!

網絡時代的算法

     有人也許會說：“今天計算機這麼快，算法還重要嗎?”其實永遠不會有太快的計算機，因為我們總會想出新的應用。雖然在摩爾定律的作用下，計算機的計算能力每年都在飛快增長，價格也在不斷下降。可我們不要忘記，需要處理的資訊量更是呈指數級的增長。現在每人每天都會創造出大量資料（照片，視訊，語音，文本等等）。日益先進的記錄和存儲手段使我們每個人的資訊量都在爆炸式的增長。網際網路的資訊流量和日志容量也在飛快增長。在科學研究方面，随着研究手段的進步，資料量更是達到了前所未有的程度。無論是三維圖形、海量資料處理、機器學習、語音識别，都需要極大的計算量。在網絡時代，越來越多的挑戰需要靠卓越的算法來解決。

     再舉另一個網絡時代的例子。在網際網路和手機搜尋上，如果要找附近的咖啡店，那麼搜尋引擎該怎麼處理這個請求呢?

     最簡單的辦法就是把整個城市的咖啡館都找出來,然後計算出它們的所在位置與你之間的距離,再進行排序,然後傳回最近的結果。但該如何計算距離呢？圖論裡有不少算法可以解決這個問題。

     這麼做也許是最直覺的，但絕對不是最迅速的。如果一個城市隻有為數不多的咖啡館,那這麼做應該沒什麼問題,反正計算量不大。但如果一個城市裡有很多咖啡館,又有很多使用者都需要類似的搜尋,那麼伺服器所承受的壓力就大多了。在這種情況下,我們該怎樣優化算法呢?

     首先，我們可以把整個城市的咖啡館做一次“預處理”。比如，把一個城市分成若幹個“格子(grid)”,然後根據使用者所在的位置把他放到某一個格子裡，隻對格子裡的咖啡館進行距離排序。

     問題又來了，如果格子大小一樣，那麼絕大多數結果都可能出現在市中心的一個格子裡，而郊區的格子裡隻有極少的結果。在這種情況下，我們應該把市中心多分出幾個格子。更進一步，格子應該是一個“樹結構”，最頂層是一個大格——整個城市，然後逐層下降，格子越來越小，這樣有利于使用者進行精确搜尋——如果在最底層的格子裡搜尋結果不多，使用者可以逐級上升，放大搜尋範圍。

     上述算法對咖啡館的例子很實用，但是它具有通用性嗎？答案是否定的。把咖啡館抽象一下，它是一個點”，如果要搜尋一個“面”該怎麼辦呢？比如，使用者想去一個水庫玩，而一個水庫有好幾個入口，那麼哪一個離使用者最近呢？這個時候，上述“樹結構”就要改成“r-tree”,因為樹中間的每一個節點都是一個範圍，一個有邊界的範圍（參考：http://www.cs.umd.edu/~hjs/rtrees/index.html）。

     通過這個小例子，我們看到，應用程式的要求千變萬化，很多時候需要把一個複雜的問題分解成若幹簡單的小問題，然後再選用合适的算法和資料結構。

     上面的例子在Google裡就要算是小case了！每天Google的網站要處理十億個以上的搜尋，GMail要儲存幾千萬使用者的2G郵箱，Google Earth要讓數十萬使用者同時在整個地球上遨遊，并将合适的圖檔經過網際網路送出給每個使用者。如果沒有好的算法，這些應用都無法成為現實。

     在這些的應用中，哪怕是最基本的問題都會給傳統的計算帶來很大的挑戰。例如，每天都有十億以上的使用者通路Google的網站，使用Google的服務，也産生很多很多的日志（Log）。因為Log每分每秒都在飛速增加，我們必須有聰明的辦法來進行處理。我曾經在面試中問過關于如何對log進行一些分析處理的問題，有很多面試者的回答雖然在邏輯上正确，但在實際應用中是幾乎不可行的。按照他們的算法，即便用上幾萬台機器，我們的處理速度都跟不上資料産生的速度。

     那麼Google是如何解決這些問題的呢？

     首先，在網絡時代，就算有最好的算法，也要能在并行計算的環境下執行。在Google的資料中心，我們使用的是超大的并行計算機。但傳統的并行算法運作時，效率會在增加機器數量後迅速降低，也就是說，十台機器如果有五倍的效果，增加到一千台時也許就隻有幾十倍的效果。這種事倍功半的代價是沒有哪家公司可以負擔得起的。而且，在許多并行算法中，隻要一個結點犯錯誤，所有計算都會前功盡棄。

     那麼Google是如何開發出既有效率又能容錯的并行計算的呢？

     Google最資深的計算機科學家Jeff Dean認識到， Google 所需的絕大部分資料處理都可以歸結為一個簡單的并行算法：Map and Reduce（http://labs.google.com/papers/mapreduce.html）。 這個算法能夠在很多種計算中達到相當高的效率，而且是可擴充的（也就是說，一千台機器就算不能達到一千倍的效果，至少也可以達到幾百倍的效果）。Map and Reduce的另外一大特色是它可以利用大批廉價的機器組成功能強大的server farm。最後，它的容錯性能異常出色，就算一個server farm裡面的機器down掉一半，整個farm依然能夠運作。正是因為這個天才的認識,才有了Map and Reduce算法。借助該算法，Google幾乎能無限地增加計算量，與日新月異的網際網路應用一同成長。

算法并不局限于計算機和網絡

     舉一個計算機領域外的例子：在高能實體研究方面，很多實驗每秒鐘都産生幾個TB的資料量。但因為處理能力和存儲能力的不足，科學家不得不把絕大部分未經處理的資料丢棄掉。可大家要知道，新元素的資訊很有可能就藏在我們來不及處理的資料裡面。同樣的，在其他任何領域裡，算法都可以改變人類的生活。例如人類基因的研究，就可能因為算法而發明新的醫療方式。在國家安全領域，有效的算法可能避免下一個911的發生。在氣象方面，算法可以更好地預測未來天災的發生，以拯救生命。

     是以，如果你把計算機的發展放到應用和資料飛速增長的大環境下，你一定會發現，算法的重要性不是在日益減小，而是在日益加強。

給程式員的七個建議

     （1）練内功。不要隻花功夫學習各種流行的程式設計語言和工具，以及某些公司招聘廣告上要求的科目。要把資料結構、算法、資料庫、作業系統原理、計算機體系結構、計算機網絡，離散數學等基礎課程學好。大家不妨試試高德納所著The Art of Computer Programming裡的題目，如果你能夠解決其中的大部分題目，就說明你在算法方面有一定的功力了。

     （2）多實戰。通過程式設計的實戰積累經驗、鞏固知識。很多中國大學畢業生缺乏程式設計和調試經驗；學習C語言，考試過關就算學會了；課題項目中，隻要程式能夠編譯，運作，并且輸入輸出滿足要求就算了事。這些做法是不行的。寫程式的時候，大家必須多想想如何把程式寫得更加精煉、高效、高品質。建議大家争取在大學四年中積累編寫十萬行代碼的經驗。我們必須明白的是：好程式員是寫出來的，不是學出來的。

     （3）求實幹。不要輕視任何實際工作，比如一些看似簡單的編碼或測試。要不懈追求對細節一絲不苟的實幹作風與敬業精神。我發現不少程式員對于知識的掌握很膚淺，不求甚解，沒有好奇心，不會刨根問底。比如，學會了C++，是否了解一個對象在編譯後，在彙編代碼中是如何被初始化的？這個對象的各個成員在記憶體中是如何存放的？當一個成員函數被調用時，編譯器在彙編代碼中加入了哪些額外的動作？虛函數的調用是如何實作的? 這些東西恐怕在程式設計語言或編譯原理中都沒有詳細提到，隻有通過踏實的實幹才能真正掌握。

     （4）重視數學學習。數學是思維的體操，數學無處不在。學計算機至少要學習離散數學、機率論、布爾代數、集合論和數理邏輯。這些知識并不難，但是對你未來的工作幫助會很大。 尤其當你對一些“數學密集型”的領域如視訊、圖像處理等有興趣時，這些知識将成為你手中的利器。

     （5）培養團隊精神，學會與人合作。今天的軟體工程早已經不是一個人可以單獨操作的，而必須靠團隊合作才能成功。不懂得合作的人是不能成大器的。大家要多去尋找可以與人一起做項目的機會。

     （6）激勵創新意識，培養好奇心，不要死記硬背。沒有掌握某種算法技術的根本原理，就不會有應變和創新的能力。想成為一位好程式員（其實從事任何一個行業都是如此），重要的是要養成鑽研，好奇，創新，動手，合作的優秀習慣，不滿足于填鴨，不滿足于考試交差，不滿足于表象。這不是學幾門課能夠一蹴而就的。

     （7）有政策地“打工”。在不影響學業的前提下，尋找真正有意義的暑期工作或兼職。去找一個重視技術的公司，在一個好的“老闆”指導下完成真正會被使用者使用的程式。

     不要急于去一個要你做“頭”而獨擋一面的地方，因為向别人學習才是你的目的。找工作也是一樣，不要隻看待遇和職銜，要挑一個你能夠學習的環境，一個願意培養員工的企業，一個重視你的專業的公司。最後，還要挑一個好老闆。

     希望大家都能把握機會，養成好的學習習慣，把算法學精學透；希望大家都能有一個美好的未來！