通过定制编程来最大化Java程序性能.docVIP

　　我们在开发商用系统的时候，通常要让它满足很多性能需求，例如执行速度、资源占用等。在本篇文章中我们将通过几个例子来探讨定制编程在优化性能中的作用。尽管编译器和必威体育精装版的拟机提供了一些工具来实现程序的自动优化，不过要想真正获得最大性能的程序，除了依靠它们外，你还有必要在编程的时候使用巧妙的数据结构和针对特定问题而设计的新优化算法。 　　验证方法介绍 　　在本篇文章中，我们将通过对比验证的方式来证明上述观点的正确性，我们将分别给出标准对比图。关联程序同时也会检查并使用平均测试结果，抛弃异常数据。总之，尽量使测试结果能够客观真实的反映不同程序的性能表现。 　　高效编程 　　一个程序执行的指令越少它运行的速度就越快，这个观点并非笔者首先提出，也不具有争议性，这是在多年的计算机科学发展已经证明的一个常识。无论你的程序使用什么语言编写，它通常都适用这个原则，当然使用J环境来手动来进行编程。与之相对应的是，单纯依靠配置普通的组件，不根据特定环境进行程序设计和实现，程序优化任务或者借助于现成的代码库或编辑器的自动优化功能，或者借助于JVM技术中高级功能。的确，在很多环境下后面的做法可能也足够了，但是依靠这种方法你编写出来的程序不一定具有最佳的性能。从根本上来说，定制化的设计、编码和优化，再加上这些过程中程序员的创新技能，这些因素加起来将可以做出运行最快和扩展性最强的程序。 　普通排序VS计数排序 　　下面我们将通过对比两种排序算法来验证上面的结论，其中一个是标准的Java排序程序，另一个则是根据具体情况定制化的排序程序。第一个例子是简单的对n个正整数排序，数值在0到k之间。在Java中我们可以通过简单的使用Collections(集合)或Arrays(数组)类来实现这个目的，如下例所示： 1 /**2 * 使用Collections的sort方法来对输入的正整数进行排序3 */4 public ArrayListInteger sortInts(ArrayListInteger 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 　　2、这些整数没有关联数据，它们不是元组(tuples)。因此在排序过程中，同样大小的元素可以不用重复排序过程，这可以提高效率。 　　考虑到我们输入序列具有以上两个特点，我们可以编写一个非常不同的排序程序，计数排序的改进版，如Listing 1所示。 　　listi