Неприятное поведение фильтра при реализации "Сита Эратосфена" в python - PullRequest
Новая
       19

Неприятное поведение фильтра при реализации "Сита Эратосфена" в python

7 голосов
/ 03 мая 2019

Я придумал этот код 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: параметр x лямбды получает конкретный аргумент, который является следующим элементом из pickerгенератор.Я не понимаю этого поведения даже после просмотра документации filter.

Запуск 

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

Я получаю: 

2
3
4
5
6

Вместо 

2
3
5
7
11

ОБНОВЛЕНИЕ:

Моя ошибка связана с неправильным пониманием того, как работают лямбды в Python, подробнее об этом здесь .

Добавление дополнительного параметра в лямбду устраняет проблему: 

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

1 Ответ

3 голосов
/ 03 мая 2019

Я думаю, что проблема в том, что вы полагаетесь на локальные переменные, а созданные вами генераторы (используя 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]

Но мне действительно нужно указать, что это чисто образовательное решение, чтобы показать, как все работает. Я бы не предложил использовать это решение для какого-либо производительного кода. Он создает большое количество генераторов внутри, которые освобождаются, только когда вы опускаете дескриптор родительского генератора. Вероятно, это пустая трата ресурсов, и вы можете создать бесконечное количество простых чисел, не создавая бесконечное количество генераторов.

...