使用定制编程来最大化Java程序性能

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

　　验证方法介绍

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

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

　　高效编程

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

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

　　普通排序VS计数排序

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

　　　在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所示。

　　listing1

　　下面我们来简单对这个程序的算法进行介绍，这个程序首先获得输入序列中很大的数值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).因此这个计数排序不仅仅与要排序的数值多少有关系，还与其中很大数值大小有关系。

　　下面我们通过图形来对比三种排序程序的表现，分别取不同数量、不同很大输入数值的情况进行对比。

　　图1显示了对0到100范围内的整数(k=100)进行排序的结果，输入序列个数在20000到1000000之间。

　　
图1

　　图2中对排序数值的大小范围进行了扩大为0到10000(k=10000)。

　　
图2

　　后面，我们将k提高到1000000，对比结果如图3所示。

　
图3

　　我们可以看到计数排序明显比Java库中使用的算法更快速。或许简单的整数排序不会有多大用处，下面我们比较对整数元组进行排序的不同。

　　普通排序VS鸽巢(Pigeon-Hole)排序

　　接下来，我们放宽对输入序列的一个限制，允许输入元组作为输入数组的元素，这意味着我们必须在输入数列中保存元素的标识。在这个例子中，我们需要对n个有序整数对进行排序，其中整数对中的第一个值作为排序键(key)。整数对的第二个值被看做“相关数据”。

　　在Listing2中我们显示了使用Collections和Arrays类如何进行排序，从例子中我们看到了OrderedPair类，它包含两个整数，其中k是排序的键值。我们的排序程序所要求的接口是PigeonHoleable。

　　在Listing 3中我们同样使用了Collections和Arrays类来对这些有序对进行排序，但是这次我们还使用了一个可以比较键值的比较器comparator。

　　Listing 3

　　在我们的定制程序中包含了鸽巢排序的改进，如Listing 4所示。

　　和前面我们所使用的计数排序一样，这个程序开始先查找输入序列中的很大键值，然后使用它来创建一个计数数组counts。这个输入数列然后再次被检查，在计数数组中相应位置再累加每一个键值出现的次数。接下来是与前面计数排序的不同之处，利用counts数组中的数值，我们创建一个元素为数组的数组slots，并将counts数组的所有值归零。如Figure 1所示。

　　Figure 1

　　然后程序对输入数列进行遍历，并直接将每一个输入序列中元素的插入到slots数组中，使用键值作为第一个索引，counts数组中的值作为第二个索引。在这个循环中，counts数组被用于其它用处，来保存“下一个索引”。这就是为什么每一个counts数组的值要被归零的原因。过程如Figure 2所示。

　　Figure 2

　　后面对这个二维数组的数组进行遍历，按顺序读出每一个指向，就得到了我们要排序的结果。即，如果我们最初的输入序列是(3,6)(1,2)(4,8)(7,1)(1,5) (4,9)(0,4)，则得到排序的结果为(0,4)(1,2)(1,5)(3,6)(4,8)(4,9)(7,1)。

　　这个鸽巢排序算法的实现共对原始序列进行了四次遍历，每一次所需要的时间复杂度为O(n).一旦发现很大值(k)后，第二次累加不同数值出现的次数，第三次则插入指向到子数组中，后面将循环读取子数组的指向到排序后的列表中。在空间方面，这个算法分配了两个数组，counts和slots，大小均为k，另外slots中的每一个子数组也分配空间，空间复杂度为O(n)。这样总体时间复杂度和内存使用约为O(n+k)。和我们前面描述的技术排序一样，这个鸽巢排序是一个可靠的排序，不仅与排序元素数量有关，而且和输入元素中数值的大小有关。

　　现在，我们再次对三种排序方法通过图形来比较其性能，同样分别取不同数量、不同很大关键值的情况进行对比。

　　图4中显示关键值大小在0到100，排序元素数量在20000和1000000之间的时间。

　
图4

　　图5中关键值范围在0到10000之间

图5

　　图6中关键值k=1000000

　　
图6

　　从图6中我们可以看到鸽巢排序在20000

　　Java中Arrays对有序对的排序明显要性能低的多，而Collections排序则表现好一些，比Arrays排序快很多。但是它们两个都比鸽巢排序要慢的多，尤其对于键值k比较小的情况下，鸽巢排序要比Arrays排序性能提高15到17倍，比Collections排序要提高12到13倍。当键值k变大的时候，性能提高倍数不再那么明显，大约有3-4倍，原因可能是指定内存的时间随着k值的增大而变得非常耗时。

　　通过预先分配必要内存来执行排序或重用的方法，还有可能提高这个排序算法的性能，不过这是否可行要取决于要排序的元素的特点。

　　结论

　　验证本文观点的例子还有很多，本文只是列举了其中两个。如果我们设定了一个最短执行时间的性能要求，如果认为每一个指令在一定时间内被执行，那么具有最少指令的程序无疑将运行最快。可能有多个最优性能的程序和做个接近最优性能的程序。

　　这些最优性能程序可以完全通过手工编程实现，不过这可能是不现实的;或者通过自动优化技术，诸如优化编译器，来分析程序并产生高效代码。自动优化技术以前主要是分析代码的静态结构，但是现在的Java环境也开始通过在执行的时候收集统计数字来验证动态程序行为，例如使用诸如逃逸分析(escape analysis)，然后迅速的动态重新编译执行代码。无论哪一种情况，只有信息在程序中明白的表示出来，或者可以通过对程序行为推理而获得，它们才可以被优化决策过程来使用。某些优化是不可能或不现实能够自动产生的，因为需要使用内容相关的特定知识，这些知识不可能清楚的编写在程序中，不能从程序行为中推理而出。

　　因此重申一下本文开头的观点：要想真正获得很大性能的程序，除了依靠自动优化技术外，你还有必要在编程的时候使用巧妙的数据结构和针对特定问题而设计的新优化算法。

评论加载中... 内容： 评论者： 验证码：