9

M. O'Neill の素晴らしい論文に従って、Python でエラトステネスのふるいの怠惰な無限バージョンをいくつか実装してみました。論文ではより高速に実行されるはずであると主張されているヒープベースのバージョンが、実際には 2 倍以上遅かったことに驚きました。

この論文には 2 つの例が含まれています。1 つは dict に基づいており、私が (Haskell から) 翻訳したものです。

from itertools import count
def dict_sieve():
    yield 2
    yield 3
    candidates = count(5, 2)
    composites = {9:{3}}  # map composites to their prime factors

    for candidate in candidates:
        try:
            factors = composites.pop(candidate)
        except KeyError:  # if it's not in the dict, it's prime
            yield candidate
            composites[candidate**2] = {candidate}  # Euler's optimization: start from prime**2
        else:
            for prime in factors:  # go through the prime factors and increment their keys
                try:
                    composites[candidate+prime*2].add(prime)  # use prime*2 because we are ignoring evens
                except KeyError:
                    composites[candidate+prime*2] = {prime}

この論文の 2 番目の例では、プライオリティ キューをデータ構造として使用する方法を示しています。また、単純なインクリメントではなく遅延リストを使用しますが、これは公正なテストのために行っていません。itertools.count(さらに、私は遅延リストにのインスタンスを使用していましたが、実行が少し遅くなることがわかりました)。

from itertools import count
from heapq import heappush, heapreplace
def heap_sieve():
    yield 2
    yield 3
    candidates = count(5,2)
    composites = [(9, 3)]  # a priority queue of composite/factor pairs, keyed by composite

    for candidate in candidates:
        prime_flag = True
        while composites[0][0] == candidate:  # loop because there may be duplicates
            prime_flag = False  # signal to the if statement below
            composite, prime = composites[0]
            heapreplace(composites, (composite + prime*2, prime))

        if prime_flag:
            yield candidate
            heappush(composites, (candidate**2, candidate))

ここでは再現されていませんが、制限を下回るすべての素数のリストを生成する「熱心な」バージョンとともに、2つの時間を計りました。

In [44]: from itertools import islice

In [45]: %timeit list(islice(dict_sieve(), 100000))
    ...: %timeit list(islice(heap_sieve(), 100000))
    ...: %timeit eager_sieve(1299710)  # 1299709 is the 100,000th prime
    ...: 
1 loops, best of 3: 2.12 s per loop
1 loops, best of 3: 4.94 s per loop
1 loops, best of 3: 677 ms per loop

「熱心な」バージョンがはるかに高速であることは驚くべきことではありません。基本的には、メモリ使用量、上限を指定しなければならないという不便さ、および CPU 時間の間のトレードオフです。しかし、紙がより効率的であると主張しているときに、バージョンがはるかに遅いことに驚きました. heapq私の実装に問題がありますか？それとも、私たち全員が知っているように、口述が超高速でheapqある (そして比較的遅い) ということですか?

4

1 に答える 1

7

実際、ディクショナリ ベースのアプローチは、ヒープ キュー ベースのアプローチよりも高速であると予想されます。ヒープの挿入および置換操作は O(log n) ですが、辞書の挿入および置換操作は O(1) です。

実際、論文の著者が別の主張をしていると聞いて驚きました。しかし、実際にはそうではありません。a はhash mapData.Mapとして実装されていると想定しましたが、実際には、サイズ バランスの取れたバイナリ ツリーです。したがって、そのパフォーマンス特性は、ヒープ キューのパフォーマンス特性と非常によく似ています。違いは、ヒープ キューからの最小キーの取得が O(1) であることです。これにより、ふるいコードの一部が高速化されますが、ハッシュ マップはさらに高速です。

于 2012-11-19T22:51:17.330 に答える