时间戳

首页 > 解决方案 > 在 python 中实现“Eratosthenes 筛”时出现问题的过滤器行为

python - 在 python 中实现“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)

标签： pythonpython-3.xalgorithmprimes

解决方案

我认为问题在于您依赖于局部变量，并且您创建（使用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]

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

推荐阅读