Tại sao pypy của deque quá chậm?

Question

Đây là một nỗ lực (hơi lộn xộn) tại Project Euler Problem 49.

Tôi nên nói hoàn toàn rằng deque không phải là lựa chọn tốt! Ý tưởng của tôi là việc thu hẹp số lượng các số nguyên tố để kiểm tra thành viên sẽ làm cho vòng lặp tăng tốc. Tuy nhiên, khi tôi nhận ra rằng tôi nên đã sử dụng một set (và không phải lo lắng về việc loại bỏ các yếu tố), tôi đã có một tốc độ 60x.

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 

Dù sao, trước khi tôi nghĩ sử dụng set, tôi đã dùng thử trong Pypy. Tôi thấy kết quả thật đáng ngạc nhiên:

$ 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 

Tại sao Pypy chậm hơn năm lần so với mã này? Tôi đoán rằng phiên bản deque của Pypy là thủ phạm (vì nó chạy nhanh hơn trên phiên bản set), nhưng tôi không biết tại sao lại như vậy.

Answer 1

Phần chậm là inc1 in primes and inc2 in primes. Tôi sẽ xem xét lý do tại sao PyPy lại quá chậm (nhờ vào báo cáo lỗi hiệu suất, về cơ bản). Lưu ý rằng khi bạn đề cập đến mã có thể được thực hiện cực kỳ nhanh hơn (cả trên PyPy và trên CPython) --- trong trường hợp này, chỉ bằng cách sao chép de232 primes vào một tập hợp ngay trước vòng lặp for.

Answer 2

Bạn nên mong đợi các thử nghiệm thành viên trong một deque (với đặc tính hiệu suất python) chậm, vì bất kỳ kiểm tra thành viên nào trong danh sách đều bao gồm quét tuyến tính. Ngược lại, thiết lập là một cơ sở dữ liệu được tối ưu hóa cho các thử nghiệm thành viên. Theo nghĩa đó, không có lỗi ở đây.