☰

Python で効率的な素数の無限生成器を実装するにはどうすればよいでしょうか? 質問する

tag-icon • tag-icon python generator primes
Python で効率的な素数の無限生成器を実装するにはどうすればよいでしょうか? 質問する

これは宿題ではありません、ただ興味があるだけです。

ここでのキーワードは「無限」です。

これを として使用したいのですがfor p in primes()、これは Haskell の組み込み関数だと思います。

したがって、答えは「ふるいをかけるだけ」という単純なものではありません。

まず、連続する素数がいくつ消費されるかはわかりません。では、一度に 100 個の素数を作り出すことができると仮定します。素数の頻度の公式と同様に、同じふるいアプローチを使用しますか?

私は非同時アプローチを好みます。

読んでくださって（そして書いてくださって;)）ありがとうございます！

ベストアンサー1

「もっと先が見えていたら…」

クックブックの関数erat2はさらに高速化できます (約 20 ～ 25%)。

エラト2a

import itertools as it
def erat2a( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

チェックnot (x&1)はそれが奇数であることを確認しますx。しかし、両方 qおよびがp奇数である場合、追加することで、2*p奇数かどうかのテストとともに手順の半分が回避されます。

エラト3

少し余分な装飾を気にしないのであれば、erat2次の変更を加えることで 35 ～ 40% 高速化できます (注: 関数のため、Python 2.7 以上または Python 3 以上が必要ですitertools.compress)。

import itertools as it
def erat3( ):
    D = { 9: 3, 25: 5 }
    yield 2
    yield 3
    yield 5
    MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0,
    MODULOS= frozenset( (1, 7, 11, 13, 17, 19, 23, 29) )

    for q in it.compress(
            it.islice(it.count(7), 0, None, 2),
            it.cycle(MASK)):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = q + 2*p
            while x in D or (x%30) not in MODULOS:
                x += 2*p
            D[x] = p

このerat3関数は、2、3、5を除くすべての素数を30で割った結果が、frozensetに含まれる8つの数だけになるという事実を利用していますMODULOS。したがって、最初の3つの素数を生成した後、7から始めて、のみ
候補のフィルタリングにはitertools.compress関数を使用します。その「魔法」はシーケンスにあります。MASKシーケンスにはMASK15 個の要素 (関数によって選択される 30 個の数字ごとに 15 個の奇数がありますitertools.islice) があり1、7 から始まるすべての候補に対して が付きます。このサイクルは、itertools.cycle関数で指定されたとおりに繰り返されます。
候補のフィルタリングの導入には、別の変更、つまりor (x%30) not in MODULOSチェックが必要です。erat2アルゴリズムではすべての奇数が処理されましたが、アルゴリズムでは r30 個の候補のみが処理されるようになったため、すべてがそのような (偽の) 候補のみであることerat3を確認する必要があります。D.keys()

ベンチマーク

結果

Atom 330 Ubuntu 9.10 サーバー、バージョン 2.6.4 および 3.1.1+ の場合:

$ testit
up to 8192
==== python2 erat2 ====
100 loops, best of 3: 18.6 msec per loop
==== python2 erat2a ====
100 loops, best of 3: 14.5 msec per loop
==== python2 erat3 ====
Traceback (most recent call last):
…
AttributeError: 'module' object has no attribute 'compress'
==== python3 erat2 ====
100 loops, best of 3: 19.2 msec per loop
==== python3 erat2a ====
100 loops, best of 3: 14.1 msec per loop
==== python3 erat3 ====
100 loops, best of 3: 11.7 msec per loop

AMD Geode LX Gentoo ホーム サーバー、Python 2.6.5 および 3.1.2:

$ testit
up to 8192
==== python2 erat2 ====
10 loops, best of 3: 104 msec per loop
==== python2 erat2a ====
10 loops, best of 3: 81 msec per loop
==== python2 erat3 ====
Traceback (most recent call last):
…
AttributeError: 'module' object has no attribute 'compress'
==== python3 erat2 ====
10 loops, best of 3: 116 msec per loop
==== python3 erat2a ====
10 loops, best of 3: 82 msec per loop
==== python3 erat3 ====
10 loops, best of 3: 66 msec per loop

ベンチマークコード

モジュールには、、および関数がprimegen.py含まれています。以下はテスト スクリプトです。erat2erat2aerat3

#!/bin/sh
max_num=${1:-8192}
echo up to $max_num
for python_version in python2 python3
do
    for function in erat2 erat2a erat3
    do
        echo "==== $python_version $function ===="
        $python_version -O -m timeit -c \
        -s  "import itertools as it, functools as ft, operator as op, primegen; cmp= ft.partial(op.ge, $max_num)" \
            "next(it.dropwhile(cmp, primegen.$function()))"
    done
done

おすすめ記事