12

これは、プロジェクトオイラー問題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'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で試してみました。結果はかなり驚くべきものであることがわかりました。

$ 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が5倍以上遅いのはなぜですか？Pypyのバージョンが原因だと思いますがdeque（バージョンでより高速に実行されるためset）、それがなぜであるかはわかりません。

4

2 に答える 2

18

遅い部分はinc1 in primes and inc2 in primesです。PyPyが非常に遅い理由を見ていきます（基本的に、パフォーマンスバグレポートに感謝します）。あなたが言ったように、コードは信じられないほど速くなることができることに注意してください（PyPyとCPythonの両方で）---この場合、ループprimesの直前に両端キューをセットにコピーするだけです。for

于 2012-11-16T17:48:37.263 に答える
0

リスト内のメンバーシップテストには線形スキャンが含まれるため、deque（pythonのパフォーマンス特性を使用）でのメンバーシップテストは遅くなると予想する必要があります。対照的に、setはメンバーシップテスト用に最適化されたデータ構造です。その意味で、ここにバグはありません。

于 2012-11-16T18:21:41.540 に答える