迭代器的意外行为

Question

我尝试用迭代器实现埃拉托色尼筛法（因为我想用 python 更深入地了解函数式编程）。遗憾的是发生了一些意想不到的行为。您可以在此视频中看到它：https://imgur.com/gallery/XfXFw4a

这是我的代码：

def sieve_primes(stop=10):
    L = (x for x in range(2, stop+1))
    while True:
        prime = next(L)
        L = filter(lambda x: x % prime != 0 or x == prime, L)
        #L, M = itertools.tee(L)
        #print(list(M))
        yield prime

当两个注释行被取消注释时，它工作（吐出一个具有所需素数的迭代器对象）。否则，它只是遍历每个数字。

期待您的回答:) 谢谢！

Answer 1

下面的怎么样？你通常最好使用生成器表达式而不是 map/filter/reduce.

#!/usr/bin/env python3


def sieve_primes(stop=100):
    primes = []
    for candidate in range(2, stop+1):
        if not any(candidate % prime == 0 for prime in primes):
            primes.append(candidate)
            yield candidate


for prime in sieve_primes():
    print(prime)

Answer 2

您正在 lambda 中使用变量 prime，这是您从封闭范围继承的引用。当您的代码对 lambda 求值时，它将使用绑定到引用所继承范围内的该引用的任何值。当您不使用 tee 和评估列表时，所有 lambda 函数都是相同的，并且对 prime 使用相同的值。

tee 的工作原理是将结果存储在一个列表中，并在您稍后再次询问时从该列表中将结果提供给您，因此对于 prime 的每个值，它实际上将过滤器应用于所有来自 L

的值

您可以通过将 prime 作为具有默认值的参数传递到 lambda 的范围内来解决此问题。这将该值保存为函数对象的一部分，然后引用 prime 是对该存储值的本地引用。

Answer 3

def sieve_primes(stop=10):
    L = (x for x in range(2, stop+1))
    while True:
        prime = next(L)
        L = filter(lambda x: x % prime != 0 or x == prime, L)
        yield prime

您的代码中到底发生了什么，在下面逐次迭代给出。为了方便，我在第一次迭代中将 L 表示为 L1，在第二次迭代中将 L 表示为 L2，依此类推。

在第一次迭代中 prime=next(L) 为 2（如预期）。 L1=filter(lambda x: x % prime != 0 or x == prime, L)（L 的值是延迟计算的，即仅根据需要计算的值。yield prime 将产生 2 预期。
在第 2 次迭代中 prime=next(L1)。棘手的部分来了。 L1 是 filter object，其值仅按需计算。因此，在执行 prime=next(L1) 时的第 2 次迭代中，仅从 L 计算出一个值。现在 lambda 使用质数作为 2 并计算一个值 3 (3%2!=0) 现在是 prime。 L2=filter(lambda x: x % prime != 0 or x == prime, L1)（L2 的值是延迟计算的，即仅按需计算的值。现在您 yield prime 将产生 3。
在第 3 次迭代中 prime=next(L2)。现在事情变得有点复杂了。要从 L2 中获得一个值，您需要计算 L1 的一个值，要计算一个值 L1，您需要计算一个值 L。如果你没记错的话，L 现在将产生 4，L1 现在将使用它来产生一个值。但最近提到 prime 的是 3。 4%3!=0 的计算结果为 True。因此，L1 产生 4。因此，计算由 L2 产生的值 4%3!=0 被评估为 True 所以 prime=next(L2) 是 4.

对进一步的迭代应用相同的逻辑，您会发现 5,6,7,8,9... 将在进一步的迭代中产生。

迭代器的意外行为

Unexpected behavior with iterators

python

iterator

functional-programming

sieve-of-eratosthenes

python-3.x