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爲什麼這麼慢？

回答

相關問題