Pypy为什么这么慢？

这是在Project Euler Problem 49（稍微凌乱）的尝试。Pypy为什么这么慢？

我应该说彻底的认为deque不是一个好的选择！我的想法是缩减素数集来测试成员资格会导致循环加速。但是，当我意识到我应该使用set（而不用担心删除元素）时，我的速度提高了60倍。

from collections import deque 
from itertools import permutations 
from .sieve import sieve_of_erastothenes # my own implementation of the Sieve of Erastothenes 

primes = deque(prime for prime in sieve_of_erastothenes(10000) if prime > 1000 and prime != 1487) # all four-digit primes except 1487 
try: 
    while True: 
     prime = primes.popleft() # decrease the length of primes each time to speed up membership test 
     for inc in xrange(1,10000 + 1 - (2 * prime)): # this limit ensures we don't end up with results > 10000 
      inc1 = prime + inc 
      inc2 = prime + 2*inc 

      if inc1 in primes and inc2 in primes: 
       primestr = str(prime) 
       perms = set(''.join(tup) for tup in permutations(primestr)) # because permutations() returns tuples 
       inc1str = str(inc1) 
       inc2str = str(inc2) 
       if inc1str in perms and inc2str in perms: 
        print primestr + inc1str + inc2str 
        raise IOError # I chose IOError because it's unlikely to be raised 
            # by anything else in the block. Exceptions are an easy 
            # way to break out of nested loops. 
except IOError: 
    pass

反正之前我以为使用set，我尝试了一下在Pypy。我发现结果是相当suprising：

$ time python "problem49-deque.py" 
296962999629 

real 1m3.429s 
user 0m49.779s 
sys 0m0.335s 

$ time pypy-c "problem49-deque.py" 
296962999629 

real 5m52.736s 
user 5m15.608s 
sys 0m1.509s

为什么Pypy五倍这个代码慢？我猜想Pypy版本的deque是罪魁祸首（因为它在set版本上运行得更快），但我不知道这是什么原因。

来源

2012-11-16 Benjamin Hodgson

感谢您提出这个问题！我正要发布一个问题，询问为什么我的代码版本比列表版本慢28％。 –

缓慢的部分是inc1 in primes and inc2 in primes。我会看看为什么PyPy太慢了（基本上感谢性能缺陷报告）。请注意，正如您所提到的，代码可以快得多（在PyPy和CPython上） - 在这种情况下，只需将primes双端队列复制到for循环之前的一个集合即可。

来源

2012-11-16 17:48:37

+1，但我没有接受答案，因为它尚未回答问题。如果你发现问题是什么，请你向我报告？我很想知道是什么原因造成的。 –

后续官方[bug跟踪器]（https://bugs.pypy.org/issue1327） –

官方错误跟踪器移动：https：//bitbucket.org/pypy/pypy/issues/1327（当然它已被永久固定。） –

您应该期望deque（具有python性能特征）的成员资格测试速度较慢，因为列表中的任何成员资格测试都涉及线性扫描。相比之下，set是为会员测试优化的数据结构。从这个意义上说，这里没有错误。

来源

2012-11-16 18:21:41 Marcin

我的问题是关于CPython的'deque'和Pypy的'deque'之间的速度差异。我同意（看问题），在这个特殊情况下'set'是数据结构的正确选择，而'deque'则不是。 –

@poorsod对，但你的问题是“为什么不适当的数据结构表现不佳”。答案是这是不恰当的，而且那是事先知道的。 CPython成员测试代码是高度优化的，但CPython代码不是不错的，因为这不是一个适用于需要很多这样的测试的数据结构。 – Marcin

我对Pypy的会员测试比CPython慢很多的确切原因感到好奇。如果你觉得这个问题不清楚，我会编辑它。 –

Pypy为什么这么慢？

回答

相关问题