Почему Pypy deque так медленно?

Вот (слегка грязная) попытка Project Euler Problem 49.

Я должен сказать прямо, что 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 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. Я нашел, что результаты выглядят довольно удивительно:

$ 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), но я понятия не имею, почему это так.

Ответы

Ответ 1

Медленная часть inc1 in primes and inc2 in primes. Я посмотрю, почему PyPy так медленно (спасибо за отчет об ошибке производительности, в основном). Обратите внимание, что, как вы уже упоминали, код можно сделать невероятно быстрее (как на PyPy, так и на CPython) - в этом случае просто скопируйте primes deque в набор перед циклом for.

Ответ 2

Вы должны ожидать, что тесты на членство в deque (с характеристиками производительности python) будут медленными, потому что любой тест на членство в списке включает в себя линейное сканирование. Напротив, набор - это структура данных, оптимизированная для тестов на членство. В этом смысле здесь нет ошибки.