我們在開發(fā)商用系統(tǒng)的時候，通常要讓它滿足很多性能需求，例如執(zhí)行速度、資源占用等。在本篇文章中我們將通過幾個例子來探討定制編程在優(yōu)化性能中的作用。 盡管編譯器和最 新的Java虛擬機提供了一些工具來實現(xiàn)程序的自動優(yōu)化，不過要想真正獲得最大性能的程序，除了依靠它們外，你還有必要在編程的時候使用巧 妙的數(shù)據(jù)結構和針對特定問題而設計的新優(yōu)化算法。

　　驗證方法介紹

　　在本篇文章中，我們將通過對比驗證的方式來證明上述觀點的正確性，我們將分別給出標準的Java整數(shù)排序程序，還有根據(jù)特定內容進行定制化編程的排序程序，并對兩者進行對比，對比結果以圖形的方式直觀的顯示出來。

　　本篇文章中涉及到的所有驗證示例都將運行多次，取其平均表現(xiàn)，從而最大限度減少由于意外的操作系統(tǒng)行為造成的結果差異。另外，所有測試都在一個 獨立的系統(tǒng)上運行，該系統(tǒng)上沒有其它用戶和其它運行的程序，以保證結果的準確性。為了減少人工錯誤，測試結果被測量程序直接輸出到一個外部文件中，并由一 個圖形程序自動來根據(jù)這些數(shù)據(jù)生成對比圖。關聯(lián)程序同時也會檢查并使用平均測試結果，拋棄異常數(shù)據(jù)�？傊�，盡量使測試結果能夠客觀真實的反映不同程序的性 能表現(xiàn)。

　　高 效編程

　　一個程序執(zhí)行的指令越少它運行的速度就越快，這個觀點并非筆者首先提出，也不具有爭議性，這是在多年的計算機科學發(fā)展已經(jīng)證明的一個常識。無論 你的程序使用什么語言編寫，它通常都適用這個原則，當然使用Java和C++編寫的程序也不例外，人們通常使用這兩種編程語言來開發(fā)大型、可升級、快 速的 分布式系統(tǒng)。

　　從實際效果來看，要想成功的實現(xiàn)一個運行最快、消耗資源最少的程序，通常要求我們使用一個通用語言(諸如Java或C++)并根據(jù)特定編程環(huán)境 來手動來進行編程。與之相對應的是，單純依靠配置普通的組件，不根據(jù)特定環(huán)境進行程序設計和實現(xiàn)，程序優(yōu)化任務或者借助于現(xiàn)成的代碼庫或編輯器的自動優(yōu)化 功能，或者借助于JVM技術中高級功能。的確，在很多環(huán)境下后面的做法可能也足夠了，但是依靠這種方法你編寫出來的程序不一定具有最 佳的性能。從根本上來 說，定制化的設計、編碼和優(yōu)化，再加上這些過程中程序員的創(chuàng)新技能，這些因素加起來將可以做出運行最快和擴展性最強的程序。

　　普通排序VS計數(shù)排序

　　下面我們將通過對比兩種排序算法來驗證上面的結論，其中一個是標準的Java排序程序，另一個則是根據(jù)具體情況定制化的排序程序。第 一個例子是 簡單的對n個正整數(shù)排序，數(shù)值在0到k之間。在Java中我們可以通過簡單的使用Collections(集合)或Arrays(數(shù)組)類來實現(xiàn)這個目 的，如下例所示：

　　1 /**

　　2 * 使用Collections的sort方法來對輸入的正整數(shù)進行排序

　　3 */

　　4 public ArrayList sortInts(ArrayList inputSequence)

　　5 {

　　6 Collections.sort(inputSequence);

　　7 return inputSequence;

　　8 } /**

　　9

　　10

　　11 *使用Arrays類來對一個整數(shù)數(shù)字進行排序

　　12

　　13 */

　　14 public int[] sortInts(int [] inputSequence)

　　15 {

　　16 Arrays.sort(inputSequence);

　　17 return inputSequence;

　　18 }

　　在Java文檔中這樣描述Collections.sort程序：

　　“該排序算法是一個經(jīng)過修改的合并排序算法(其中如果低子列表中的最高元素小于高子列表中的最低元素，則忽略合并)。此算法提供可保證的n log(n)性能。 此實現(xiàn)將指定列表轉儲到一個數(shù)組中，并對數(shù)組進行排序，在重置數(shù)組中相應位置處每個元素的列表上進行迭代。這避免了由于試圖對適當位置上的鏈接列表進行排 序而產生的n2 log(n)性能。”

　　Collections.sort程序被設計可以支持任意元素類型，因此這個排序算法不能利用我們例子中專門針對正整數(shù)排序的一些特點。而Arrays.sort程序的文檔描述則顯示它是一個更適合對整數(shù)進行排序的算法：

　　“將特定的整數(shù)數(shù)組進行排序，得到一個有序整數(shù)數(shù)組。該排序算法是一個經(jīng)過調優(yōu)的快 速排序法，改編自Jon L. Bentley和M.Douglas McIlroy合著的《Engineering a Sort Function", Software-Practice and Experience》 Vol. 23(11) P. 1249-1265 (November 1993)。此算法在許多數(shù)據(jù)集上提供 n*log(n) 性能，這導致其他快 速排序會降低二次性能。

　　這個Arrays.sort算法已經(jīng)針對整數(shù)排序進行了改進，與我們本例中的特定要求已經(jīng)更接近了一步，因此它的效率要比Collections.sort更高一些。但是，O(nlogn)的性能依然非常高，我們還有方法來改進它。

　　現(xiàn)在，如果我們要專門針對正整數(shù)來設計一個最優(yōu)化的排序程序， 那么我們要記住整數(shù)類型具有以下特點：

　　1、與實數(shù)或浮點數(shù)不同的是，兩個相鄰整數(shù)之間沒有其它整數(shù)。例如有兩個整數(shù)a和b，如果a+1=b，那么你不可能再找到第三個整數(shù)x能滿足a

　　填寫下面表單即可預約申請免費試聽java課程!害怕學不會?助教陪讀，隨時解惑!擔心就業(yè)?一地學習，可全國推薦就業(yè)!

　　2、這些整數(shù)沒有關聯(lián)數(shù)據(jù)，它們不是元組(tuples)。因此在排序過程中，同樣大小的元素可以不用重復排序過程，這可以提高 效率。

　　考慮到我們輸入序列具有以上兩個特點，我們可以編寫一個非常不同的排序程序，計數(shù)排序的改進版，如Listing 1所示。

　　listing1

　　1 /**

　　2 * 實現(xiàn)計數(shù)排序算法

　　3 */

　　4 public int[] countingSort(int[] inputSequence)

　　5 {

　　6 // 獲得最大值

　　7 int maxValue = -1;

　　8 for(int i = 0; i < inputSequence.length; i++)

　　9 {

　　10 int x = inputSequence[i];

　　11 if(x > maxValue)

　　12 {

　　13 maxValue = x;

　　14 }

　　15 }

　　16

　　17 // 指定一個數(shù)組

　　18 int[] counts = new int[maxValue + 1];

　　19

　　20 // 計算輸入序列中每一個數(shù)出現(xiàn)的次數(shù)

　　21 for(int i : inputSequence)

　　22 {

　　23 counts[i] += 1;

　　24 }

　　25

　　26 // 獲得排序數(shù)字序列

　　27 for(int i = 0, j = 0; i <= maxValue; i++)

　　28 {

　　29 int c = counts[i];

　　30 for(int k = 0; k < c; k++, j++)

　　31 {

　　32 inputSequence[j] = i;

　　33 }

　　34 }

　　35

　　36 return inputSequence;

　　37 }

　　下面我們來簡單對這個程序的算法進行介紹，這個程序首先獲得輸入序列中最大的數(shù)值k，并以它為最大下標來創(chuàng)建一個數(shù)組(長度為k+1)。然后再 次檢查輸入序列，并確定每一個數(shù)值在序列中出現(xiàn)的次數(shù)，并將其記錄在counts數(shù)組中相應下標位置。舉個例子來說，如果輸入的數(shù)值序列是 [3,1,4,7,1,4,0],那么我們將得到一個長度為8的計數(shù)數(shù)組counts[]，包含下列值[1,2,0,1,2,0,0,1]。最后程序根據(jù) 計數(shù)數(shù)組來重寫輸入數(shù)列inputSequence。在這個例子中得到的數(shù)值是[0,1,1,3,4,4,7] 。

　　從以上算法中我們可以明白為什么這個算法不能用來對實數(shù)或浮點數(shù)進行排序;因為它們的輸入序列中的最大數(shù)值不能告訴我們要創(chuàng)建多少長度的技術數(shù) 組，而且這個計數(shù)排序也不能用來對整數(shù)鍵值的元組進行排序，因為算法執(zhí)行最后一步的時候，重寫了最初的輸入元素，破壞了元素的最初數(shù)值。

　　這個改進版的計數(shù)排序算法對輸入序列共進行了三次遍歷：第 一次是發(fā)現(xiàn)其最大值(即k)，這個操作的時間復雜度是O(n)。它分配了一個最大下標 為k的數(shù)組，盡管這只是一個簡單的數(shù)組指定操作，我們也認為它的時間復雜度為O(k)。然后它第二次對輸入數(shù)值進行遍歷，來計算不同數(shù)值出現(xiàn)的次數(shù)。最后 它使用排序的序列來對覆蓋原始輸入序列，時間復雜度為O(n)。因此這個算法總的時間復雜度為O(n+k)，空間復雜度為O(k).因此這個計數(shù)排序不僅 僅與要排序的數(shù)值多少有關系，還與其中最大數(shù)值大小有關系。