在python中实现“ Eratosthenes筛”时出现麻烦的过滤器行为

Question

我为“ Eratosthenes筛”的试验部门变体提出了以下Python代码：

import itertools

def sieve():
    # begin with all natural numbers above 1
    picker = itertools.count(2)
    while True:
        # take the next available number
        v = next(picker)
        yield v
        # filter from the generator its multiples
        picker = filter(lambda x: x % v != 0, picker)

它没有按我预期的那样工作。

调试它时，我得到一些不知道何时filter被调用的行为：xlambda 的参数得到一个具体的参数，它是picker生成器中的下一个元素。即使查看的文档，我也无法理解这种行为filter。

跑步

s = sieve()
for i in range(5):
    print(next(s))

我得到：

2
3
4
5
6

代替

2
3
5
7
11

更新：

我的错误来自对lambda在Python中的工作方式的误解，更多信息请参见这里。

向lambda添加一个额外的参数可解决此问题：

picker = filter(lambda x, prime = v: x % prime != 0, picker)

Answer 1

我认为问题是因为您依赖于局部变量，并且您创建的生成器（使用filter()）引用了局部变量，当生成器继续迭代时，这些变量会被覆盖。

如果您使用本地函数，它可以正常工作：

def sieve():
    def selector(iterator, d):
        for x in iterator:
            if x % d != 0:
                yield x
    picker = itertools.count(2)
    while True:
        # take the next available number
        prime = next(picker)
        yield prime
        # filter from the generator its multiples
        picker = selector(picker, prime)

尝试list(itertools.islice(sieve(), 10))显示：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

但我确实需要指出，这纯粹是一个教育解决方案，旨在展示事物是如何运作的。我不建议将此解决方案用于任何生产代码。它在内部构建了大量的生成器，只有当您删除父生成器的句柄时，这些生成器才会被释放。这可能是一种资源浪费，您可以创建无限数量的素数，而无需创建无限数量的生成器。