将while转换为生成器时性能下降3.4倍

Question

发生了什么？有人能给我解释一下这里发生了什么吗？我在紧密循环中做了一些更改：

##            j=i
##            while j < ls - 1 and len(wordlist[j]) > lc: j+=1
            j = next(j for j in range(i,ls) if len(wordlist[j]) <=  lc)

注释掉的while版本运行整个程序的时间是625毫秒，而下一个生成器版本运行整个程序的时间是2.125秒。

是什么原因导致这个更符合Python风格的版本性能如此糟糕呢？

编辑：也许是因为使用了psyco模块？当然，至少在没有psyco的Python 2.7中，下一版本的运行时间是2.141秒，这几乎和有psyco的Python 2.6一样。

在删除了*.pyc文件后，我发现代码没有变慢。然后当我也从库模块中删除了psyco的导入后，使用没有psyco的2.6版本的时间也一样，结果显示非psyco版本和psyco版本（因为现在库例程也变慢了，它的时间也变得相关：）

非psyco：

1. while：库准备时间：532毫秒，总运行时间2.625秒
2. next：库准备时间：532毫秒，总运行时间（time.clock()）：2.844秒（使用xrange的版本同样的墙面时间）

psyco：

1. while：库准备时间：297毫秒，总运行时间：609..675毫秒
2. next：库准备时间：297毫秒，总运行时间：1.922秒（程序中到处使用range而不是xrange的版本：1.985秒）

在WindowsXP AMD Sempron 3100+系统上运行，内存2GB。用两个全局变量计数循环和调用：

    j=i
    callcount += 1
    while j < ls - 1 and len(wordlist[j]) > lc:
        j+=1
        loopcount += 1

使用psyco的测试输入结果：

Finished in 625 ms
Loopcount: 78317
Callcount: 47970
Ration: 1.633

所以这个循环是在紧密循环中，但平均只执行了几次（注意到两个全局计数器的增加并没有让psyco中的代码变慢）

结论：尽管算法对词汇长度非常敏感，这导致我在这个循环中排除了一些不可能的单词，但之后基本的递归情况是通过字典查找来检查的，这个查找的复杂度是O(n)，因此之前的优化变得不那么有益，即使在输入更长的情况下，把调用计数器放在函数开头显示调用计数不受词汇长度的影响，但外部循环计数略有减少（原始发布的代码在if语句的elif部分）。

更长的运行时间（29,372个解）使用while循环并且整个循环被移除（用i代替j）（库准备时间312毫秒）：

1. 没有循环：elif分支计数：485488，外部循环计数：10129147，比例：0.048，运行时间6.000秒（没有计数器：4.594秒）
2. 有循环：循环计数：19355114，外部计数：8194033，比例：0.236，运行时间5.704秒（没有计数器：4.688秒）

（没有循环、计数器和psyco的运行时间：32.792秒，库608毫秒）

所以在没有额外计数器的情况下，这个循环的好处在更困难的情况下是：（4688-4594）*100/4688.0 % = 2%

这让我想到了反转另一个早期的优化，我在DaniWeb上曾对此感到困惑。代码的早期版本运行得更快，当最小单词大小是全局变量而不是参数时。根据文档，本地变量调用更快，但显然在加重递归的成本超过了这一点。现在在更困难的情况下，这种优化的反转带来了更预期的性能表现，没有优化单词长度的情况下：使用psyco的运行时间为312毫秒准备时间，总运行时间4.469..4.484秒。所以这让代码更简洁，并在这种情况下带来了比移除循环更大的好处。而将参数放入使用while循环的版本中，运行时间变化不大（库准备代码的变化变得更大）

**What I learned from this: If you do n optimizations for speed 
you must check the first n-1 optimizations after doing nth one**

Answer 1

这两者并不相同。

j=i
while j < ls - 1 and len(wordlist[j]) > lc: 
    j+=1

这个代码会在 wordlist[j] 小于等于 lc 的时候立刻停止循环。如果 wordlist 列表中的第一个单词的长度小于或等于 lc，循环甚至可能一次都不执行。

j = next(j for j in range(i,ls) if len(wordlist[j]) <=  lc)

这个代码会继续遍历从 i 到 ls 的整个范围，不管列表中单词的长度是多少。

编辑: 忽略上面的内容 - 正如 Amber 指出的，调用 next() 意味着生成器表达式只会计算到返回第一个结果为止。在这种情况下，我怀疑时间差异是因为使用了 range() 而不是 xrange()（除非这是 Python 3.x）。在 Python 2.x 中，range() 会在内存中创建完整的列表，即使生成器表达式只返回第一个值。

Answer 2

我发现使用生成器有时候比直接生成整个列表要慢，这听起来有点反常。我通过简单地加上一个[]符号，就解决了性能瓶颈。

比如对比一下这些：

$ python -m timeit -n 1000 "' '.join(c for c in 'hello world')"
1000 loops, best of 3: 6.11 usec per loop
$ python -m timeit -n 1000 "' '.join([c for c in 'hello world'])"
1000 loops, best of 3: 3.79 usec per loop

在这种简单的情况下，先生成整个列表几乎快了两倍，而不是使用生成器！

编辑：正如Thomas Wouters在评论中提到的，生成器在这里慢的原因是因为这个例子太简单了。为了公平起见，这里有他的测试，生成器明显更快：

$ python -m timeit -s "s = 'hello world' * 10000" -s "class C: pass" "for i in (C() for c in s): pass"
10 loops, best of 3: 33.6 msec per loop
$ python -m timeit -s "s = 'hello world' * 10000" -s "class C: pass" "for i in [C() for c in s]: pass"
10 loops, best of 3: 172 msec per loop