以 SICP 风格创建素数生成器

Question

在以后的课程中，我将有一门使用 Python 的学科，重点是使用序列和生成器以及诸如此类的东西 inn Python。

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

(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：在中已经提出了筛生成器的实现方案，但它明确处理筛中的先前素数。而在惰性列表范式中，objective 是从实际执行操作的顺序中抽象出来的。

Answer 1

在 Python 解决方案中，sieve 将是一个函数，它接受一个生成器并且它本身就是一个生成器，如下所示：

from itertools import count, islice

def sieve(gen):
    for n in gen:
        if n%2 == 0:
            yield n

def evens(start=2, limit=None):
    return islice(sieve(count(start)), limit)

for n in evens(limit=10):
    print(n)

2
4
6
8
10
12
14
16
18
20

...除了要生成素数之外，我们不仅要检查被 2 整除，还要检查每个给定点处小于 n 的所有事物的整除性。我们可以做得更好，因为对于每一对除数 a • b = n，其中一个除数 ≤ sqrt(n).

Python 与 Scheme 的不同之处在于 Python 不鼓励递归，对递归深度的限制很小。 See this question.

所以，在 sieve 内部循环是个好主意。

from itertools import count, islice
from math import sqrt

def sieve(gen):
    for n in gen:
        sqrt_n = int(sqrt(n))
        for d in count(2):
            if d > sqrt_n:
                yield n
                break
            if n % d == 0:
                break

def primes(start=2, limit=None):
    return islice(sieve(count(start)), limit)

for p in primes(limit=20):
    print(p)

我们可以利用生成器的状态特性。我们可以在生成器中保留先前生成的素数列表，以 space 换取更快的运行时间。

def primes():
    primes = [2]
    yield 2
    for n in count(3):
        sqrt_n = int(sqrt(n))
        for p in primes:
            if p > sqrt_n:
                primes.append(n)
                yield n
                break
            if n % p == 0:
                break

这允许生成中等大小的素数：

In [56]: %time nth(primes(), 1000000)
CPU times: user 40.9 s, sys: 142 ms, total: 41.1 s
Wall time: 41.2 s
Out[56]: 15485863

有关真正智能的实施，请参阅 Simple Prime Generator in Python。

Answer 2

对于你的第一个版本，你可以只使用 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）

对于您的循环版本，删除递归调用，只需堆叠 filters:

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

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

或者，对于纯迭代解决方案，您可以存储已见素数集并检查其中 any 是否为除数。（两种递归变体基本上也存储这组素数，只是它们将其隐藏在嵌套的 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 从 sieve 下一级获得 next 值，依此类推，每一个都添加 另一个层筛子在每次迭代中，导致sieve-stack的高度在每次迭代中达到两倍。

以 SICP 风格创建素数生成器

Creating a generator for primes in the style of SICP

python

python-3.x

generator

sicp

lazy-sequences