python - 为什么这个切片代码比更多的过程代码更快？

Question

我有一个 Python 函数，它接受一个列表并返回一个生成器，生成每个相邻对的二元组，例如

>>> list(pairs([1, 2, 3, 4]))
[(1, 2), (2, 3), (3, 4)]

我考虑过使用 2 个切片的实现:

def pairs(xs):
    for p in zip(xs[:-1], xs[1:]): 
        yield p

还有一个以更程序化的风格编写的:

def pairs(xs):
    last = object()
    dummy = last
    for x in xs:
        if last is not dummy:
            yield last,x
        last = x

使用 range(2 ** 15) 作为输入进行测试会产生以下时间(您可以找到我的测试代码和输出 here ):

2 slices: 100 loops, best of 3: 4.23 msec per loop
0 slices: 100 loops, best of 3: 5.68 msec per loop

无切片实现的部分性能损失是循环中的比较(if last is not dummy)。删除它(使输出不正确)可以提高其性能，但它仍然比 zip-a-pair-of-slices 实现慢:

2 slices: 100 loops, best of 3: 4.48 msec per loop
0 slices: 100 loops, best of 3: 5.2 msec per loop

所以，我很难过。为什么将 2 个切片压缩在一起，有效地并行遍历列表两次，比迭代一次、更新 last 和 x 更快？

编辑

Dan Lenski proposed第三个实现:

def pairs(xs):
    for ii in range(1,len(xs)):
        yield xs[ii-1], xs[ii]

这是它与其他实现的比较:

2 slices: 100 loops, best of 3: 4.37 msec per loop
0 slices: 100 loops, best of 3: 5.61 msec per loop
Lenski's: 100 loops, best of 3: 6.43 msec per loop

它甚至更慢!这让我感到困惑。

编辑 2:

ssm suggested使用 itertools.izip 而不是 zip，它甚至比 zip 更快:

2 slices, izip: 100 loops, best of 3: 3.68 msec per loop

所以，izip 是迄今为止的赢家!但仍然出于难以检查的原因。

Answer 1

本主题其他地方有很多有趣的讨论。基本上，我们开始比较这个函数的两个版本，我将用以下愚蠢的名称来描述它:

1. “zip-py”版本:

   def pairs(xs):
       for p in zip(xs[:-1], xs[1:]): 
           yield p
   

2. “loopy”版本:

   def pairs(xs):
       last = object()
       dummy = last
       for x in xs:
           if last is not dummy:
               yield last,x
           last = x
   

那么为什么 loopy 版本变慢了呢？基本上，我认为这归结为几件事:

1. loopy 版本明确地做了额外的工作:它在内部循环的每个对生成迭代中比较两个对象的身份(if last is not dummy: ...)。

   • @mambocab 的编辑显示不进行此比较确实会产生循环版本
     稍微快一点，但并没有完全缩小差距。
     
     

2. zippy 版本在编译后的 C 代码中做的事情比 loopy 版本在 Python 代码中做的更多:

   • 将两个对象组合成一个元组。 loopy 版本 yield last,x，而在 zippy 版本中，元组 p 直接来自 zip，所以它只是 产量 p。

   • 将变量名称绑定(bind)到对象:loopy 版本在每个循环中执行两次，在 for 循环中分配 x 和 last=x。 zippy 版本只在 for 循环中执行一次。

3. 有趣的是，zippy 版本实际上以一种方式做了更多的工作:它使用两个 listiterator， iter(xs[:-1]) 和 iter(xs[1:])，它们被传递给 zip。 loopy 版本仅使用一个 listiterator (for x in xs)。

   • 创建一个 listiterator 对象(iter([]) 的输出)可能是一个高度优化的操作，因为 Python 程序员经常使用它。
   • 遍历列表切片 xs[:-1] 和 xs[1:] 是一种非常轻量级的操作，与遍历整个列表。本质上，它只是意味着移动迭代器的起点或终点，而不是改变每次迭代发生的事情。