Неожиданное поведение с итераторами

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

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 в 1-й итерации, L как L2 во 2-й итерации и т. Д.

• В 1-й итерации 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, чьи значения рассчитываются только по требованию. Таким образом, во 2-й итерации, когда выполняется prime=next(L1), только одно значение вычисляется из L. Теперь лямбда использует простое число как 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 гг lds 4. Таким образом, вычисление значения, которое должно быть получено с помощью L2 4%3!=0, оценивается как True, поэтому prime=next(L2) равно 4.

Примените те же логи c для дальнейшего итераций, которые вы найдете 5,6,7,8,9 ... будут получены в следующих итерациях.

Answer 2

Вы используете переменную prime в своей лямбде, которая является ссылкой, которую вы наследуете от включающей области видимости. Когда ваш код оценивает лямбду, он будет использовать любое значение, связанное с этой ссылкой, в области, от которой эта ссылка унаследована. Когда вы не используете tee и не оцениваете список, все лямбда-функции идентичны и используют одинаковое значение для prime.

tee работает, просто сохраняя результаты в списке и передавая их вам из этого списка при повторном запросе позже, поэтому для каждого значения prime он фактически применяет фильтр ко всем значениям с L

Это можно исправить, связав prime в области действия lambda, передав его в качестве аргумента со значением по умолчанию. Это сохраняет это значение как часть функционального объекта, и тогда ссылка prime является локальной ссылкой на это сохраненное значение.

Answer 3

Как насчет следующего? Обычно лучше использовать выражения генератора, чем карту / фильтр / уменьшение.

#!/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)