探究数组排序提升Python程序的循环的运行效率的原因

早上我偶然看见一篇介绍两个Python脚本的博文，其中一个效率更高。这篇博文已经被删除，所以我没办法给出文章链接，但脚本基本可以归结如下：
fast.py
 

import timea = [i for i in range(1000000)]sum = 0t1 = time.time()for i in a:  sum = sum + it2 = time.time()print t2-t1

slow.py
 

import timefrom random import shufflea = [i for i in range(1000000)]shuffle(a)sum = 0t1 = time.time()for i in a:  sum = sum + it2 = time.time()print t2-t1

如你所见，两个脚本有完全相同的行为。都产生一个包含前一百万个整数的列表，并打印对这些整数求和的时间。唯一的不同是 slow.py 先将整数随机排序。尽管这看起来有些奇怪，似乎随机化足够将程序明显变慢。在我机器上，运行的Python2.7.3， fast.py 始终比 slow.py 快十分之一秒（fast.py 执行大约耗时四分之三秒，这是不平常的增速）。你不妨也试试看。（我没有在Python3上测试，但结果应该不会差太多。）

那为什么列表元素随机化会导致这么明显的减速呢？博文的原作者把这记作“分支预测（branch prediction）”。如果你对这个术语不熟悉，可以在 StackOverflow 的提问中看看，这里很好地解释了这个概念。（我的疑虑是原文的原作者遇到了这个问题或者与此类似的问题，并把这个想法应用到不太适合应用的Python片段中。）

当然，我怀疑分支预测（branch prediction）是否是真正导致问题的原因。在这份Python代码中没有顶层条件分支，而且合乎情理的是两个脚本在循环体内有严格一致的分支。程序中没有哪一部分是以这些整数为条件的，并且每个列表的元素都是不依赖于数据本身的。当然，我还是不确定python是否算得上足够“底层”，以至于CPU级别的分支预测能够成为python脚本性能分析中的一个因素。Python毕竟是一门高级语言。

因此，如果不是分支预测的原因，那为什么 slow.py 会这么慢？通过一点研究，经过一些“失败的开端”之后，我觉得自己找到了问题。这个答案需要对Python内部虚拟机有点熟悉。

失败的开端：列表vs.生成器（lists and generators）

我的第一想法是Python对排序的列表[i for i in range(1000000)] 的处理效率要比随机列表高。换句话说，这个列表可以用下面的生成器替代：

def numbers():  i = 0  while i < 1000000:    yield i    i += 1

我想这可能在时间效率上更高效些。毕竟，如果Python在内部使用生成器替代真正的列表可以避免在内存中一次保存所有整数的麻烦，这可以节省很多开销。slow.py 中的随机列表不能轻易的被一个简单生成器捕获，所有VM（虚拟机）无法进行这样的优化。