我们在开发商用系统的时候，通常要让它满足很多性能需求，例如执行速度、资源占用等。在本篇文章中我们将通过几个例子来探讨定制编程在优化性能中的作用。 尽管编译器和最 新的Java虚拟机提供了一些工具来实现程序的自动优化，不过要想真正获得最大性能的程序，除了依靠它们外，你还有必要在编程的时候使用巧 妙的数据结构和针对特定问题而设计的新优化算法。

　　验证方法介绍

　　在本篇文章中，我们将通过对比验证的方式来证明上述观点的正确性，我们将分别给出标准的Java整数排序程序，还有根据特定内容进行定制化编程的排序程序，并对两者进行对比，对比结果以图形的方式直观的显示出来。

　　本篇文章中涉及到的所有验证示例都将运行多次，取其平均表现，从而最大限度减少由于意外的操作系统行为造成的结果差异。另外，所有测试都在一个 独立的系统上运行，该系统上没有其它用户和其它运行的程序，以保证结果的准确性。为了减少人工错误，测试结果被测量程序直接输出到一个外部文件中，并由一 个图形程序自动来根据这些数据生成对比图。关联程序同时也会检查并使用平均测试结果，抛弃异常数据。总之，尽量使测试结果能够客观真实的反映不同程序的性 能表现。

　　高 效编程

　　一个程序执行的指令越少它运行的速度就越快，这个观点并非笔者首先提出，也不具有争议性，这是在多年的计算机科学发展已经证明的一个常识。无论 你的程序使用什么语言编写，它通常都适用这个原则，当然使用Java和C++编写的程序也不例外，人们通常使用这两种编程语言来开发大型、可升级、快 速的 分布式系统。

　　从实际效果来看，要想成功的实现一个运行最快、消耗资源最少的程序，通常要求我们使用一个通用语言(诸如Java或C++)并根据特定编程环境 来手动来进行编程。与之相对应的是，单纯依靠配置普通的组件，不根据特定环境进行程序设计和实现，程序优化任务或者借助于现成的代码库或编辑器的自动优化 功能，或者借助于JVM技术中高级功能。的确，在很多环境下后面的做法可能也足够了，但是依靠这种方法你编写出来的程序不一定具有最 佳的性能。从根本上来 说，定制化的设计、编码和优化，再加上这些过程中程序员的创新技能，这些因素加起来将可以做出运行最快和扩展性最强的程序。

　　普通排序VS计数排序

　　下面我们将通过对比两种排序算法来验证上面的结论，其中一个是标准的Java排序程序，另一个则是根据具体情况定制化的排序程序。第 一个例子是 简单的对n个正整数排序，数值在0到k之间。在Java中我们可以通过简单的使用Collections(集合)或Arrays(数组)类来实现这个目 的，如下例所示：

　　1 /**

　　2 * 使用Collections的sort方法来对输入的正整数进行排序

　　3 */

　　4 public ArrayList sortInts(ArrayList inputSequence)

　　5 {

　　6 Collections.sort(inputSequence);

　　7 return inputSequence;

　　8 } /**

　　9

　　10

　　11 *使用Arrays类来对一个整数数字进行排序

　　12

　　13 */

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

　　15 {

　　16 Arrays.sort(inputSequence);

　　17 return inputSequence;

　　18 }

　　在Java文档中这样描述Collections.sort程序：

　　“该排序算法是一个经过修改的合并排序算法(其中如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并)。此算法提供可保证的n log(n)性能。 此实现将指定列表转储到一个数组中，并对数组进行排序，在重置数组中相应位置处每个元素的列表上进行迭代。这避免了由于试图对适当位置上的链接列表进行排 序而产生的n2 log(n)性能。”

　　Collections.sort程序被设计可以支持任意元素类型，因此这个排序算法不能利用我们例子中专门针对正整数排序的一些特点。而Arrays.sort程序的文档描述则显示它是一个更适合对整数进行排序的算法：

　　“将特定的整数数组进行排序，得到一个有序整数数组。该排序算法是一个经过调优的快 速排序法，改编自Jon L. Bentley和M.Douglas McIlroy合著的《Engineering a Sort Function", Software-Practice and Experience》 Vol. 23(11) P. 1249-1265 (November 1993)。此算法在许多数据集上提供 n*log(n) 性能，这导致其他快 速排序会降低二次性能。

　　这个Arrays.sort算法已经针对整数排序进行了改进，与我们本例中的特定要求已经更接近了一步，因此它的效率要比Collections.sort更高一些。但是，O(nlogn)的性能依然非常高，我们还有方法来改进它。

　　现在，如果我们要专门针对正整数来设计一个最优化的排序程序， 那么我们要记住整数类型具有以下特点：

　　1、与实数或浮点数不同的是，两个相邻整数之间没有其它整数。例如有两个整数a和b，如果a+1=b，那么你不可能再找到第三个整数x能满足a

　　填写下面表单即可预约申请免费试听java课程!害怕学不会?助教陪读，随时解惑!担心就业?一地学习，可全国推荐就业!

　　2、这些整数没有关联数据，它们不是元组(tuples)。因此在排序过程中，同样大小的元素可以不用重复排序过程，这可以提高 效率。

　　考虑到我们输入序列具有以上两个特点，我们可以编写一个非常不同的排序程序，计数排序的改进版，如Listing 1所示。

　　listing1

　　1 /**

　　2 * 实现计数排序算法

　　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 // 指定一个数组

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

　　19

　　20 // 计算输入序列中每一个数出现的次数

　　21 for(int i : inputSequence)

　　22 {

　　23 counts[i] += 1;

　　24 }

　　25

　　26 // 获得排序数字序列

　　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 }

　　下面我们来简单对这个程序的算法进行介绍，这个程序首先获得输入序列中最大的数值k，并以它为最大下标来创建一个数组(长度为k+1)。然后再 次检查输入序列，并确定每一个数值在序列中出现的次数，并将其记录在counts数组中相应下标位置。举个例子来说，如果输入的数值序列是 [3,1,4,7,1,4,0],那么我们将得到一个长度为8的计数数组counts[]，包含下列值[1,2,0,1,2,0,0,1]。最后程序根据 计数数组来重写输入数列inputSequence。在这个例子中得到的数值是[0,1,1,3,4,4,7] 。

　　从以上算法中我们可以明白为什么这个算法不能用来对实数或浮点数进行排序;因为它们的输入序列中的最大数值不能告诉我们要创建多少长度的技术数 组，而且这个计数排序也不能用来对整数键值的元组进行排序，因为算法执行最后一步的时候，重写了最初的输入元素，破坏了元素的最初数值。

　　这个改进版的计数排序算法对输入序列共进行了三次遍历：第 一次是发现其最大值(即k)，这个操作的时间复杂度是O(n)。它分配了一个最大下标 为k的数组，尽管这只是一个简单的数组指定操作，我们也认为它的时间复杂度为O(k)。然后它第二次对输入数值进行遍历，来计算不同数值出现的次数。最后 它使用排序的序列来对覆盖原始输入序列，时间复杂度为O(n)。因此这个算法总的时间复杂度为O(n+k)，空间复杂度为O(k).因此这个计数排序不仅 仅与要排序的数值多少有关系，还与其中最大数值大小有关系。