0,0
рейтинг
14 ноября 2011 в 15:41

Разработка → Как работает yield перевод

На StackOverflow часто задают вопросы, подробно освещённые в документации. Ценность их в том, что на некоторые из них кто-нибудь даёт ответ, обладающий гораздо большей степенью ясности и наглядности, чем может себе позволить документация. Этот — один из них.

Вот исходный вопрос:
Как используется ключевое слово yield в Python? Что оно делает?

Например, я пытаюсь понять этот код (**):
def _get_child_candidates(self, distance, min_dist, max_dist):
    if self._leftchild and distance - max_dist < self._median:
        yield self._leftchild
    if self._rightchild and distance + max_dist >= self._median:
        yield self._rightchild

Вызывается он так:
result, candidates = list(), [self]
while candidates:
    node = candidates.pop()
    distance = node._get_dist(obj)
    if distance <= max_dist and distance >= min_dist:
        result.extend(node._values)
        candidates.extend(node._get_child_candidates(distance, min_dist, max_dist))
        return result


Что происходит при вызове метода _get_child_candidates? Возвращается список, какой-то элемент? Вызывается ли он снова? Когда последующие вызовы прекращаются?

** Код принадлежит Jochen Schulz (jrschulz), который написал отличную Python-библиотеку для метрических пространств. Вот ссылка на исходники: http://well-adjusted.de/~jrschulz/mspace/


А вот ответ:

Итераторы


Для понимания, что делает yield, необходимо понимать, что такое генераторы. Генераторам же предшествуют итераторы. Когда вы создаёте список, вы можете считывать его элементы один за другим — это называется итерацией:
>>> mylist = [1, 2, 3]
>>> for i in mylist :
...    print(i)
1
2
3

Mylist является итерируемым объектом. Когда вы создаёте список, используя генераторное выражение, вы создаёте также итератор:
>>> mylist = [x*x for x in range(3)]
>>> for i in mylist :
...    print(i)
0
1
4

Всё, к чему можно применить конструкцию «for… in...», является итерируемым объектом: списки, строки, файлы… Это удобно, потому что можно считывать из них значения сколько потребуется — однако все значения хранятся в памяти, а это не всегда желательно, если у вас много значений.

Генераторы


Генераторы это тоже итерируемые объекты, но прочитать их можно лишь один раз. Это связано с тем, что они не хранят значения в памяти, а генерируют их на лету:
>>> mygenerator = (x*x for x in range(3))
>>> for i in mygenerator :
...    print(i)
0
1
4

Всё то же самое, разве что используются круглые скобки вместо квадратных. НО: нельзя применить конструкцию for i in mygenerator второй раз, так как генератор может быть использован только единожды: он вычисляет 0, потом забывает про него и вычисляет 1, завершаяя вычислением 4 — одно за другим.

Yield


Yield это ключевое слово, которое используется примерно как return — отличие в том, что функция вернёт генератор.
>>> def createGenerator() :
...    mylist = range(3)
...    for i in mylist :
...        yield i*i
...
>>> mygenerator = createGenerator() # создаём генератор
>>> print(mygenerator) # mygenerator является объектом!
<generator object createGenerator at 0xb7555c34>
>>> for i in mygenerator:
...     print(i)
0
1
4

В данном случае пример бесполезный, но это удобно, если вы знаете, что функция вернёт большой набор значений, который надо будет прочитать только один раз.

Чтобы освоить yield, вы должны понимать, что когда вы вызываете функцию, код внутри тела функции не исполняется. Функция только возвращает объект-генератор — немного мудрёно :-)

Ваш код будет вызываться каждый раз, когда for обращается к генератору.

Теперь трудная часть:

В первый запуск вашей функции, она будет исполняться от начала до того момента, когда она наткнётся на yield — тогда она вернёт первое значение из цикла. На каждый следующий вызов будет происходить ещё одна итерация написанного вами цикла, возвращаться будет следующее значение — и так пока значения не кончатся.

Генератор считается пустым, как только при исполнении кода функции не встречается yield. Это может случиться из-за конца цикла, или же если не выполняется какое-то из условий «if/else».

Объяснение кода из исходного вопроса


Генератор:
# Создаём метод узла, который будет возвращать генератор
def _get_child_candidates(self, distance, min_dist, max_dist):

  # Этот код будет вызываться при каждом обращении к объекту-генератору:

  # Если у узла есть потомок слева
  # И с расстоянием всё в порядке, возвращаем этого потомка
  if self._leftchild and distance - max_dist < self._median:
                yield self._leftchild

  # Если у узла есть потомок справа
  # И с расстоянием всё в порядке, возвращаем этого потомка
  if self._rightchild and distance + max_dist >= self._median:
                yield self._rightchild

  # Если исполнение дошло до этого места, генератор считается пустым

Вызов:
# Создаём пустой список и список со ссылкой на текущий объект
result, candidates = list(), [self]

# Входим в цикл по кандидатам (в начале там только один элемент)
while candidates:

    # Вытягиваем последнего кандидата и удаляем его из списка
    node = candidates.pop()

    # Вычисляем расстояние между объектом и кандидатом
    distance = node._get_dist(obj)

    # Если с расстоянием всё в порядке, добавляем в результат
    if distance <= max_dist and distance >= min_dist:
        result.extend(node._values)

    # Добавляем потомков кандидата в список кандидатов,
    # чтобы цикл продолжал исполняться до тех пор,
    # пока не обойдёт всех потомков потомков <...> кандидата
    candidates.extend(node._get_child_candidates(distance, min_dist, max_dist))

return result

Этот код содержит несколько меньших частей:
  • Цикл итерируется по списку, но списко расширяется во время итерации :-) Это лаконичный способ обойти все сгрупиррованные данные, зоть это и немного опасно, так как может обернуться бесконечным циклом. В таком случае candidates.extend(node._get_child_candidates(distance, min_dist, max_dist)) исчерпает все значения генератора, но при этом продолжит создавать новые объекты-генераторы, которые будут давать значения, отличные от предыдущих (поскольку применяются к к другим узлам).
  • Метод extend() это метод объекта списка, который ожидает на вход что-нибудь итерируемое и добавляет его значения к списку.

Обычно мы передаём ему список:
>>> a = [1, 2]
>>> b = [3, 4]
>>> a.extend(b)
>>> print(a)
[1, 2, 3, 4]

Но в нашем коде он принимает генератор, что хорошо по следующим причинам:
  • Нет необходимости читать значения дважды.
  • Может случиться так, что потомков много и хранить их всех в памяти не хочется.

И это работает, потому что Python всё равно, является аргумент этого метода списком или нет. Python ожидает итерируемый объект, так что это сработает со строками, списками, кортежами и генераторами! Это называется утиной типизацией и является одной из причин, почему Python так крут. Но это другая история для другого вопроса…

Читатель может остановиться здесь, или же прочитать ещё немного о продвинутом использовании генераторов:

Контроль за исчерпанием генератора


>>> class Bank(): # создаём банк, строящий торговые автоматы (ATM — Automatic Teller Machine)
...    crisis = False
...    def create_atm(self) :
...        while not self.crisis :
...            yield "$100"
>>> hsbc = Bank() # когда всё хорошо, можно получить сколько угодно денег с торгового автомата
>>> corner_street_atm = hsbc.create_atm()
>>> print(corner_street_atm.next())
$100
>>> print(corner_street_atm.next())
$100
>>> print([corner_street_atm.next() for cash in range(5)])
['$100', '$100', '$100', '$100', '$100']
>>> hsbc.crisis = True # пришёл кризис, денег больше нет!
>>> print(corner_street_atm.next())
<type 'exceptions.StopIteration'>
>>> wall_street_atm = hsbc.create_atm() # что верно даже для новых автоматов
>>> print(wall_street_atm.next())
<type 'exceptions.StopIteration'>
>>> hsbc.crisis = False # проблема в том, что когда кризис прошёл, автоматы по-прежнему пустые...
>>> print(corner_street_atm.next())
<type 'exceptions.StopIteration'>
>>> brand_new_atm = hsbc.create_atm() # но если построить ещё один, будешь снова в деле!
>>> for cash in brand_new_atm :
...    print cash
$100
$100
$100
$100
$100
$100
$100
$100
$100
...

Это может оказаться полезным для разных целей вроде управления доступом к какому-нибудь ресурсу.

Ваш лучший друг Itertools


Модуль itertools содержит специальные функции для работы с итерируемыми объектами. Желаете продублировать генератор? Соединить два генератора последовательно? Сгруппировать значения вложенных списков в одну строчку? Применить map или zip без создания ещё одного списка?

Просто добавьте import itertools.

Хотите пример? Давайте посмотрим на возможные порядки финиширования на скачках (4 лошади):
>>> horses = [1, 2, 3, 4]
>>> races = itertools.permutations(horses)
>>> print(races)
<itertools.permutations object at 0xb754f1dc>
>>> print(list(itertools.permutations(horses)))
[(1, 2, 3, 4),
 (1, 2, 4, 3),
 (1, 3, 2, 4),
 (1, 3, 4, 2),
 (1, 4, 2, 3),
 (1, 4, 3, 2),
 (2, 1, 3, 4),
 (2, 1, 4, 3),
 (2, 3, 1, 4),
 (2, 3, 4, 1),
 (2, 4, 1, 3),
 (2, 4, 3, 1),
 (3, 1, 2, 4),
 (3, 1, 4, 2),
 (3, 2, 1, 4),
 (3, 2, 4, 1),
 (3, 4, 1, 2),
 (3, 4, 2, 1),
 (4, 1, 2, 3),
 (4, 1, 3, 2),
 (4, 2, 1, 3),
 (4, 2, 3, 1),
 (4, 3, 1, 2),
 (4, 3, 2, 1)]


Понимание внутреннего механизма итерации


Итерация это процесс, включающий итерируемые объекты (реализующие метод __iter__()) и итераторы (реализующие __next__()). Итерируемые объекты это любые объекты, из которых можно получить итератор. Итераторы это объекты, позволяющие итерировать по итерируемым объектам.

Больше информации по данному вопросу доступно в статье про то, как работает цикл for.
Перевод: Kevin Samuel
Андрей Смоленский @qrazydraqon
карма
76,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (41)

  • +3
    В избранное, немедленно в избранное!
    P.S. Большое спасибо за понятное объяснение.
    • +4
      Все это очень хорошо описывается в «Learning Python» Mark Lutz, всем кто не читал настоятельно рекомендую
      • –1
        Именно его сейчас читаю.
  • +1
    Спасибо, стало гораздо понятнее.
    Тоже сохранил в избранное.
  • 0
    Кажется, уже было, но в избранном пусть полежит. А то я знаю про них, умею пользоваться, но не использую — в питоне с большим объемом данных не работаю.
    • 0
      Сорри за некропостинг. Это не только с большими данными. К примеру поиск файла с определенными критериями как Вы организовываете?
      1.Очень многие сначала пробегаются по директории рекурсивно, создают список, а потом в for-конструкции берут очередной элемент этого списка, т.е. имя файла и уже работают с ним.
      2. А это можно значительно улучшить тем, что как только нашли имя файла, то вместо сохранения в список, сразу же yield filename.
  • 0
    def node._get_child_candidates — разве это нормально? Скорее всего имелось в виду — def _get_child_candidates
    • 0
      И действительно, что отмечают и в комментариях на SO:
      def anobject.method(): pass is invalid syntax in Python. – J.F. Sebastian Oct 24 '08 at 19:09

      Посмотрел в исходники (http://well-adjusted.de/~jrschulz/mspace/mspace-pysrc.html#VPTree._get_child_candidates) — там тоже такого нет. Непонятно, в общем, откуда автор вопроса такое взял.
      • 0
        Заменил.
  • 0
    Пару месяцев назад разобрался с yield именно благодаря этому топику на stackoverflow.
  • +2
    Смутно вспоминаю, что в документации было написано, что не стоит менять список во время итерации по нему.
    • 0
      Это не совсем модификация списка, это такой хитрый способ перебрать дерево.
      • 0
        Разве? У нас же while по candidates.

        А в теле цикла candidates.extend.
        • 0
          в данном примере нет итерации по списку. ;)
          возможно, чтобы исключить путаницу, авторам нужно было воспользоваться collections.deque для реализации стека, а не list.
          • +2
            Был неправ. Там while candidates и candidates.pop, а не for… in candidates.
            Посмотрел невнимательно. Типичный стек.
  • +4
    Наверное, также стоит добавить, что итерирование завершается за счет выбрасывания исключения StopIteration. Т.е. вот этот код

    for i in gen:
         print i
    

    на самом деле работает как-то так:

    try:
        while True:
            print gen.next()
    catch StopIteration:
        pass
    


    Это важно понимать, если для итерирования генеретора не достаточно констрункции for ... in, и нужно закрутить что-то с while'ом.
    • 0
      Только конечно не catch, а except. )
    • +4
      Еще, в статье не упоминается, что в коде генератора также можно использовать return, но без возвращаемого значения, который воспринимается, как завершение итерирования и аналогичен raise StopIteration
      • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      А насколько в питоне исключения быстро работают? В некоторых языках, например жава, не рекомендуется использовать исключения для штатных ситуаций, потому что это работает не очень быстро. В питоне, получается, такого нет.
      • 0
        Питон не позиционируется как системный язык, а потому в вопросе использования исключений принято исходить из удобства. Ситуация, когда функция возвращает «не успешность» своего выполнения как значение (return) является скорее антипаттерном.
      • 0
  • +4
    Например, через yield генератор может не только возвращать значение, но и принимать произвольный аргумент:

    Более того, это само интересное в yield-е и есть. yield i разжёвывать и смысла особого нет — ну генераторы и генераторы. А вот j = yield i позволяет делать сопроцедуры (coroutines). Которые открывают совершенно новые возможности в Python-е, от цепочек «потребителей» (в смысле, они являются как бы антонимом к «генераторам», но, точно так же, как и генераторы, могут объединяться в цепочки) до кооперативной многозадачности (!!!).

    На эту тему есть хорошая (правда, длинная и на английском) презентация: www.dabeaz.com/coroutines/Coroutines.pdf
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        «А никто не обещал, что будет легко» :)

        На самом деле, метафора generator vs consumer очень хорошо подходит для первого сценария использования.
        Ну, а кооперативная многозадачность… впрочем, вряд ли кому понадобится заниматься ей на таком низком уровне (а не хотя бы на уровне eventlet/gevent).
    • 0
      На основе этого сделан inline callback в асинхронных фреймворках twisted, web tornado.
    • 0
      Шикарная вещь, узнал об этом буквально неделю назад. Понял, что во многих местах нужно было использовать именно g.send() вместо костылей.
    • 0
      вот ещё статья, про использование генераторов для управления задачами: www.kamaelia.org/MiniAxon.html.
  • 0
    Итерация это процесс, включающий итерируемые объекты (реализующие метод __iter__()) и итераторы (реализующие __next__())

    Только не __next_()_, а next().
  • 0
    Отличное изложение, все понятно и по делу.
  • 0
    >Генераторам же предшествуют итераторы.

    Всё никак не могу понять: в теории итераторы и генераторы — это просто множества со схожими свойствами/интерфейсами или одно из них является подмножеством (или наследником, если угодно) другого? Является ли корректным высказывание: «Любой итератор — это генератор»?
    • +2
      Бывают iterators, iterables и generators.
      Iterable (iterable interface) — интерфейс, позволяющий итерироваться (метод next/__next__ и raise StopIteration в конце).
      Iterator — объект с iterable interface.
      Generator — функция, возвращающая iterator.

      The Python Tutorial — Classes
      Building Skills in Python — Iterators and Generators
  • –2
    Да StackOverflow уже не торт, там всякие Димы Маликовы тусуются.
  • –1
    Ужасно!
    В объяснении удалось избежать функциональных замыканий, continuations и сопроцедур!
  • 0
    а в питоне поддерживается возбуждение исключения в месте yield?
    • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Требую мануал по рекурсивным генераторам! :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.