python - 以 SICP 风格创建素数生成器

Question

在未来的类(class)中，我将开设一门使用 Python 的学科，重点是使用序列和生成器以及 Python 中的类似东西。

我一直在按照练习列表来练习这些部分。我被困在一个要求质数发生器的练习中。到目前为止，我还没有太多地使用 Python，但我已经阅读并完成了 SICP 中的大部分练习。在那里，他们提出了以下程序，该程序利用埃拉托色尼筛法生成惰性素数列表。

(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

在 Python 中，据我所读，最接近的是生成器所以我尝试将其翻译成以下内容。

import itertools
def sieve(seq):
    n = next(seq)
    yield n
    sieve(filter(lambda x: x % n != 0, seq))

def primes():
    return sieve(itertools.count(2))

print(list(itertools.islice(primes(),10)))

但它只打印[2]。我认为这是因为对 sieve 的递归调用的结果只是被丢弃，而不是像我最初预期的那样再次运行该函数。

为了解决这个问题，我尝试使用循环代替:

def sieve(seq):
    def divisible(n):
        return lambda x: x % n != 0
    while True:
        n = next(seq)
        yield n
        seq = sieve(filter(divisible(n), seq))

在我可以生成前 9 个素数的情况下，这是可行的，但如果我要求生成第十个素数，则会引发 RecursionError。

所以，我的问题是如何改进它以便能够计算更大的素数？

PS:https://stackoverflow.com/a/568618/6571467 中已经提出了筛生成器的实现方案，但它明确处理了筛中的先前素数。而在惰性列表范式中，目标是从操作实际执行的顺序中抽象出来。

Answer 1

对于你的第一个版本，你可以只使用 yield from 从递归调用中产生:

def sieve(seq):
    n = next(seq)
    yield n
    yield from sieve(filter(lambda x: x % n != 0, seq))

(或 for x in sieve(...): yield x 对于旧版本的 Python)

对于你的循环版本，删除递归调用，只需堆叠过滤器:

def sieve(seq):
    while True:
        n = next(seq)
        yield n
        seq = filter(lambda x, n=n: x % n != 0, seq)

这两个版本都适用于前(几乎)1000 个素数，然后还会导致最大递归错误(即使使用循环，因为你有一堆嵌套的 filter 函数)，这可以通过设置更高的递归限制来推迟，但并没有真正阻止——除非不使用递归，或者不使用支持尾调用优化的语言。

或者，对于纯迭代解决方案，您可以存储已见素数集并检查其中的任何是否是除数。 (两种递归变体基本上也存储这组质数，只是它们将其隐藏在嵌套的 filter 调用堆栈中。)

def sieve(seq):
    ps = []
    while True:
        n = next(seq)
        if not any(n % p == 0 for p in takewhile(lambda p: p*p <= n, ps)):
            yield n
            ps.append(n)

所有三个版本都产生相同的结果，但“无递归”的速度(快得多):

>>> %timeit primes(sieve1, 900)
1 loop, best of 5: 297 ms per loop

>>> %timeit primes(sieve2, 900)
1 loop, best of 5: 185 ms per loop

>>> %timeit primes(sieve3, 900)
10 loops, best of 5: 35.4 ms per loop

(使用 n.__rmod__ 而不是 lambda x: x % n != 0 可以很好地提升基于 filter 的那些，但它们仍然慢得多。)

---

附录，关于您的第二种方法即使对于非常小的值也会导致递归错误:我仍然无法解决这个问题，但这是我的理解方式:通过执行 seq = sieve(filter( nondivisible(n), seq)) 而不仅仅是 seq = filter(nondivisible(n), seq)，“顶级”sieve 得到next 值来自 sieve 下一层，依此类推，每一个都在每次迭代中添加另一层筛子，导致高度sieve-stack 在每次迭代中加倍。