標(biāo)準(zhǔn)庫(kù)中的sort函數(shù)，是快速排序算法的典型實(shí)現(xiàn)。算法將含有n個(gè)元素的序列排序，平均需要 O(n log n) 時(shí)間。

上周，我提出了“測(cè)試一個(gè)程序的性能比測(cè)試其功能更難”這個(gè)觀點(diǎn)。確認(rèn)程序的性能達(dá)到標(biāo)準(zhǔn)以及確定“標(biāo)準(zhǔn)”的含義都十分困難。

接下來(lái)，我會(huì)繼續(xù)討論標(biāo)準(zhǔn)庫(kù)中的sort(排序)函數(shù)。sort函數(shù)實(shí)現(xiàn)了快速排序算法，快速排序算法平均可以在 O(n log n) 時(shí)間內(nèi)對(duì)含有n個(gè)元素的序列進(jìn)行排序。除了這個(gè)平均性能之外，如果選擇了“不幸”的輸入情況，快速排序的運(yùn)行時(shí)間會(huì)比平均時(shí)間長(zhǎng)很多，比如，某些情況下快速排序的時(shí)間復(fù)雜度可以達(dá)到O(n2)。我使用“不幸”這個(gè)詞是因?yàn)樵诳焖倥判虻膶?shí)現(xiàn)中經(jīng)常使用隨機(jī)性的來(lái)保證O(n2)這樣的性能表現(xiàn)很少出現(xiàn)。

為什么隨機(jī)性在這里很重要呢？快速排序算法開(kāi)始時(shí)挑選序列中的一個(gè)特定元素開(kāi)始排序，叫做pivot（中心數(shù)據(jù)）。然后，快速排序算法調(diào)整元素的順序，使得小于等于中心數(shù)據(jù)的元素位于中心數(shù)據(jù)的前面，所有大于中心數(shù)據(jù)的元素排在中心數(shù)據(jù)的后面。最后，快速排序算法遞歸調(diào)用，來(lái)完成對(duì)這兩部分元素的排序

因此，快速排序的執(zhí)行時(shí)間，最壞情況下與元素個(gè)數(shù)對(duì)應(yīng)的最大遞歸深度成比例。在實(shí)現(xiàn)中，依賴(lài)于遞歸深度的快速排序的性能，一般不會(huì)大于O(log n)。只要中心數(shù)據(jù)選定，遞歸深度就可以估計(jì)。平均情況下，這個(gè)深度與最大或最小元素的值無(wú)關(guān)。
快速排序算法是怎樣確保選定的中心數(shù)據(jù)不是很接近序列的端點(diǎn)呢？一般來(lái)看，這是無(wú)法保證的。盡管如此，大部分情況下可以采用隨機(jī)選取中心數(shù)據(jù)的方法，來(lái)避免出現(xiàn)最壞情況。這樣做可以保證快速排序算法的平均性能是可以接受的，即使在個(gè)別情況下，中心數(shù)據(jù)會(huì)出現(xiàn)在序列的端點(diǎn)位置，從而導(dǎo)致算法性能低下。由于這樣的情況非常少見(jiàn)，對(duì)于平均性能來(lái)說(shuō)它不是一個(gè)大問(wèn)題。對(duì)嗎？

這要視情況而定。假設(shè)，你的任務(wù)是編寫(xiě)性能測(cè)試程序，來(lái)測(cè)試快速排序的實(shí)現(xiàn)。

你怎樣將c++標(biāo)準(zhǔn)中模糊的“平均性能”，改寫(xiě)為實(shí)際需求，從而可以測(cè)試所有情況？
你以怎樣的方式來(lái)測(cè)試快速排序，這樣的方式可以保證測(cè)試結(jié)果正確可靠？
測(cè)試平均性能之所以困難，是因?yàn)樵谶@個(gè)概念中一個(gè)概率的因素。如果，程序最終必須產(chǎn)生一個(gè)特定結(jié)果，那么，你可以確定一個(gè)測(cè)試程序的運(yùn)行結(jié)果是正確還是錯(cuò)誤。相反，如果你在測(cè)試平均性能，那么對(duì)于一個(gè)多帶帶的測(cè)試用例，無(wú)法判斷運(yùn)行結(jié)果是否正確。最好情況是，通過(guò)運(yùn)行越來(lái)越多的測(cè)試用例，你可以更有把握程序是否正確運(yùn)行。在這個(gè)測(cè)試的過(guò)程中，更多的測(cè)試可能會(huì)改變你對(duì)于程序正確性的判斷。

簡(jiǎn)而言之，如果性能中包括了關(guān)于平均執(zhí)行時(shí)間的描述，那么相應(yīng)的測(cè)試需要用到一些統(tǒng)計(jì)分析。這樣的分析并不簡(jiǎn)單，但是這是工程應(yīng)用的傳統(tǒng)。美國(guó)航空191號(hào)班機(jī)的空難就是一個(gè)例子。191號(hào)班機(jī)在1979年5月25日從奧黑爾國(guó)際機(jī)場(chǎng)起飛。當(dāng)飛機(jī)剛剛離開(kāi)地面時(shí)，飛機(jī)左翼引擎忽然失靈并且從機(jī)翼上脫落。引擎是通過(guò)安全銷(xiāo)連接在機(jī)翼上的，這樣的設(shè)計(jì)是為了與機(jī)翼脫離而不是毀壞機(jī)翼。盡管如此，由于維護(hù)失誤，機(jī)翼被毀，導(dǎo)致飛機(jī)失控，發(fā)生空難，機(jī)上所有人無(wú)一幸免。

在閱讀相關(guān)的調(diào)查中，我看見(jiàn)了不同的飛機(jī)制造商對(duì)安全銷(xiāo)進(jìn)行的測(cè)試，證明— 假設(shè)飛機(jī)正常維護(hù) — 安全銷(xiāo)會(huì)使得引擎離開(kāi)機(jī)翼而不是毀壞機(jī)翼。在此之前，我沒(méi)有見(jiàn)到過(guò)這樣的測(cè)試，但是設(shè)計(jì)安全銷(xiāo)在工程商的主要問(wèn)題是：安全銷(xiāo)的目的是，受到過(guò)大壓力時(shí)，使引擎和機(jī)翼脫落。沒(méi)有辦法在安全銷(xiāo)不被破壞的情況下測(cè)試安全銷(xiāo)是否滿(mǎn)足要求。因此，在飛機(jī)中實(shí)際使用的安全銷(xiāo)不能檢測(cè)。

人們?cè)鯓硬拍艽_保使用這樣生產(chǎn)的安全銷(xiāo)不會(huì)影響飛機(jī)的安全性呢？答案設(shè)計(jì)非常聰明。

引擎被許多個(gè)安全銷(xiāo)固定在機(jī)翼上，這樣即使有一個(gè)安全銷(xiāo)失靈，引擎也能從機(jī)翼上分離，而不損壞機(jī)翼。
安全銷(xiāo)以100個(gè)為一批進(jìn)行生產(chǎn)，一個(gè)批次內(nèi)的安全銷(xiāo)同時(shí)以同樣的方式生產(chǎn)制造。
每個(gè)批次的100個(gè)安全銷(xiāo)中，會(huì)被隨機(jī)挑選10個(gè)進(jìn)行測(cè)試，因此，10個(gè)安全銷(xiāo)會(huì)在測(cè)試中毀壞。如果，10個(gè)安全銷(xiāo)都通過(guò)了測(cè)試，那么就認(rèn)為剩下的90個(gè)安全銷(xiāo)是安全可用的。如果10個(gè)中有一個(gè)安全銷(xiāo)沒(méi)有通過(guò)測(cè)試，那么這個(gè)批次都會(huì)被銷(xiāo)毀。
顯然，這樣的設(shè)計(jì)不僅僅包括了巧妙的工業(yè)設(shè)計(jì)，也包含了精妙的統(tǒng)計(jì)分析。必須準(zhǔn)確選擇對(duì)安全銷(xiāo)的限制條件，在10%的安全銷(xiāo)已經(jīng)通過(guò)測(cè)試的條件下，即使兩個(gè)隨機(jī)選取的安全銷(xiāo)也幾乎不可能超出限制條件。我推測(cè)，這樣的限制條件可能是比實(shí)際應(yīng)用中安全銷(xiāo)需要滿(mǎn)足的限制條件更窄的范圍。

我不想為了評(píng)估快速排序算法的平均性能而進(jìn)行這樣的統(tǒng)計(jì)分析。即使我有信心可以正確地進(jìn)行類(lèi)似的統(tǒng)計(jì)分析，將來(lái)可能出現(xiàn)的規(guī)范或者測(cè)試程序的改變，都會(huì)使這樣的分析無(wú)效。同時(shí)，在以快速排序?yàn)槔乃惴?，和以安全銷(xiāo)為例的機(jī)械設(shè)備之間有一個(gè)重要區(qū)別，那就是，有時(shí)為了達(dá)到某些目的，算法的輸入會(huì)被設(shè)計(jì)的非常復(fù)雜。比如在Doug McIlroy 1999年寫(xiě)的論文中，詳細(xì)描述了怎樣構(gòu)造快速排序的輸入，使得算法對(duì)于n個(gè)元素的排序時(shí)間達(dá)到O(n2)。在這樣的情況下，快速算法就與描述不符了嗎？如果是這樣，那么就很難看見(jiàn)我們現(xiàn)在對(duì)快速算法的應(yīng)用了。

使得這樣的性能測(cè)試問(wèn)題簡(jiǎn)單化的一個(gè)方法是采用白盒測(cè)試的方法。白盒測(cè)試的方法利用了已知程序?qū)崿F(xiàn)細(xì)節(jié)這一優(yōu)勢(shì)。下周，我會(huì)詳細(xì)介紹這樣的測(cè)試技術(shù)。

原文：How Can One Test a Program"s Average Performance?
轉(zhuǎn)載自：伯樂(lè)在線 - programmer_lin