啊哈！算法

研究算法給實際編程的程序員帶來許多好處。先進的算法工具有時候對軟件系統影響很大——減少開發時間，同時使執行速度更快。

算法與其他那些深奧的思想一樣重要，但在更一般的編程層面上具有更重要的影響。在《啊哈!靈機一動》一書中（本文的標題就借鑒了它），Martin Gardner1描述了深得我心的一個思想：“看起來很困難的問題也可以有一個簡單的、意想不到的答案。”與高級的方法不同，算法的啊哈！靈機一動?并非只有在大量的研究以后才能出現；任何愿意在編程之前、之中和之后進行認真思考的程序員都有機會捕捉到這靈機一動。

1　三個問題

好了，泛泛的話講得夠多啦。本文將圍繞三個小問題展開。在繼續閱讀以前，請先試著解決它們。

A．給定一個最多包含40億個隨機排列的32位整數的順序文件，找出一個不在文件中的32位整數（在文件中至少缺失一個這樣的數——為什么？）。在具有足夠內存的情況下，如何解決該問題？如果有幾個外部的“臨時”文件可用，但是僅有幾百字節的內存，又該如何解決該問題？

B．將一個n元一維向量向左旋轉2i個位置。例如，當n=8且i=3時，向量abcdefgh旋轉為defghabc。簡單的代碼使用一個n元的中間向量在n步內完成該工作。你能否僅使用數十個額外字節的存儲空間，在正比于n的時間內完成向量的旋轉?

C．給定一個英語字典，找出其中的所有變位詞集合。例如，“pots”、“stop”和“tops”互為變位詞，因為每一個單詞都可以通過改變其他單詞中字母的順序來得到。

2　無處不在的二分搜索

我想到的一個數在1到100之間，你來猜猜看。50？太小了。75？太大了。如此，游戲進行下去，直到你猜中我想到的數為止。如果我的整數位于1到n之間，那么你可以在次之內猜中。如果n是1 000，10次就可以完成；如果n是100萬，則最多20次就可以完成。

這個例子引出了一項可以解決眾多編程問題的技術：二分搜索。初始條件是已知一個對象存在于一個給定的范圍內，而一次探測操作可以告訴我們該對象是否低于、等于或高于給定的位置。二分搜索通過重復探測當前范圍的中點來定位對象。如果一次探測沒有找到該對象，那么我們將當前范圍減半，然后繼續下一次探測。當找到所需要的對象或范圍為空時停止。

在程序設計中二分搜索最常見的應用是在有序數組中搜索元素。在查找項50時，算法進行如下探測。

眾所周知，二分搜索程序要正確運行很困難。

順序搜索在搜索一個具有n個元素的表時，平均需要進行n/2次比較，而二分搜索僅僅進行不超過次的比較就可以完成。這在系統性能上會造成巨大的差異。下面的故事來自于《ACM通訊》的實例研究“TWA Reservation System”。

我們有一個執行線性搜索的程序，可以在1秒鐘內對一塊非常巨大的內存塊完成100次搜索。隨著網絡的增長，處理每條消息所需的平均CPU時間上升了0.3毫秒，這對我們來說是巨大的變化。我們發現問題的根源是線性搜索。把程序改為使用二分搜索以后，該問題消失了。

我在許多系統中也遇到過相同的問題。程序員在開始的時候使用簡單的順序搜索數據結構，這在開始的時候通常都足夠快。當搜索變得太慢的時候，對表進行排序并使用二分搜索通常可以消除瓶頸。

但是二分搜索的故事并沒有在快速搜索有序數組這里終止。Roy Weil將該技術應用于清理一個約1000行的輸入文件，其中僅包含一個錯誤行。很不幸，肉眼看不出錯誤行。只能通過在程序中運行文件的一個（起始）部分并且觀察到離奇錯誤的答案來辨別，這將會花費幾分鐘的時間。他的前任調試人員試圖通過每次運行整個程序中的少數幾行程序來找出錯誤行，但只在取得解決方案的道路上前進了一點點。Weil是如何僅僅運行10次程序就找到罪魁禍首的呢？

經過前面的熱身，我們現在來攻克問題A。輸入為順序文件（考慮磁帶或磁盤——雖然磁盤可以隨機讀寫，但是從頭至尾讀取文件通常會快得多）。文件包含最多40億個隨機排列的32位整數，而我們需要找出一個不存在于該文件中的32位整數。（至少缺少一個整數，因為一共有232也就是4 294 967 296個這樣的整數。）如果有足夠的內存，可以采用位圖技術，使用536 870 912個8位字節形成位圖來表示已看到的整數。然而，該問題還問到在僅有幾百個字節內存和幾個稀疏順序文件的情況下如何找到缺失的整數？為了采用二分搜索技術，就必須定義一個范圍、在該范圍內表示元素的方式以及用來確定哪一半范圍存在缺失整數的探測方法。如何來實現呢？

我們采用已知包含至少一個缺失元素的一系列整數作為范圍，并使用包含所有這些整數在內的文件表示這個范圍。靈機一動的結果是通過統計中間點之上和之下的元素來探測范圍：或者上面或者下面的范圍具有至多全部范圍的一半元素。由于整個范圍中有一個缺失元素，因此我們所需的那一半范圍中必然也包含缺失的元素。這些就是解決該問題的二分搜索算法所需要的主要想法。在翻閱答案查看Ed Reingold是如何做的以前，請嘗試將這些想法組織起來。

對于二分搜索技術在程序設計中的應用來說，這些應用僅僅是皮毛而已。求根程序使用二分搜索技術，通過連續地對分區間來求解單變量方程式（數值分析家稱之為對分法）。當選擇算法區分出一個隨機元素以后，就對該元素一側的所有元素遞歸地調用自身（這是一種隨機二分搜索）。其他使用二分搜索的地方包括樹數據結構和程序調試（當程序沒有任何提示就意外中止時，你會從源代碼中哪一部分開始探測來定位錯誤語句呢？）。在上述的每個例子中，分析程序并對二分搜索算法做些許修改，可以帶給程序員功能強大的啊哈！靈機一動。

3　基本操作的威力

二分搜索是許多問題的解決方案，下面研究一個有幾種解決方案的問題。問題B僅使用幾十個字節的額外空間將一個n元向量x在正比于n的時間內向左旋轉i個位置。該問題在應用程序中以各種不同的偽裝出現。在一些編程語言中，該功能是向量的一個基本操作。更重要地，旋轉操作對應于交換相鄰的不同大小的內存塊：每當拖動文件中的一塊文字到其他地方時，就要求程序交換兩塊內存中的內容。在許多應用場合下，運行時間和存儲空間的約束會很嚴格。

可以通過如下方式解決該問題：首先將x的前i個元素復制到一個臨時數組中，然后將余下的n－i個元素向左移動i個位置，最后將最初的i個元素從臨時數組中復制到x中余下的位置。但是，這種辦法使用的i個額外的位置產生了過大的存儲空間的消耗。另一種方法是定義一個函數將x向左旋轉一個位置（其時間正比于n）然后調用該函數i次。但該方法又產生了過多的運行時間消耗。

要在有限的資源內解決該問題，顯然需要更復雜的程序。有一個成功的方法有點像精巧的雜技動作：移動x[0]到臨時變量t，然后移動x[i]至x[0]，x[2i]至x[i]，依此類推（將x中的所有下標對n取模），直至返回到取x[0]中的元素，此時改為從t取值然后終止過程。當i為3且n為12時，元素按如下順序移動。

如果該過程沒有移動全部元素，就從x[1]開始再次進行移動，直到所有的元素都已經移動為止。

從另外一面考察這個問題，可以得到一個不同的算法：旋轉向量x其實就是交換向量ab的兩段，得到向量ba。這里a代表x中的前i個元素。假設a比b短，將b分為bl和br，使得br具有與a相同的長度。交換a和br，也就將ablbr轉換為brbla。序列a此時已處于其最終的位置，因此現在的問題就集中到交換b的兩部分。由于新問題與原來的問題具有相同的形式，我們可以遞歸地解決之。使用該算法可以得到優雅的程序，但是需要巧妙的代碼，并且要進行一些思考才能看出它的效率足夠高。

問題看起來很難，除非最終獲得了啊哈！靈機一動：我們將問題看做是把數組ab轉換成ba，同時假定我們擁有一個函數可以將數組中特定部分的元素求逆。從ab開始，首先對a求逆，得到arb，然后對b求逆，得到arbr。最后整體求逆，得到(arbr)r。此時就恰好是ba。于是，我們得到了如下用于旋轉的代碼，其中注釋部分表示abcdefgh向左旋轉三個位置以后的結果。

Doug McIlroy3給出了將十元數組向上旋轉5個位置的翻手例子。初始時掌心對著我們的臉，左手在右手上面。

------------------左手翻轉 ----------------- 右手翻轉 ------------------- 翻轉雙手---------------------------

翻轉代碼在時間和空間上都很高效，而且代碼非常簡短，很難出錯。Brian Kernighan4和P. J. Plauger5在其1981年出版的Software Tools in Pascal一書中，就使用該代碼在文本編輯器中實現了行的移動。Kernighan報告稱在第一次執行的時候程序就正確運行了，而他們先前基于鏈表的處理相似任務的代碼則包含幾個錯誤。該代碼用在幾個文本處理系統中，其中包括我最初用于錄入本章內容的文本編輯器。Ken Thompson6在1971年編寫了編輯器和這種求逆代碼，甚至在那時就主張把該代碼當作一種常識。

4　排序

現在我們來討論問題C。給定一本英語單詞字典（每個輸入行是一個由小寫字母組成的單詞），要求找出所有的變位詞分類。研究這個問題可以舉出許多理由。首先是技術上的：獲得這個問題的解決方案需要既具有正確的視角又能使用正確的工具。第二個理由更具有說服力：你總不想成為聚會中唯一一個不知道“deposit”、“dopiest”、“posited”和“topside”是變位詞的人吧？

解決這個問題的許多方法都出奇地低效和復雜。任何一種考慮單詞中所有字母的排列的方法都注定了要失敗。單詞“cholecystoduodenostomy”（我的字典中單詞“duodenocholecystostomy”的一個變位詞）有22！種排列，少量的乘法運算表明22! ≈ 1.1241021。即使假設以閃電一樣的速度每百億分之一秒執行一種排列，這也要消耗1.1109 秒。經驗法則“π秒就是一個納世紀”指出1.1109是數十年。而比較所有單詞對的任何方法在我的機器上運行至少要花費一整夜的時間——在我使用的字典里有大約230 000個單詞，而即使是一個簡單的變位詞比較也將花費至少1 微秒的時間，因此，總時間估算起來就是

230 000單詞230 000比較/單詞1微秒/比較=52 900106微秒=52 900秒≈14.7小時

你能夠找到同時避免上述缺陷的方法嗎？

我們獲得的啊哈！靈機一動?就是標識字典中的每一個詞，使得在相同變位詞類中的單詞具有相同的標識。然后，將所有具有相同標識的單詞集中在一起。這將原始的變位詞問題簡化為兩個子問題：選擇標識和集中具有相同標識的單詞。在進一步閱讀之前，先好好想想這些問題。

對第一個問題，我們可以使用基于排序的標識7：將單詞中的字母按照字母表順序排列。“deposit”的標識就是“deiopst”，這也是“dopiest”和其他任何在該類中的單詞的標識。要解決第二個問題，我們將所有的單詞按照其標識的順序排序。我所知道的關于該算法的最好描述就是Tom Cargill的翻手表示：先用一種方式排序（水平翻手），再用另一種方式排序（垂直翻手）。

5　原理

排序?排序最顯而易見的用處是產生有序的輸出，該輸出既可以是系統規范要求的一部分，也可以是另一個程序（也許是一個二分搜索程序）的前期準備工作。但是在變位詞問題中，排序并不是關注的焦點。排序是為了將相等的元素（本例中為標識）集中到一起。這些標識產生了另外一個排序應用：將單詞內字母排序使得同一個變位詞類中的單詞具有標準型。通過給每條記錄添加一個額外的鍵，并按照這些鍵進行排序，排序函數可以用于重新排列磁盤文件中的數據。在第三部分，我們還會多次回顧排序這個主題。

二分搜索?該算法在有序表中查找元素時極為高效，并且可用于內存排序或磁盤排序。唯一的缺陷就是整個表必須已知并且事先排好序。基于該簡單算法的思想在許多應用程序中都有應用。

標識?當使用等價關系來定義類時，定義一種標識使得類中的每一項都具有相同的標識，而該類以外的其他項則沒有該標識，這是很有用的。對單詞中的字母排序可以產生一個用于變位詞類的標識。其他標識通過排序給出。然后使用一個計數來代表重復的次數（于是標識“mississippi”可以寫成“i4m1p2s4”或將1省略——“i4mp2s4”）。也可以使用一個包含26個整數的數組來標識每個字母出現的次數。標識的其他應用包括：美國聯邦***用來索引指紋的方法，以及用來識別讀音相同但是拼寫不同的名字的Soundex啟發式方法：

Knuth8在其The Art of Computer Programming, Volume 3: Sorting and Sear ching9一書的描述了Soundex方法。

問題定義。確定用戶的真實需求是程序設計的根本。本文的中心思想是問題定義的下一步：使用哪些基本操作來解決問題？在每個例子中，啊哈！靈機一動都定義了一個新的基本操作使得問題得到簡化。

問題解決者的觀點。優秀程序員都有點懶：他們坐下來并等待靈機一動的出現而不急于使用最開始的想法編程。當然，這必須通過在適當的時候開始寫代碼來加以平衡。真正的技能就在于對這個適當時候的把握，這只能來源于解決問題和反思答案所獲得的經驗。

6　習題

1．考慮查找給定輸入單詞的所有變位詞問題。僅給定單詞和字典的情況下，如何解決該問題？如果有一些時間和空間可以在響應任何查詢之前預先處理字典，又會如何？

2．給定包含4 300 000 000個32位整數的順序文件，如何找出一個出現至少兩次的整數？

3．前面涉及了兩個需要精巧代碼來實現的向量旋轉算法。將其分別作為獨立的程序實現。在每個程序中，i和n的最大公約數如何出現？

4．幾位讀者指出，既然所有的三個旋轉算法需要的運行時間都正比于n，雜技算法的運行速度顯然是求逆算法的兩倍。雜技算法對數組中的每個元素僅存儲和讀取一次，而求逆算法需要兩次。在實際的計算機上進行實驗以比較兩者的速度差異，特別注意內存引用位置附近的問題。

5．向量旋轉函數將向量ab變為ba。如何將向量abc變為cba？（這對交換非相鄰內存塊的問題進行了建模）。

6．20世紀70年代末期，貝爾實驗室開發出了“用戶操作的電話號碼簿輔助程序”，該程序允許雇員使用標準的按鍵電話在公司電話號碼簿中查找電話號碼。

要查找該系統設計者的名字Mike Lesk10，可以按“LESKM”（也就是“53756”），隨后，系統會輸出他的電話號碼。這樣的服務現在隨處可見。該系統中出現的一個問題是，不同的名字有可能具有相同的按鍵編碼。在Lesk的系統中發生這種情況時，系統會詢問用戶更多的信息。給定一個大的名字文件（例如標準的大城市電話號碼簿），如何定位這些“錯誤匹配”呢？（當Lesk在這種規模的電話號碼簿上做實驗時，他發現錯誤匹配發生的概率僅僅是0.2%。）如何實現一個以名字的按鍵編碼為參數，并返回所有可能的匹配名字的函數？

7．在20世紀60年代早期，Vic Vyssotsky與一個程序員一起工作，該程序員需要轉置一個存儲在磁帶上的4 000×4 000的矩陣（每條記錄的格式相同，為數十個字節）。他的同事最初提出的程序需要運行50個小時。Vyssotsky如何將運行時間減少到半小時呢？

8．[J. Ullman]給定一個n元實數集合、一個實數t和一個整數k，如何快速確定是否存在一個k元子集，其元素之和不超過t？

9．順序搜索和二分搜索代表了搜索時間和預處理時間之間的折中。處理一個n元表格時，需要執行多少次二分搜索才能彌補對表進行排序所消耗的預處理時間？

10．某一天，一個新研究員向托馬斯·愛迪生報到。愛迪生要求他計算出一個空燈泡殼的容積。在使用測徑儀和微積分進行數小時的計算后，這個新員工給出了自己的答案——150 cm3。而愛迪生在幾秒鐘之內就計算完畢并給出了結果“更接近155”。他是如何實現的呢？

7　變位詞程序的實現（邊欄）

我的變位詞程序按三個階段的“管道”組織，其中一個程序的輸出文件作為下一個程序的輸入文件。第一個程序標識單詞，第二個程序排序標識后的文件，而第三個程序將這些單詞壓縮為每個變位詞類一行的形式。下面是一個僅有6個單詞的字典的處理過程。

輸出包括三個變位詞類。

下面的C語言sign程序假定沒有超過100個字母的單詞，并且輸入文件僅包含小寫字母和換行符。（因此我使用了一個一行的命令對字典進行預處理，將其中的大寫字母改為小寫字母。）

while循環每次讀取一個字符串到word中，直至文件末尾為止。strcpy函數復制輸入單詞到單詞sig中，然后調用C標準庫函數qsort對單詞sig中的字母進行排序（參數是待排序的數組、數組的長度、每個待排序項的字節數以及比較兩個項的函數名。在本例中，待比較項為單詞中的字母）。最后，printf語句依次打印標識、單詞本身和換行符。

系統sort程序將所有具有相同標識的單詞歸攏到一起。squash程序在同一行中將其打印出來。

大部分工作都是使用第二個printf語句來完成的。對每一個輸入行，該語句輸出第二個字段，后面跟一個空格。if語句捕捉標識之間的差異。如果sig與oldsig（其上一次的值）不同，那么就打印換行符（文件中的第一條記錄除外）。最后一個printf輸出最后一個換行符。

在使用小輸入文件對這些簡單部分進行測試后，我通過下面的命令構建了變位詞列表：

sign?gramlist

該命令將文件dictionary輸入到程序sign，連接sign的輸出至sort，連接sort的輸出至squash，并將squash的輸出寫入文件gramlist。程序的運行時間為18秒：sign用時4秒、sort用時11秒而squash用時3秒。

我在一個包含230 000個單詞的字典上運行了該程序。然而，不包括眾多的-s和-ed后綴。以下是一些很有趣的變位詞類。

1Martin Gardner（1914—），美國著名的科普作家，主持《科學美國人》的數學游戲專欄25年，寫作了大量文章和圖書，有世界影響。——編者注

2即循環移位。——審校者注

3?Doug McIlroy（1932—），著名計算機科學家，美國工程院院士，現為達特茅斯學院兼職教授。他于1968年第一個提出了軟件組件的概念。他參與設計了PL/I和C++語言、Multics和Unix操作系統。Unix上許多工具是他開發的，包括diff、echo、sort、spell和join等，管道實現也由他首創。他曾長期擔任貝爾實驗室計算技術研究部主任，并曾任ACM圖靈獎主席。——編者注

4?Brian Kernighan（1942—）著名計算機科學家，現為普林斯頓大學教授。他與人合作創造了Awk和AMPL編程語言，對Unix和C語言的設計也有很大貢獻。他還與人合寫了多部計算機名著，包括與Ritchie合著的The C Programming Language。——編者注

5?P. J. Plauger，著名C/C++語言專家，現為著名標準庫開發商Dinkumware總裁。他曾擔任ISO C標準委員會負責人，著有名著《C標準庫》（中文版由人民郵電出版社出版）。——編者注

6?Ken Thompson（1943—），著名計算機科學家，1983年圖靈獎得主。現為Google杰出工程師。他是Unix操作系統的主要設計者，并設計了C語言的前身B語言。——編者注

7?該變位詞算法是由許多人各自獨立發現的，至少可以追溯到20世紀60年代中期。

9?該書第2版英文影印版已由清華大學出版社引進出版，中文書名《計算機程序設計藝術 第3卷 排序和查找》，中譯版已由國防工業出版社出版，中文書名《計算機程序設計藝術 第3卷 排序與查找》。——編者注

10?Mike Lesk，著名程序員，ACM會士，美國工程院院士，現任Rutgers大學教授兼系主任。他在貝爾實驗室工作期間開發了大量工具，包括lex、uucp和stdio.h的前身。他領導了美國NSF數字圖書館計劃，該計劃支持了斯坦福大學搜索引擎研究項目，促生了Google。——編者注

本文節選自《編程珠璣（第2版?修訂版）》

內容簡介

本文轉載自異步社區

軟件開發 軟件開發

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。