Python Language
Генераторы

Вступление

Синтаксис

• выход <expr>
• выход из <expr>
• <var> = yield <expr>
• следующий ( <iter> )

итерация

Объект-генератор поддерживает протокол итератора . То есть он предоставляет метод next() ( __next__() в Python 3.x), который используется для выполнения его выполнения, и его метод __iter__ возвращает себя. Это означает, что генератор может использоваться в любой конструкции языка, которая поддерживает общие повторяющиеся объекты.

# naive partial implementation of the Python 2.x xrange()
def xrange(n):
    i = 0
    while i < n:
        yield i
        i += 1

# looping
for i in xrange(10):
    print(i)  # prints the values 0, 1, ..., 9

# unpacking
a, b, c = xrange(3)  # 0, 1, 2

# building a list
l = list(xrange(10))  # [0, 1, ..., 9]

Функция next ()

next() встроенный - удобная оболочка, которая может использоваться для получения значения от любого итератора (включая итератор генератора) и предоставления значения по умолчанию в случае исчерпания итератора.

def nums():
    yield 1
    yield 2
    yield 3
generator = nums()

next(generator, None)  # 1
next(generator, None)  # 2
next(generator, None)  # 3
next(generator, None)  # None
next(generator, None)  # None
# ...

Синтаксис next(iterator[, default]) . Если итератор заканчивается и передается значение по умолчанию, оно возвращается. Если по умолчанию не было StopIteration , StopIteration поднимается.

Отправка объектов в генератор

Помимо получения значений от генератора, можно отправить объект генератору с помощью метода send() .

def accumulator():
    total = 0
    value = None
    while True:
        # receive sent value
        value = yield total
        if value is None: break
        # aggregate values
        total += value

generator = accumulator()

# advance until the first "yield"
next(generator)      # 0

# from this point on, the generator aggregates values
generator.send(1)    # 1
generator.send(10)   # 11
generator.send(100)  # 111
# ...

# Calling next(generator) is equivalent to calling generator.send(None)
next(generator)      # StopIteration

Здесь происходит следующее:

• Когда вы сначала вызываете next(generator) , программа переходит к первому оператору yield и возвращает значение total в этой точке, которое равно 0. Выполнение генератора приостанавливается в этой точке.
• Когда вы вызываете generator.send(x) , интерпретатор принимает аргумент x и делает его возвращаемым значением последнего оператора yield , которому присваивается value . Затем генератор выполняется, как обычно, до тех пор, пока он не выдает следующее значение.
• Когда вы, наконец, вызываете next(generator) , программа рассматривает это так, как будто вы отправляете None в генератор. В None нет ничего особенного, однако в этом примере используется None как специальное значение, чтобы попросить генератор остановиться.

Выражения генератора

Можно создать итераторы генератора, используя синтаксис, подобный пониманию.

generator = (i * 2 for i in range(3))

next(generator)  # 0
next(generator)  # 2
next(generator)  # 4
next(generator)  # raises StopIteration

Если функции не обязательно нужно передавать список, вы можете сохранить на символах (и улучшить читаемость), разместив выражение генератора внутри вызова функции. Скобки из вызова функции неявно делают ваше выражение выражением генератора.

sum(i ** 2 for i in range(4))  # 0^2 + 1^2 + 2^2 + 3^2 = 0 + 1 + 4 + 9 = 14

Кроме того, вы сохраните память, потому что вместо того, чтобы загружать весь список, который вы повторяете ( [0, 1, 2, 3] в приведенном выше примере), генератор позволяет Python использовать значения по мере необходимости.

Вступление

Выражения генератора аналогичны выражениям , словарю и множеству понятий, но заключены в круглые скобки. Скобки не обязательно должны присутствовать, когда они используются в качестве единственного аргумента для вызова функции.

expression = (x**2 for x in range(10))

В этом примере генерируются 10 первых совершенных квадратов, включая 0 (в которых x = 0).

Функции генератора похожи на обычные функции, за исключением того, что они имеют одно или несколько yield операторов в своем теле. Такие функции не могут return какие-либо значения (однако пустые return s разрешены, если вы хотите остановить генератор раньше).

def function():
    for x in range(10):
        yield x**2

Эта функция генератора эквивалентна предыдущему выражению генератора, он выводит то же самое.

Примечание : все выражения генератора имеют свои собственные эквивалентные функции, но не наоборот.

Выражение генератора может использоваться без круглых скобок, если оба скобки будут повторяться иначе:

sum(i for i in range(10) if i % 2 == 0)   #Output: 20
any(x = 0 for x in foo)                   #Output: True or False depending on foo
type(a > b for a in foo if a % 2 == 1)    #Output: <class 'generator'>

Вместо:

sum((i for i in range(10) if i % 2 == 0))
any((x = 0 for x in foo))
type((a > b for a in foo if a % 2 == 1))

Но нет:

fooFunction(i for i in range(10) if i % 2 == 0,foo,bar)
return x = 0 for x in foo
barFunction(baz, a > b for a in foo if a % 2 == 1)

Вызов функции генератора создает объект-генератор , который позже может быть повторен. В отличие от других типов итераторов, объекты генератора могут перемещаться только один раз.

g1 = function()
print(g1)  # Out: <generator object function at 0x1012e1888>

Обратите внимание, что тело генератора не выполняется сразу: когда вы вызываете function() в приведенном выше примере, он немедленно возвращает объект-генератор, не выполняя даже первого оператора печати. Это позволяет генераторам потреблять меньше памяти, чем функции, которые возвращают список, и позволяет создавать генераторы, которые производят бесконечно длинные последовательности.

По этой причине генераторы часто используются в науках о данных и в других контекстах, связанных с большими объемами данных. Другим преимуществом является то, что другой код может сразу использовать значения, генерируемые генератором, не дожидаясь завершения полной последовательности.

Однако, если вам нужно использовать значения, вырабатываемые генератором более одного раза, и если их генерация стоит больше, чем хранение, лучше сохранить заданные значения в виде list чем повторять генерации последовательности. Подробнее см. «Сброс генератора» ниже.

Обычно объект-генератор используется в цикле или в любой функции, которая требует итерации:

for x in g1:
    print("Received", x)

# Output:
# Received 0
# Received 1
# Received 4
# Received 9
# Received 16
# Received 25
# Received 36
# Received 49
# Received 64
# Received 81

arr1 = list(g1)
# arr1 = [], because the loop above already consumed all the values.
g2 = function()
arr2 = list(g2)  # arr2 = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Поскольку объекты-генераторы являются итераторами, их можно перебирать вручную с помощью функции next() . Это приведет к возврату возвращаемых значений один за другим при каждом последующем вызове.

Под капотом каждый раз, когда вы вызываете next() на генераторе, Python выполняет инструкции в теле функции генератора, пока не попадет в следующий оператор yield . В этот момент он возвращает аргумент команды yield и запоминает точку, в которой это произошло. Вызов next() снова возобновит выполнение с этой точки и продолжит работу до следующей инструкции yield .

Если Python достигнет конца функции генератора, не StopIteration никакого yield , StopIteration исключение StopIteration (это нормально, все итераторы ведут себя одинаково).

g3 = function()
a = next(g3)  # a becomes 0
b = next(g3)  # b becomes 1
c = next(g3)  # c becomes 2
...
j = next(g3)  # Raises StopIteration, j remains undefined

Обратите внимание, что в генераторных объектах Python 2 были .next() которые можно было использовать для итерации по заданным значениям вручную. В Python 3 этот метод был заменен стандартным .__next__() стандартом .__next__() для всех итераторов.

Сброс генератора

Помните, что вы можете только итерации через объекты, генерируемые генератором один раз . Если вы уже выполнили итерацию через объекты в скрипте, любая дальнейшая попытка сделать это даст None .

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

Использование генератора для поиска чисел Фибоначчи

Практический пример использования генератора состоит в том, чтобы перебирать значения бесконечного ряда. Вот пример нахождения первых десяти членов последовательности Фибоначчи .

def fib(a=0, b=1):
    """Generator that yields Fibonacci numbers. `a` and `b` are the seed values"""
    while True:
        yield a
        a, b = b, a + b

f = fib()
print(', '.join(str(next(f)) for _ in range(10)))

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Бесконечные последовательности

Генераторы могут использоваться для представления бесконечных последовательностей:

def integers_starting_from(n):
    while True:
        yield n
        n += 1

natural_numbers = integers_starting_from(1)

Бесконечная последовательность чисел, как указано выше, также может быть сгенерирована с помощью itertools.count . Вышеприведенный код можно записать ниже

natural_numbers = itertools.count(1)

Вы можете использовать генераторные концепции для бесконечных генераторов для создания новых генераторов:

multiples_of_two = (x * 2 for x in natural_numbers)
multiples_of_three = (x for x in natural_numbers if x % 3 == 0)

Имейте в виду, что бесконечный генератор не имеет конца, поэтому передача его любой функции, которая будет пытаться потреблять генератор, будет иметь ужасные последствия :

list(multiples_of_two)  # will never terminate, or raise an OS-specific error

Вместо этого используйте методы list / set с range (или xrange для python <3.0):

first_five_multiples_of_three = [next(multiples_of_three) for _ in range(5)] 
# [3, 6, 9, 12, 15]

или используйте itertools.islice() чтобы itertools.islice() итератор на подмножество:

from itertools import islice
multiples_of_four = (x * 4 for x in integers_starting_from(1))
first_five_multiples_of_four = list(islice(multiples_of_four, 5))
# [4, 8, 12, 16, 20]

Обратите внимание, что исходный генератор также обновляется, как и все другие генераторы, поступающие из одного и того же «корня»:

next(natural_numbers)    # yields 16
next(multiples_of_two)   # yields 34
next(multiples_of_four)  # yields 24

Бесконечная последовательность также может повторяться с for -loop . Обязательно включите оператор условного break чтобы в конечном итоге цикл завершился:

for idx, number in enumerate(multiplies_of_two):
    print(number)
    if idx == 9:
        break  # stop after taking the first 10 multiplies of two

Классический пример - числа Фибоначчи

import itertools

def fibonacci():
    a, b = 1, 1
    while True:
        yield a
        a, b = b, a + b

first_ten_fibs = list(itertools.islice(fibonacci(), 10))
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

def nth_fib(n):
    return next(itertools.islice(fibonacci(), n - 1, n))

ninety_nineth_fib = nth_fib(99)  # 354224848179261915075

Учет всех значений из другого итерабельного

def foob(x):
    yield from range(x * 2)
    yield from range(2)

list(foob(5))  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]

def fibto(n):
    a, b = 1, 1
    while True:
        if a >= n: break
        yield a
        a, b = b, a + b

def usefib():
    yield from fibto(10)
    yield from fibto(20)

list(usefib())  # [1, 1, 2, 3, 5, 8, 1, 1, 2, 3, 5, 8, 13]

Сопрограммы

Генераторы могут использоваться для реализации сопрограмм:

# create and advance generator to the first yield
def coroutine(func):
    def start(*args,**kwargs):
        cr = func(*args,**kwargs)
        next(cr)
        return cr
    return start

# example coroutine
@coroutine
def adder(sum = 0):
    while True:
        x = yield sum
        sum += x

# example use
s = adder()
s.send(1) # 1
s.send(2) # 3

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

Выход с рекурсией: рекурсивно перечисление всех файлов в каталоге

Сначала импортируйте библиотеки, которые работают с файлами:

from os import listdir
from os.path import isfile, join, exists

Вспомогательная функция для чтения только файлов из каталога:

def get_files(path):
    for file in listdir(path):
        full_path = join(path, file)
        if isfile(full_path):
            if exists(full_path):
                yield full_path

Другая вспомогательная функция для получения только подкаталогов:

def get_directories(path):
    for directory in listdir(path):
        full_path = join(path, directory)
        if not isfile(full_path):
            if exists(full_path):
                yield full_path

Теперь используйте эти функции для рекурсивного получения всех файлов в каталоге и во всех его подкаталогах (с использованием генераторов):

def get_files_recursive(directory):
    for file in get_files(directory):
        yield file
    for subdirectory in get_directories(directory):
        for file in get_files_recursive(subdirectory): # here the recursive call
            yield file

Эта функция может быть упрощена, используя yield from :

def get_files_recursive(directory):
    yield from get_files(directory)
    for subdirectory in get_directories(directory):
        yield from get_files_recursive(subdirectory)

Итерация по генераторам параллельно

Для параллельной обработки нескольких генераторов используйте встроенный zip :

for x, y in zip(a,b):
    print(x,y)

Результаты в:

1 x
2 y
3 z

В python 2 вместо этого вы должны использовать itertools.izip . Здесь мы также видим, что все zip функции дают кортежи.

Обратите внимание, что zip остановит итерацию, как только закончится один из повторяющихся элементов. Если вы хотите выполнить итерацию до тех пор, пока она будет самой длинной, используйте itertools.zip_longest() .

Рефакторинг для составления списка

Предположим, у вас есть сложный код, который создает и возвращает список, начиная с пустого списка и многократно добавляя его:

def create():
    result = []
    # logic here...
    result.append(value) # possibly in several places
    # more logic...
    return result # possibly in several places

values = create()

Когда нецелесообразно заменять внутреннюю логику пониманием списка, вы можете превратить всю функцию в генератор на месте, а затем собрать результаты:

def create_gen():
    # logic...
    yield value
    # more logic
    return # not needed if at the end of the function, of course

values = list(create_gen())

Если логика рекурсивна, используйте yield from для включения всех значений из рекурсивного вызова в результат «сплющенного»:

def preorder_traversal(node):
    yield node.value
    for child in node.children:
        yield from preorder_traversal(child)

поиск

next функция полезна даже без итерации. Передача выражения генератора для next - это быстрый способ поиска первого вхождения элемента, соответствующего некоторому предикату. Процедурный код

def find_and_transform(sequence, predicate, func):
    for element in sequence:
        if predicate(element):
            return func(element)
    raise ValueError

item = find_and_transform(my_sequence, my_predicate, my_func)

можно заменить на:

item = next(my_func(x) for x in my_sequence if my_predicate(x))
# StopIteration will be raised if there are no matches; this exception can
# be caught and transformed, if desired.

Для этой цели может быть желательно создать псевдоним, например first = next , или функцию-оболочку для преобразования исключения:

def first(generator):
    try:
        return next(generator)
    except StopIteration:
        raise ValueError