資訊專欄INFORMATION COLUMN
標準庫中的sort函數(shù)，是快速排序算法的典型實現(xiàn)。算法將含有n個元素的序列排序，平均需要 O(n log n) 時間。
上周，我提出了“測試一個程序的性能比測試其功能更難”這個觀點。確認程序的性能達到標準以及確定“標準”的含義都十分困難。
接下來，我會繼續(xù)討論標準庫中的sort(排序)函數(shù)。sort函數(shù)實現(xiàn)了快速排序算法，快速排序算法平均可以在 O(n log n) 時間內(nèi)對含有n個元素的序列進行排序。除了這個平均性能之外，如果選擇了“不幸”的輸入情況，快速排序的運行時間會比平均時間長很多，比如，某些情況下快速排序的時間復雜度可以達到O(n2)。我使用“不幸”這個詞是因為在快速排序的實現(xiàn)中經(jīng)常使用隨機性的來保證O(n2)這樣的性能表現(xiàn)很少出現(xiàn)。
為什么隨機性在這里很重要呢？快速排序算法開始時挑選序列中的一個特定元素開始排序，叫做pivot（中心數(shù)據(jù)）。然后，快速排序算法調(diào)整元素的順序，使得小于等于中心數(shù)據(jù)的元素位于中心數(shù)據(jù)的前面，所有大于中心數(shù)據(jù)的元素排在中心數(shù)據(jù)的后面。最后，快速排序算法遞歸調(diào)用，來完成對這兩部分元素的排序
因此，快速排序的執(zhí)行時間，最壞情況下與元素個數(shù)對應的最大遞歸深度成比例。在實現(xiàn)中，依賴于遞歸深度的快速排序的性能，一般不會大于O(log n)。只要中心數(shù)據(jù)選定，遞歸深度就可以估計。平均情況下，這個深度與最大或最小元素的值無關。
快速排序算法是怎樣確保選定的中心數(shù)據(jù)不是很接近序列的端點呢？一般來看，這是無法保證的。盡管如此，大部分情況下可以采用隨機選取中心數(shù)據(jù)的方法，來避免出現(xiàn)最壞情況。這樣做可以保證快速排序算法的平均性能是可以接受的，即使在個別情況下，中心數(shù)據(jù)會出現(xiàn)在序列的端點位置，從而導致算法性能低下。由于這樣的情況非常少見，對于平均性能來說它不是一個大問題。對嗎？
這要視情況而定。假設，你的任務是編寫性能測試程序，來測試快速排序的實現(xiàn)。
你怎樣將c++標準中模糊的“平均性能”，改寫為實際需求，從而可以測試所有情況？
你以怎樣的方式來測試快速排序，這樣的方式可以保證測試結果正確可靠？
測試平均性能之所以困難，是因為在這個概念中一個概率的因素。如果，程序最終必須產(chǎn)生一個特定結果，那么，你可以確定一個測試程序的運行結果是正確還是錯誤。相反，如果你在測試平均性能，那么對于一個多帶帶的測試用例，無法判斷運行結果是否正確。最好情況是，通過運行越來越多的測試用例，你可以更有把握程序是否正確運行。在這個測試的過程中，更多的測試可能會改變你對于程序正確性的判斷。
簡而言之，如果性能中包括了關于平均執(zhí)行時間的描述，那么相應的測試需要用到一些統(tǒng)計分析。這樣的分析并不簡單，但是這是工程應用的傳統(tǒng)。美國航空191號班機的空難就是一個例子。191號班機在1979年5月25日從奧黑爾國際機場起飛。當飛機剛剛離開地面時，飛機左翼引擎忽然失靈并且從機翼上脫落。引擎是通過安全銷連接在機翼上的，這樣的設計是為了與機翼脫離而不是毀壞機翼。盡管如此，由于維護失誤，機翼被毀，導致飛機失控，發(fā)生空難，機上所有人無一幸免。
在閱讀相關的調(diào)查中，我看見了不同的飛機制造商對安全銷進行的測試，證明— 假設飛機正常維護 — 安全銷會使得引擎離開機翼而不是毀壞機翼。在此之前，我沒有見到過這樣的測試，但是設計安全銷在工程商的主要問題是：安全銷的目的是，受到過大壓力時，使引擎和機翼脫落。沒有辦法在安全銷不被破壞的情況下測試安全銷是否滿足要求。因此，在飛機中實際使用的安全銷不能檢測。
人們怎樣才能確保使用這樣生產(chǎn)的安全銷不會影響飛機的安全性呢？答案設計非常聰明。
引擎被許多個安全銷固定在機翼上，這樣即使有一個安全銷失靈，引擎也能從機翼上分離，而不損壞機翼。
安全銷以100個為一批進行生產(chǎn)，一個批次內(nèi)的安全銷同時以同樣的方式生產(chǎn)制造。
每個批次的100個安全銷中，會被隨機挑選10個進行測試，因此，10個安全銷會在測試中毀壞。如果，10個安全銷都通過了測試，那么就認為剩下的90個安全銷是安全可用的。如果10個中有一個安全銷沒有通過測試，那么這個批次都會被銷毀。
顯然，這樣的設計不僅僅包括了巧妙的工業(yè)設計，也包含了精妙的統(tǒng)計分析。必須準確選擇對安全銷的限制條件，在10%的安全銷已經(jīng)通過測試的條件下，即使兩個隨機選取的安全銷也幾乎不可能超出限制條件。我推測，這樣的限制條件可能是比實際應用中安全銷需要滿足的限制條件更窄的范圍。
我不想為了評估快速排序算法的平均性能而進行這樣的統(tǒng)計分析。即使我有信心可以正確地進行類似的統(tǒng)計分析，將來可能出現(xiàn)的規(guī)范或者測試程序的改變，都會使這樣的分析無效。同時，在以快速排序為例的算法，和以安全銷為例的機械設備之間有一個重要區(qū)別，那就是，有時為了達到某些目的，算法的輸入會被設計的非常復雜。比如在Doug McIlroy 1999年寫的論文中，詳細描述了怎樣構造快速排序的輸入，使得算法對于n個元素的排序時間達到O(n2)。在這樣的情況下，快速算法就與描述不符了嗎？如果是這樣，那么就很難看見我們現(xiàn)在對快速算法的應用了。
使得這樣的性能測試問題簡單化的一個方法是采用白盒測試的方法。白盒測試的方法利用了已知程序實現(xiàn)細節(jié)這一優(yōu)勢。下周，我會詳細介紹這樣的測試技術。
原文：How Can One Test a Program"s Average Performance?
轉載自：伯樂在線 - programmer_lin
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/8685.html
摘要：新生代農(nóng)民工就業(yè)薪資，程序員最高在調(diào)查樣本中，從事信息傳輸軟件和信息技術服務業(yè)的新生代農(nóng)民工比例為，是所有行業(yè)中增幅最大的一個。調(diào)查樣本中，新生代農(nóng)民工月均收入元，比上年增加元，增長。 ...
摘要：本篇文章來自于騰訊和共同舉辦的技術開放日后臺專場出品人傅鴻城的分享，由壹佰案例整理編輯。對于騰訊而言，后臺服務可用性都是四個九，四個九轉化為時間就要求一年內(nèi)的故障時間不能超過分鐘。 showImg(https://segmentfault.com/img/bVvL5f); 本篇文章來自于騰訊SNG和msup共同舉辦的技術開放日后臺專場出品人傅鴻城的分享，由壹佰案例整理編輯。原文發(fā)布在壹...
摘要：計算機組成中的大量原理和設計，都對應著性能這個詞。時間的倒數(shù)性能計算機的性能，其實和體力勞動很像，好比是我們要搬東西。對于計算機的性能，我們需要有個標準來衡量。花的時間越少，自然性能就越好。 0 學習路線的知識點概括 showImg(https://segmentfault.com/img/remote/1460000020031616?w=3832&h=2540); 學習計算機組成原...
閱讀 1540·2023-04-26 02:50
閱讀 3547·2023-04-26 00:28
閱讀 1937·2023-04-25 15:18
閱讀 3217·2021-11-24 10:31
閱讀 988·2019-08-30 13:00
閱讀 1004·2019-08-29 15:19
閱讀 1773·2019-08-29 13:09
閱讀 2983·2019-08-29 13:06
