首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》讨论3:线性算法的性能

关灯直达底部

有一些问题的解决看起来明显地需要更多的工作。任何一个8岁大的孩子都知道7+5等于12。那么难一点的问题,37+45呢?一般来说,相加两个n位的数(an……a1+bn……b1)得到一个n+1位的cn+1……c1数字有多难?相加算法使用了如下的原生操作:

例2-2是相加算法的一个Java实现,n位数字被用一个int数组表示。在本节的例子中,我们假设数组中的元素表示一个十进制数d(0≤d≤9)。

例2-2:Java的add实现

只要这个输入数据能够被存储在内存中,add就能够使用两个int数组n1和n2来计算两个数的加法。例2-3有一些小改动,这个实现能够更加高效吗?

例2-3:Java的last实现

这个小改动确实影响了算法的性能吗?让我们考虑其他两个潜在因素,这两个因素将会影响算法的性能。

·编程语言是一个因素,如果这两个实现都能够转换成C程序,那么编程语言是如何影响算法的性能?

·如果这个程序能够在另外一台不同的计算机上执行,那么计算机硬件是如何影响算法性能?

这些实现将会执行10 000次,数的位数从256位到32 768位。数的每一位都是随机产生的。其后,在每次执行中,这两个数都会循环移位,产生两个不同的数进行相加。我们使用了两台计算机:桌面PC和一台高端计算机。并且使用两种不同的编程语言(C和Java)。我们一开始就假设随着数据规模的加倍,算法执行时间也会加倍。我们希望重新确认算法总体行为和计算机、编程语言以及实现无关。

图2-5表示了数据的规模(用x轴表示)与执行10 000次(用y轴表示)的时间(单位是毫秒)的关系。每一次变化都更改了这些配置选项:

图 2-5 在不同的情境下比较add和last的表现

g

C程序将会把调试信息编译进去。

none

C程序不会进行任何优化。

O1,O2,O3

C程序将会按照不同的优化等级进行编译。一般来说,数字越高的意味着更好的优化与更佳的性能。

Java

算法的Java版。

PC-Java

在PC上执行,只有一种配置,之前的那些数据也同样会在高端计算机上执行。

留意在图2-5的左边(标"Desktop PC"),每条计算线的斜率都是近似线性的,这种性质表示X和Y的值之间存在线性关系。在高端计算机执行优化过的代码,计算结果却不能够简单地归为线性,因为需要考虑到高端处理器的重要影响。

表2-3包含了一些图上的数据。本书中提供的代码都会提供这种信息。表2-3的第6行、第7行和最后一行直接对比了HighEnd-C-Last-O3实现[1]在不同数据规模下的性能。性能的比率与预想的很接近,在2左右。假设t(n)是在数据规模为n的情况下,加法算法的实际运行时间。这个增长模型提供了强有力的证据,证明在高端计算机上,使用C语言并且执行O3级优化,计算n位数之和的时间将会在n/11到n/29之间。

计算机科学家认为加法算法是关于输入规模呈线性的。也就是说,对于所有n>n0,存在一个常数c,c>0,使得t(n)≤c*n。事实上我们并不需要知道c或者n0的值。一个争论的焦点是,在做加法时,每一个位都必须检查(考虑一下漏掉的后果),这样的复杂程度是否需要一个线性时间下界。

在加法算法的last实现,我们设置c为1/11,选择n0为256。其他的加法实现应该会有不同的常数,但是它们的总体表现仍呈线性。这个结果让那些认为整数算术是常数操作的程序员大吃一惊。当整数的固定位数用n来表示时(例如16位或者64位),常数时间的加法是可达的。

在考虑算法间差异时,知道算法的阶数比了解常数c更为重要。看似无关紧要的差异会导致不同的性能。加法算法的last实现在不采用取模计算之后显得更加高效。在操作不是2的幂的数时,取模计算是出了名的慢。在数不能被10整除的情况下,二进制计算机做“%10”计算会有较大的开销且并不高效。当然,这并不是说我们可以忽略掉常数c的值。如果我们做大量加法的话,那么c的一点点小的变动都会对程序的性能产生很大的影响。

[1]也就是说,last的C实现O3优化版在高端计算机上的性能如附录基准测试中描述的那样一致。