By 劉未鵬(pongba)

C++的羅浮宮(http://blog.csdn.net/pongba)

TopLanguage(http://groups.google.com/group/pongba)

目錄

0. 前言

1. 猜數(shù)字

2. 稱球

3. 排序

    3.1 為什么堆排比快排慢

    3.2 為什么快排其實(shí)也不是那么快

    3.3 基排又為什么那么快呢

4. 信息論！信息論？

5. 小結(jié)

0. 前言

    知道這個(gè)理論是在TopLanguage上的一次討論，先是g9轉(zhuǎn)了David MacKay的一篇文章，然后引發(fā)了牛人們的一場(chǎng)關(guān)于信息論的討論。Anyway，正如g9很久以前在Blog里面所說的：

有時(shí)無知是福。俺看到一點(diǎn)新鮮的科普也能覺得造化神奇。剛才讀Gerald Jay Sussman（SICP作者）的文章，Building Robust Systems – an essay，竟然心如小鹿亂撞，手心濕潤(rùn)，仿佛第一次握住初戀情人溫柔的手。

    而看到MacKay的這篇文章我也有這種感覺——以前模糊的東西忽然有了深刻的解釋，一切頓時(shí)變得明白無比。原來看問題的角度或?qū)用婺軌驇磉@么大的變化。再一次印證了越是深刻的原理往往越是簡(jiǎn)單和強(qiáng)大。所以說，土鱉也有土鱉的幸福:P

這篇文章相當(dāng)于MacKay原文的白話文版。MacKay在原文中用到了信息論的知識(shí)，后者在我看來并不是必須的，盡管計(jì)算的時(shí)候方便，但與本質(zhì)無關(guān)。所以我用大白話解釋了一通。

1. 猜數(shù)字

    我們先來玩一個(gè)猜數(shù)字游戲：我心里默念一個(gè)1~64之間的數(shù)，你來猜（你只能問答案是“是”或“否”的問題）。為了保證不論在什么情況下都能以盡量少的次數(shù)猜中，你應(yīng)該采取什么策略呢？很顯然，二分。先是猜是不是位于1~32之間，排除掉一半可能性，然后對(duì)區(qū)間繼續(xù)二分。這種策略能夠保證無論數(shù)字怎么跟你捉迷藏，都能在log_2{n}次以內(nèi)猜中。用算法的術(shù)語來說就是它的下界是最好的。

    我們?cè)賮砘仡櫼幌逻@個(gè)游戲所蘊(yùn)含的本質(zhì)：為什么這種策略具有最優(yōu)下界？答案也很簡(jiǎn)單，這個(gè)策略是平衡的。反之如果策略不是平衡的，比如問是不是在1~10之間，那么一旦發(fā)現(xiàn)不是在1~10之間的話就會(huì)剩下比N/2更多的可能性需要去考察了。

    徐宥在討論中提到，這種策略的本質(zhì)可以概括成“讓未知世界無機(jī)可乘”。它是沒有“弱點(diǎn)的”，答案的任何一個(gè)分支都是等概率的。反之，一旦某個(gè)分支蘊(yùn)含的可能性更多，當(dāng)情況落到那個(gè)分支上的時(shí)候你就郁悶了。比如猜數(shù)字游戲最糟糕的策略就是一個(gè)一個(gè)的猜：是1嗎？是2嗎？... 因?yàn)檫@種猜法最差的情況下需要64次才能猜對(duì)，下界非常糟糕。二分搜索為什么好，就是因?yàn)樗看味紝⒖赡苄耘懦话氩⑶覠o論如何都能排除一半（它是最糟情況下表現(xiàn)最好的）。

2. 稱球

    12個(gè)小球，其中有一個(gè)是壞球。有一架天平。需要你用最少的稱次數(shù)來確定哪個(gè)小球是壞的并且它到底是輕還是重。

    這個(gè)問題是一道流傳已久的智力題。網(wǎng)絡(luò)上也有很多講解，還有泛化到N個(gè)球的情況下的嚴(yán)格證明。也有零星的一些地方提到從信息論的角度來看待最優(yōu)解法。本來我一直認(rèn)為這道題目除了試錯(cuò)之外沒有其它高妙的思路了，只能一個(gè)個(gè)方法試，并盡量從結(jié)果中尋找信息，然后看看哪種方案最少。

    然而，實(shí)際上它的確有其它的思路，一個(gè)更本質(zhì)的思路，而且根本用不著信息論這么拗口的知識(shí)。

    我們先回顧一下猜數(shù)字游戲。為了保證任何情況下以最少次數(shù)猜中，我們的策略是每次都排除恰好一半的可能性。類比到稱球問題上：壞球可能是12個(gè)球中的任意一個(gè)，這就是12種可能性；而其中每種可能性下壞球可能輕也可能重。于是“壞球是哪個(gè)球，是輕是重”這個(gè)問題的答案就有12×2=24種可能性。現(xiàn)在我們用天平來稱球，就等同于對(duì)這24種可能性發(fā)問，由于天平的輸出結(jié)果有三種“平衡、左傾、右傾”，這就相當(dāng)于我們的問題有三個(gè)答案，即可以將所有的可能性切成三份，根據(jù)猜數(shù)字游戲的啟發(fā)，我們應(yīng)當(dāng)盡量讓這三個(gè)分支概率均等，即平均切分所有的可能性為三等份。如此一來的話一次稱量就可以將答案的可能性縮減為原來的1/3，三次就能縮減為1/27。而總共才有24種可能性，所以理論上是完全可以3次稱出來的。

    如何稱的指導(dǎo)原則有了，構(gòu)造一個(gè)稱的策略就不是什么太困難的事情了。首先不妨解釋一下為什么最直觀的稱法不是最優(yōu)的——6、6稱：在6、6稱的時(shí)候，天平平衡的可能性是0。剛才說了，最優(yōu)策略應(yīng)該使得天平三種狀態(tài)的概率均等，這樣才能三等分答案的所有可能性。

   為了更清楚的看待這個(gè)問題，我們不妨假設(shè)有6個(gè)球，來考慮一下3、3稱和2、2稱的區(qū)別：

   在未稱之前，一共有12種可能性：1輕、1重、2輕、2重、...、6輕、6重。現(xiàn)在將1、2、3號(hào)放在左邊，4、5、6放在右邊3、3稱了之后，不失一般性假設(shè)天平左傾，那么小球的可能性就變成了原來的一半（6種）：1重、2重、3重、4輕、5輕、6輕。即這種稱法能排除一半可能性。

    現(xiàn)在再來看2、2稱法，即1、2放左邊，3、4放右邊，剩下的5、6不稱，放一邊。假設(shè)結(jié)果是天平平衡，那么可能性剩下——4種：5重、5輕、6重、6輕。假設(shè)天平左傾，可能性也剩下4種：1重、2重、3輕、4輕。右傾和左傾的情況類似。總之，這種稱法，不管天平結(jié)果如何，情況都被我們縮小到了原來的三分之一！我們充分利用了“天平的結(jié)果狀態(tài)可能有三種”這個(gè)條件來三等分所有可能性，而不是二等分。

    說到這里，剩下的事情就實(shí)在很簡(jiǎn)單了：第二步稱法，只要記著這樣一個(gè)指導(dǎo)思想——你選擇的稱法必須使得當(dāng)天平平衡的時(shí)候答案剩下的可能性和天平左傾（右傾）的時(shí)候答案剩下的可能性一樣多。實(shí)際上，這等同于你得選擇一種稱法，使得天平輸出三種結(jié)果的概率是均等的，因?yàn)樘炱捷敵瞿硞€(gè)結(jié)果的概率就等同于所有支持這個(gè)結(jié)果（左傾、右傾、平衡）的答案可能性的和，并且答案的每個(gè)可能性都是等概率的。

MacKay在他的書《Information Theory: Inference and Learning Algorithms》（作者開放免費(fèi)電子書）里面4.1節(jié)專門講了這個(gè)稱球問題，還畫了一張不錯(cuò)的圖，我就照抄了：

    圖中“1+”是指“1號(hào)小球?yàn)橹?span lang=EN-US>”這一可能性。一開始一共有24種可能性。4、4稱了之后不管哪種情況（分支），剩下來的可能性總是4種。這是一個(gè)完美的三分。然后對(duì)每個(gè)分支構(gòu)造第二次稱法，這里你只要稍加演算就可以發(fā)現(xiàn)，分支1上的第二次稱法，即“1、2、6對(duì)3、4、5”這種稱法，天平輸出三種結(jié)果的可能性是均等的（嚴(yán)格來說是幾乎均等）。這就是為什么這個(gè)稱法能夠在最壞的情況下也能表現(xiàn)最好的原因，沒有哪個(gè)分支是它的弱點(diǎn)，它必然能將情況縮小到原來的1/3。

3. 排序

    用前面的看問題視角，排序的本質(zhì)可以這樣來表述：一組未排序的N個(gè)數(shù)字，它們一共有N!種重排，其中只有一種排列是滿足題意的（譬如從大到小排列）。換句話說，排序問題的可能性一共有N!種。任何基于比較的排序的基本操作單元都是“比較a和b”，這就相當(dāng)于猜數(shù)字游戲里面的一個(gè)問句，顯然這個(gè)問句的答案只能是“是”或“否”，一個(gè)只有兩種輸出的問題最多只能將可能性空間切成兩半，根據(jù)上面的思路，最佳切法就是切成1/2和1/2。也就是說，我們希望在比較了a和b的大小關(guān)系之后，如果發(fā)現(xiàn)a<b的話剩下的排列可能性就變成N!/2，如果發(fā)現(xiàn)a>b也是剩下N!/2種可能性。由于假設(shè)每種排列的概率是均等的，所以這也就意味著支持a<b的排列一共有N!/2個(gè)，支持a>b的也是N!/2個(gè)，換言之，a<b的概率等于a>b的概率。

    我們希望每次在比較a和b的時(shí)候，a<b和a>b的概率是均等的，這樣我們就能保證無論如何都能將可能性縮小為原來的一半了！最優(yōu)下界。

    一個(gè)直接的推論是，如果每次都像上面這樣的完美比較，那么N個(gè)元素的N!種可能排列只需要log_2{N!}就排查玩了，而log_2{N!}近似于NlogN。這正是快排的復(fù)雜度。

    3.1 為什么堆排比快排慢

    回顧一下堆排的過程：

    1. 建立最大堆（堆頂?shù)脑卮笥谄鋬蓚€(gè)兒子，兩個(gè)兒子又分別大于它們各自下屬的兩個(gè)兒子... 以此類推）

    2. 將堆頂?shù)脑睾妥詈笠粋€(gè)元素對(duì)調(diào)（相當(dāng)于將堆頂元素（最大值）拿走，然后將堆底的那個(gè)元素補(bǔ)上它的空缺），然后讓那最后一個(gè)元素從頂上往下滑到恰當(dāng)?shù)奈恢茫ㄖ匦率苟炎畲蠡?

    3. 重復(fù)第2步。

    這里的關(guān)鍵問題就在于第2步，堆底的元素肯定很小，將它拿到堆頂和原本屬于最大元素的兩個(gè)子節(jié)點(diǎn)比較，它比它們大的可能性是微乎其微的。實(shí)際上它肯定小于其中的一個(gè)兒子。而大于另一個(gè)兒子的可能性非常小。于是，這一次比較的結(jié)果就是概率不均等的，根據(jù)前面的分析，概率不均等的比較是不明智的，因?yàn)樗⒉荒鼙ＷC在糟糕情況下也能將問題的可能性削減到原本的1/2。可以想像一種極端情況，如果a肯定小于b，那么比較a和b就會(huì)什么信息也得不到——原本剩下多少可能性還是剩下多少可能性。

    在堆排里面有大量這種近乎無效的比較，因?yàn)楸荒玫蕉秧數(shù)哪莻€(gè)元素幾乎肯定是很小的，而靠近堆頂?shù)脑赜謳缀蹩隙ㄊ呛艽蟮模瑢⒁粋€(gè)很小的數(shù)和一個(gè)很大的數(shù)比較，結(jié)果幾乎肯定是“小于”的，這就意味著問題的可能性只被排除掉了很小一部分。

    這就是為什么堆排比較慢（堆排雖然和快排一樣復(fù)雜度都是O(NlogN)但堆排復(fù)雜度的常系數(shù)更大）。

    MacKay也提供了一個(gè)修改版的堆排：每次不是將堆底的元素拿到上面去，而是直接比較堆頂（最大）元素的兩個(gè)兒子，即選出次大的元素。由于這兩個(gè)兒子之間的大小關(guān)系是很不確定的，兩者都很大，說不好哪個(gè)更大哪個(gè)更小，所以這次比較的兩個(gè)結(jié)果就是概率均等的了。具體參考這里。

3.2 為什么快排其實(shí)也不是那么快

    我們考慮快排的過程：隨機(jī)選擇一個(gè)元素做“軸元素”，將所有大于軸元素的移到左邊，其余移到右邊。根據(jù)這個(gè)過程，快排的第一次比較就是將一個(gè)元素和軸元素比較，這個(gè)時(shí)候顯而易見的是，“大于”和“小于”的可能性各占一半。這是一次漂亮的比較。

    然而，快排的第二次比較就不那么高明了：我們不妨令軸元素為pivot，第一次比較結(jié)果是a1<pivot，那么可以證明第二次比較a2也小于pivot的可能性是2/3！這容易證明：如果a2>pivot的話，那么a1，a2，pivot這三個(gè)元素之間的關(guān)系就完全確定了——a1<pivot<a2，剩下來的元素排列的可能性我們不妨記為P（不需要具體算出來）。而如果a2<pivot呢？那么a1和a2的關(guān)系就仍然是不確定的，也就是說，這個(gè)分支里面含有兩種情況：a1<a2<pivot，以及a2<a1<pivot。對(duì)于其中任一種情況，剩下的元素排列的可能性都是P，于是這個(gè)分支里面剩下的排列可能性就是2P。所以當(dāng)a2<pivot的時(shí)候，還剩下2/3的  可能性需要排查。

    再進(jìn)一步，如果第二步比較果真發(fā)現(xiàn)a2<pivot的話，第三步比較就更不妙了，模仿上面的推理，a3<pivot的概率將會(huì)是3/4！

    這就是快排也不那么快的原因，因?yàn)樗矝]有做到每次比較都能將剩下的可能性砍掉一半。

    3.3 雞排為什么又那么快呢？

    傳統(tǒng)的解釋是：基排不是基于比較的，所以不具有后者的局限性。話是沒錯(cuò)，但其實(shí)還可以將它和基于比較的排序做一個(gè)類比。

    基排的過程也許是源于我們理順一副牌的過程：如果你有N（N<=13）張牌，亂序，如何理順呢？我們假象桌上有十三個(gè)位置，然后我們將手里的牌一張一張放出去，如果是3，就放在位置3上，如果是J，就放在位置11上，放完了之后從位置1到位置13收集所有的牌（沒有牌的位置上不收集任何牌）。

    我們可以這樣來理解基排高效的本質(zhì)原因：假設(shè)前i張牌都已經(jīng)放到了它們對(duì)應(yīng)的位置上，第i+1張牌放出去的時(shí)候，實(shí)際上就相當(dāng)于“一下子”就確立了它和前i張牌的大小關(guān)系，用O(1)的操作就將這張牌正確地插入到了前i張牌中的正確位置上，這個(gè)效果就相當(dāng)于插入排序的第i輪原本需要比較O(i)次的，現(xiàn)在只需要O(1)了。

    但是，為什么基排能夠達(dá)到這個(gè)效果呢？上面只是解釋了過程，解釋了過程不代表解釋了本質(zhì)。

    當(dāng)i張牌放到位之后，放置第i+1張牌的時(shí)候有多少種可能性？大約i+1種，因?yàn)榍?span lang=EN-US>i張牌將13個(gè)位置分割成了i+1個(gè)區(qū)間——第i+1張牌可以落在任意一個(gè)區(qū)間。所以放置第i+1張牌就好比是詢問這樣一個(gè)問題：“這張牌落在哪個(gè)區(qū)間呢？”而這個(gè)問題的答案有i+1種可能性？所以它就將剩下來的可能性均分成了i+1份（換句話說，砍掉了i/i+1的可能性！）。再看看基于比較的排序吧：由于每次比較只有兩種結(jié)果，所以最多只能將剩下的可能性砍掉一半。

    這就是為什么基排要快得多。而所有基于比較的排序都逃脫不了NlogN的宿命。

    4. 信息論！信息論？

    本來呢，MacKay寫那篇文章是想用信息論來解釋為什么堆排慢，以及為什么快排也慢的。MacKay在他的文章中的解釋是，只有提出每種答案的概率都均等的問題，才能獲得最大信息量。然而，仔細(xì)一想，其實(shí)這里信息論并不是因，而是果。這里不需要用信息論就完全能夠解釋，而且更明白。信息論只是對(duì)這個(gè)解釋的一個(gè)形式化。當(dāng)然，信息論在其它地方還是有應(yīng)用的。但這里其實(shí)用不著信息論這么重量級(jí)的東西（也許具體計(jì)算一些數(shù)據(jù)的時(shí)候是需要的），而是只需要一種看問題的本質(zhì)視角：將排序問題看成和猜數(shù)字一樣，是通過問問題來縮小/排除（narrow down）結(jié)果的可能性區(qū)間，這樣一來，就會(huì)發(fā)現(xiàn)，“最好的問題”就是那些能夠均分所有可能性的問題，因?yàn)槟菢拥脑挷还軉栴}的答案如何，都能排除掉k-1/k（k為問題的答案有多少種輸出——猜數(shù)字里面是2，稱球里面是3）種可能性，而不均衡的問題總會(huì)有一個(gè)或一些答案分支排除掉的可能性要小于k-1/k。于是策略的下界就被拖累了。

    5. 小結(jié)

    這的確是“小結(jié)”，因?yàn)閮牲c(diǎn)：

    1. 這個(gè)問題可以有信息論的理論解釋，而信息論則是一個(gè)相當(dāng)大的領(lǐng)域了。

    2. 文中提到的這種看問題的視角除了用于排序、稱球，還能夠運(yùn)用到哪些問題上（比如搜索）。

Update(06/13/2008) : 徐宥在討論中繼續(xù)提到：

    另外，這幾天我重新把TAOCP 第三卷(第二版)翻出來看了看 Knuth 怎么說這個(gè)問題的, 發(fā)現(xiàn)真是牛大了：

    先說性能：

pp148, section 5.2.3 說：

When N = 1000, the approximate average runiing time on MIX are 160000u for heapsort 130000u for shellsort 80000u  for quicksort

    這里,  Knuth 同學(xué)發(fā)現(xiàn)一般情況下 heapsort 表現(xiàn)很不好. 于是，在下文他就說，習(xí)題18 (pp156, 難度21)

(R.W.Floyd) During the selection phase of heapsort, the key K tends to be quite small, so that nearly all the comparisons in step H6 find K<K_j. Show how to modify the algorithm so that K is not compared with K_j in the main loop of the computation, thereby nearly cutting the average number of comparisons in half.

    答案里面的方法和DMK的方法是一樣的。(我覺得DMK是看了這個(gè)論文或者TAoCP的) 這里說 by half，就正好和快排差不多了。

    再說信息論分析：

    在5.3.1 (pp181) 高爺爺就說, “排序問題可以看成是一個(gè)樹上的鳥兒排排站的問題. (還特地畫了一棵樹), 下一段就說, 其實(shí)這個(gè)也有等價(jià)說法, 就是信息論, 我們從稱球問題說起...”

   然后后面一直講信息論和最小比較排序...

   高爺爺真不愧是姓高的，囧rz..