Warum ist Pypys Deque so langsam? ⇐ Python

[Anonymous]

Hier ist ein (etwas chaotischer) Versuch des Projekt-Euler-Problems 49.

Ich sollte direkt sagen, dass die Deque keine gute Wahl war! Meine Idee war, dass eine Verkleinerung der Menge der Primzahlen zum Testen der Zugehörigkeit zu einer Beschleunigung der Schleife führen würde. Als mir jedoch klar wurde, dass ich einen Satz hätte verwenden sollen (und mir keine Gedanken über das Entfernen von Elementen machen sollen), erhielt ich eine 60-fache Beschleunigung.

Code: Select all

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

Wie auch immer, bevor ich daran dachte, ein Set zu verwenden, habe ich es in Pypy ausprobiert. Ich fand die Ergebnisse ziemlich überraschend:

Code: Select all

$ 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

Warum ist Pypy bei diesem Code mehr als fünfmal langsamer? Ich würde vermuten, dass Pypys Version der Deque der Schuldige ist (weil sie auf der Set-Version schneller läuft), aber ich habe keine Ahnung, warum das so ist.