《算法技术手册》一2.5 基准测试

2.5 基准测试

Python运算符可以很快地执行指数运算。2**851的计算结果如下所示：
150150336576094004599423153910185137226235191870990070733
557987815252631252384634158948203971606627616971080383694
109252383653813326044865235229218132798103200794538451818
051546732566997782908246399595358358052523086606780893692
34238529227774479195332149248
在Python中，计算与平台无关。也就是说，在大多数平台下，使用Java或者C语言计算2851会导致数值溢出。但是使用Python，就可以快速得到上述示例中的结果。那么，Python抽象化底层的架构究竟是一个优点还是缺点呢？考虑以下两个假设：
假设H1

假设H2
大数（例如在之前处理的数）能够像其他数一样使用同样的方式进行处理，例如123 827 或者997。

奇怪的是，性能似乎有着不同的表现，第一种表现是在x小于16时，第二种表现是x在145左右时，第三种是在x大于200之后。这些行为表明Python在使用运算符计算幂次时使用了平方幂（exponentiation by squaring）算法。而使用for循环手动计算2x的性能为平方级。
为了验证假设H2，我们进行了另外一个实验，首先预处理计算出2n，然后计算*2n所需要的时间。10 000次试验后总的执行时间如图2-7所示。
为什么图2-7的点不在一条直线上？当x等于多少时，这条线开始不为直线呢？可以看出乘法运算符（*）被重载过，因为这个操作会根据乘数的不同而做不同的事情，乘数可以是浮点数、单字的整型、多字的大整数，或为这些类型的组合形式。

图2-7：大数乘法的执行时间
第一个转折点发生在x={64,65}时，这与大型浮点数的存储方式相关。需要再次说明的是，算法的计算过程可能还会存在一些预料之外的缓慢之处，只有通过这样的性能测试工作才能发现它们。