網(wǎng)絡(luò)時(shí)代的更多挑戰(zhàn)靠算法完成

算法是計(jì)算機(jī)科學(xué)領(lǐng)域最重要的基石之一，但卻受到了國(guó)內(nèi)一些程序員的冷落。計(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í)髦的人最后只懂得招式，沒有功力，是不可能成為高手的。

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

有人也許會(huì)說：“今天計(jì)算機(jī)這么快，算法還重要嗎？”其實(shí)永遠(yuǎn)不會(huì)有太快的計(jì)算機(jī)，因?yàn)槲覀兛倳?huì)想出新的應(yīng)用。雖然在摩爾定律的作用下，計(jì)算機(jī)的計(jì)算能力每年都在飛快增長(zhǎng)，價(jià)格也在不斷下降?？晌覀儾灰?，需要處理的信息量更是呈指數(shù)級(jí)增長(zhǎng)?，F(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á)到了前所未有的程度。無論是三維圖形、海量數(shù)據(jù)處理、機(jī)器學(xué)習(xí)、語(yǔ)音識(shí)別，都需要極大的計(jì)算量。在網(wǎng)絡(luò)時(shí)代，越來越多的挑戰(zhàn)需要靠卓越的算法來解決。

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

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

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

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

上述算法對(duì)咖啡館的例子很實(shí)用，但是它具有通用性嗎？答案是否定的。比如，用戶想去一個(gè)水庫(kù)玩，而一個(gè)水庫(kù)有好幾個(gè)入口，那么哪一個(gè)離用戶最近呢？這個(gè)時(shí)候，上述“樹結(jié)構(gòu)”就要改成“r-tree”，因?yàn)闃渲虚g的每一個(gè)節(jié)點(diǎn)都是一個(gè)范圍，一個(gè)有邊界的范圍。

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

并行算法可以成為Google的核心優(yōu)勢(shì)

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

在這些應(yīng)用中，哪怕是最基本的問題都會(huì)給傳統(tǒng)的計(jì)算帶來很大的挑戰(zhàn)。例如，每天都有十億以上的用戶訪問Google的網(wǎng)站，使用Google的服務(wù)，也產(chǎn)生很多很多的日志（Log）。因?yàn)槿罩久糠置棵攵荚陲w速增加，我們必須找到好的辦法去處理。如何正確地對(duì)日志進(jìn)行分析處理？在目前看來，其處理速度都跟不上數(shù)據(jù)產(chǎn)生的速度。

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