Все ответы здесь великолепны; но только один из них (получивший наибольшее количество голосов) относится к , как работает ваш код . Другие касаются генераторов в целом и того, как они работают.
Так что я не буду повторять, что такое генераторы или что делают доходности; Я думаю, что они покрыты хорошими существующими ответами. Однако, потратив несколько часов, пытаясь понять код, подобный вашему, я разобью его, как он работает.
Ваш код пересекает бинарную древовидную структуру. Давайте возьмем это дерево для примера:
5
/ \
3 6
/ \ \
1 4 8
И еще одна более простая реализация обхода дерева двоичного поиска:
class Node(object):
..
def __iter__(self):
if self.has_left_child():
for child in self.left:
yield child
yield self.val
if self.has_right_child():
for child in self.right:
yield child
Код выполнения находится на объекте Tree, который реализует __iter__ следующим образом:
def __iter__(self):
class EmptyIter():
def next(self):
raise StopIteration
if self.root:
return self.root.__iter__()
return EmptyIter()
Оператор while candidates можно заменить на for element in tree; Python перевести это на
it = iter(TreeObj) # returns iter(self.root) which calls self.root.__iter__()
for element in it:
.. process element ..
Поскольку функция Node.__iter__ является генератором, код внутри нее выполняется за итерацию. Таким образом, исполнение будет выглядеть так:
- Корневой элемент является первым; проверить, не осталось ли у него потомков, и
for повторить их (назовем его it1, потому что это первый объект итератора)
- у него есть ребенок, поэтому
for выполняется. for child in self.left создает новый итератор из self.left, который сам является объектом Node (it2)
- Та же логика, что и у 2, и создается новый
iterator (it3)
- Теперь мы достигли левого конца дерева.
it3 не имеет левых детей, поэтому оно продолжается и yield self.value
- При следующем вызове
next(it3) он вызывает StopIteration и существует, поскольку не имеет правых потомков (доходит до конца функции, ничего не возвращая)
it1 и it2 все еще активны - они не исчерпаны, и вызов next(it2) даст значения, а не повысит StopIteration- Теперь мы вернулись к контексту
it2 и вызываем next(it2), который продолжается там, где он остановился: сразу после оператора yield child. Поскольку у него больше нет левых потомков, он продолжается и дает self.val.
Подвох здесь в том, что каждая итерация создает субтераторы для обхода дерева и содержит состояние текущего итератора. Как только он достигает конца, он пересекает стек, и значения возвращаются в правильном порядке (сначала наименьшее значение доходности).
Ваш пример кода сделал что-то похожее в другой технике: он заполнил одноэлементный список для каждого потомка, затем на следующей итерации выдает его и запускает код функции для текущего объекта (отсюда self).
Надеюсь, это немного повлияло на эту легендарную тему. Я потратил несколько часов на то, чтобы понять этот процесс.