我們要講的第一個概念就是Addressing。Addressing 這個詞沒有很達意的中文翻譯，單純翻譯成「編址」大家還是不明白，會問什麼叫做編址。其實，我倒覺得更簡單的一種講法是一一把所有的東西進行編號。這樣更為準確，也容易懂。在計算機裡面所有的東西都被編了號，這包括一個個的內存格子，筆記本電腦上那些在機殼兒上看得見的和看不見的接口， 計算機通過有線或者無線所連結的各種設備，它們都被編了號。對於這些編號，我們廣義地稱之為地址。

 

另外，計算機所見到的、處理了的信息，它所運行的指令，也都被編了號。為什麼編號這件事情重要呢，它又導致了計算機做事情和我們人有什麼不同呢？我們還是先從人的認知過程講起。

 

人在早先能識別的東西不多，我們只知道某些動物或者植物能吃，有一個能遮風擋雨的地方睡覺，等等。具體是這隻羊還是那隻羊，是這個蘋果還是那蘋果，是這個山洞還是那個山洞，都沒有分別。當後來人類接觸的人和東西數量多了以後， 人會對它們的特點進行描述，以便於區分。

 

也就是說人類區分個體是通過人和物與其它東西明顯不同的特質實現的。這種區分和查找目標的習慣， 我們一直沿用至今。比如，丈夫會對妻子講，〝幫我拿一下客廳茶几上的那個白色的糖盒子〞。妻子到了客廳，直接走到茶几跟前，看到那個白色的盒子，就直接拿給丈夫了。上面就是今天人典型的做事清的方法，簡單直接。

 

但是，計算機做這件簡單的事清方法卻不同。假如在未來的家庭裡，丈夫和妻子都是機器人，丈夫機器人向妻子提出的最常見的請求會是這樣的：

 

〝能否將第三個房間，第六個家具，第九個位置的東西拿給我？〞

 

接下來，妻子機器人拿來的是糖還是一瓶墨水，她並不用去管。在這個例子中，你可以看到計算機和人類的行為有兩點不同之處。一個是編號代替了實際的對象，另一個則很有趣，如果丈夫機器人以為那個地方放的是糖，但妻子拿來的是墨水，他可能也會直接倒進咖啡裡，這其實就是我們遇到的系統當機的情況。

 

丈夫機器人能否會像人一樣說〝幫我拿一下客廳茶几上的那個白色的糖盒子〞呢？也是可以的，這時妻子機器人必須進行兩步操作，第一步是查找，找到客廳對應的房間編號，也就是前面說的地址，茶几對應的家具地址，以及白色糖盒子對應的位置地址，然後把糖盒子拿過來。也就是說，計算機的操作怎麼都繞不過編號去，這也是史教授等人說編號的設計和實現方法特別重要的原因。

 

計算機為什麼要多此一舉呢？我在前面講過，電子計算機從一誕生開始就是要處理大量的數據的，因此它必須採用完全不同於人的方式區分每一個目標。細體會這兩者的差別，以前的人把計算當作目的，圖靈是把計算當作手段，實現一些功能才是他的目的。

 

為了實現複雜的功能，對機器來講， 最簡單的方法就是把所有要計算的對象， 比如數據，都編上號。在圖靈機模型中， 所用的數字都放在一個個編了號（地址） 的格子裡。計算機對於數據的操作，都是先找到盒子的地址，然後把那個盒子中的數據拿出來處理，處理完的內容，再放回到某個地址中。

 

圖靈的這種做法有什麼好處呢？主要有兩點，首先，他可以用一個數學模型把計算機這個機器描述清楚，這就如同我們可以用變量 x、y、z 把一個數學公式描述清楚一樣。我們計算簡單的數學題和物理題時，直接使用數字，但是計算複雜的問題時，就要先寫數學公式，再代入數字， 分兩步走。這和計算機工作的道理是一樣的，因為面對的問題複雜了。

 

當計算機直接操作的是那些編了號的格子時，如何用最少的信息，將所有的東西編號就成了計算機科學裡的藝術了，這一點在以後我們會陸續講到。

 

另外，計算機科學中也從此有了一個大的課題 — 〝查找〞( Search )，也就是說，在計算機裡根據一個東西的特徵把它的地址找到。

 

查找是我們今天要講的第二個概念。得到了具體的地址後，計算機才好訪問 ( Access ) 裡面的具體內容。這就好比一個藏書千冊的國學大師，要讀一本書之前，先要用某種方法在幾十個書架上找到它的位置，然後才能取出來一樣。後一個動作就是計算機裡面的訪問，這是今天的第三個概念。

 

事實上，只要我們的藏書超過幾百本，找書的時候就要遵循一些方法了，否則找東西的效率非常低。接下來，我們就來看看在〝查找一個東西〞這個具體問題上，人和計算機的思維有何相同和不同之處，今天只講相同之處，明天會講差異之處。

 

 

第一種方法是依次按順序掃一眼，這種方洲以僅能夠用於找書，其實在街上找某個地址也是如此。這種方法看似慢，其實是人能夠最快做到的，因為如果隨機亂找，會來回來去找好幾次也不得要領。找東西有經驗的人都知道要按照順序找，找過的地方就要爭取不看第二遍。這也是上帝喜歡笨人的一個很好的例子。這個笨辦法在計算機軟件中還會時不時地用到，我們稱之為順序查找。這是我們今天講的第四個概念等一會兒我們說說它的應用場景。

 

第二種是字典查找法。查字典的人從來不用一頁頁地翻找，而是大約估摸著所要查的字所在的位置，直接打開那一頁， 如果發現要找的字在這一頁的前面，就往前翻，否則就往後翻，總之幾次之後，就能找到該找的字。而且愛動腦筋的人在使用一本字典時間長了以後，查字典的速度會提高，用不著翻幾次就能找到想找的字。大家記住這個清況，因為它比絕大多數學計算機的人所了解的二分查找方法更決。

 

那麼計算機採用什麼方法呢？上述兩種方法都用，第一種方法顯然是笨辦法， 但是在一些場景下依然在使用，比如你在編輯一篇文章時，要把〝北京〞這個詞挑出來，全都替換成〝上海〞，除了順序查找別無他法。第二種字典查找法在計算機中用得也很多，但是由於計算機中的字典只有兩個字母， 0 和 1，因此它有了一個新變種，就是計算機從業者常說的二分查找 ( Binary Search )，這是今天介紹的第五個概念。

 

關於二分查找的遊戲可能很多讀者朋友都做過。比如游戲者讓大家在心目中想一個 1 ~ 1,000 的數字，然後你問他問題，對方回答〝yes ( 是 )〞或者〝no ( 不是 )〞，你用10次一定能夠猜出他心目中想的數字。這個花招其實很簡單，你第一次只要問他是否小於 500，如果他給出了肯定的答案說明數字在1 – 499 裡面第二次折半問他這個問題即可。類似的，如果他的回應是否定的，說明對方心目中的數字是在 500 ~ 1,000 之間，第二次往大的折半問即可。然後你不斷縮小範圍，每次減少一半，這樣問 10 次即可，因為 2 的 10 次方是等於 1,024，大於 1,000。這就是二分查找。如果你用這個辦法去中國找身份證號的位置，大約只要 31 次， 不需要把 13 億中國人都掃一遍， 31 次和 13 億次，這個差距還是巨大的。

 

但是，二分查找有一個問題，就是所有的數據「事先要排序」，而排序是有成本的。相比查找，排序的速度要慢得多。因此，是否應該對數據先花點時間進行一次排序則要看具體應用的情況而定。

 

如果只對數據進行一次查找，為此事先進行排序顯然就不合算了，只有當查找的次數足夠多，通過次數抵消掉它的邊際成本，為此花一些時間排序才合算。當然，這個場景有一個前提，就是數據是靜態的，比如大學的數據庫在進行學籍管理時，每一個年級新生入校後，人員是穩定的，對他們按照學號進行一次排序就有意義。再比如，對於歷史數據，比如公司的營收，一旦形成，就是事實，不能修改的，這樣做也有意義。

 

但遺憾的是，在大部分現實生活的應用中，數據總是在變化的，比如一個公司的員工，每個月有新的進來，老的離開。再比如一個人開車時，位置是不斷變動的，周圍加油站離他的距離也是變化的。在這種倩況下，找一個目標是否要對所有的目標先排序，就值得商榷了。當然在這種清況下，我們還是有辦法做到利用原來數據有序的特點，動態調整新數據的，讓每次排序所做的工作不要太多，這在我們後面介紹完計算機中'堆”這個概念時，大家就會明白是怎麼做到的。

 

今天我們介紹了五個概念，此外，通過今天的內容我們可以看到：

 

1. 當一個問題的規模大到一定程度之後，它就不再是同類小問題的放大，就變成了另一個問題，解決的方法需要完全不同。計算機需要對所有的東西進行編號就是這個原因。

 

2. 凡事都有成本，一種方法好不好， 是有前提條件的。

 

3. 世界上大部分事清不是一成不變的，很難處理一次就能一勞永逸地享受成果。

 

除了順序查找和二分查找這兩種和人的直覺類似的方法，計算機在尋找目標的方法上，還有優於人的地方，那是我們之後要講的內容。

 

 

來源：《吳軍-如何有效地找到一個目標？ 》