Python中的“埃拉托斯特尼筛法”- 为什么heapq比dict慢？

Question

Python中的“埃拉托斯特尼筛法”- 为什么heapq比dict慢？

pythonperformanceheapsieve-of-eratosthenes

8

在阅读M. O'Neill的论文后，我尝试在Python中实现了一些懒惰、无限版本的埃拉托斯特尼筛法。令我惊讶的是，这篇论文声称应该运行得更快的基于堆的版本，在我的电脑上实际上比另一个版本慢了两倍以上。

这篇论文包含两个例子，其中一个基于字典，我已经将其翻译成了以下代码（从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}

本文的第二个示例演示了优先队列作为数据结构的使用。它还使用了惰性列表，而不是简单的增量，出于公平测试的目的，我没有这样做。（此外，我使用了 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))

我对这两个版本进行了时间测试，还有一个“eager”版本，这里没有列出，它会产生一个在给定限制下所有质数的列表：

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 相对较慢）？

- Benjamin Hodgson

@senderle 感谢您的编辑。我一直拼写他的名字，却没有意识到自己拼错了整整一生！ - Benjamin Hodgson

是的，这是一个相当不重要的编辑，但似乎很值得，因为它是一个容易拼错的名字。我自己也不得不仔细检查拼写！ - senderle

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- senderle · Accepted Answer

实际上，应该预期基于字典的方法比基于堆队列的方法更快。堆插入和替换操作是O(log n)，而字典插入和替换操作是O(1)。

事实上，我很惊讶听到论文作者声称相反的事情。但事实并非如此。您假设Data.Map是实现为哈希映射，但实际上它是一个size balanced binary tree。因此，它的性能特征与堆队列的性能特征非常相似。不同之处在于从堆队列中检索最小键是O(1)，这加速了筛选代码的某些部分，但哈希映射仍然更快。