Dlaczego Deque Pypy jest tak wolny?

Question

Oto (nieco niechlujnie) próba na Project Euler Problem 49.

Muszę powiedzieć wprost, że deque nie był dobrym wyborem! Mój pomysł polegał na tym, że zmniejszenie liczby liczb pierwszych w celu sprawdzenia członkostwa spowodowałoby przyspieszenie pętli. Jednak gdy zdałem sobie sprawę, że powinienem był użyć set (i nie martw się o usuwanie elementów), uzyskałem przyspieszenie 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 

W każdym razie, zanim pomyślałem użyć set, próbowałem go w pypy. Wyniki okazały się dość zaskakujące:

$ 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 

Dlaczego Pypy jest ponad pięć razy wolniejszy w tym kodzie? Domyślam się, że winowajcą jest wersja Pypy deque (ponieważ działa ona szybciej w wersji set), ale nie mam pojęcia, dlaczego tak jest.

Answer 1

Powolna część to inc1 in primes and inc2 in primes. Spojrzę na to, dlaczego PyPy jest tak powolny (głównie dzięki raportowi o błędzie wydajności). Zauważ, że jak już wspomniałeś, kod może być niesamowicie szybszy (zarówno w PyPy, jak i na CPython) - w tym przypadku, po prostu kopiując deque primes do zestawu tuż przed pętlą .

Answer 2

Powinieneś oczekiwać, że testy członkostwa w deque (z charakterystyką wydajności pythona) będą wolne, ponieważ każdy test członkostwa na liście wymaga skanowania liniowego. Natomiast zestaw to baza danych zoptymalizowana do testów członkostwa. W tym sensie nie ma tu błędu.