Как yield работает в обходе Inorder с рекурсивным генератором? - PullRequest
Новая
       24

Как yield работает в обходе Inorder с рекурсивным генератором?

0 голосов
/ 27 мая 2019

Я узнал о рекурсивных генераторах и нашел эту программу в сети.

Я использую рекурсивную версию обхода в заказе, но у меня возникают проблемы с пониманием рекурсивного генератора.

В частности, я не могу понять

  1. почему 'yield x' записан в цикле for?
  2. Почему 'yield x' не собирается в окончательном списке?

Я попытался перезаписать генератор и добавил часы, но обнаружил, что рекурсивный вызов выполняется несколько раз «yield x», и он не собирается в конечном результате. 

class Tree:
    def __init__(self, label, left=None, right=None):
        self.label = label
        self.left = left
        self.right = right

    def __repr__(self, level=0, indent="    "):
        s = level*indent + repr(self.label)
        if self.left:
            s = s + "\\n" + self.left.__repr__(level+1, indent)
        if self.right:
            s = s + "\\n" + self.right.__repr__(level+1, indent)
        return s

    def __iter__(self):
        return inorder(self)


def tree(list):
    n = len(list)
    if n == 0:
        return []
    i = n // 2
    return Tree(list[i], tree(list[:i]), tree(list[i + 1:]))





# Recursive Generator
def inorder(t):
    if t:
        for x in inorder(t.left):
            yield x
        yield t.label
        for x in inorder(t.right):
            yield x

Роль доходности х внутри цикла.

Ответы [ 2 ]

0 голосов
/ 28 мая 2019

Может быть, вы не понимаете, как работает генератор?Генератор отличается от итератора, он напрямую не вычисляет достойную коллекцию, он динамически получает все значения.Если результат inorder(t.left) не пройден циклом for, то yield inorder(t.left) вернет весь генератор, созданный для t.left.Поскольку вся ваша функция inorder является генератором.

К сожалению, я не смог найти конкретный документ с описанием.Это описание, основанное на моем опыте.Другие могут внести исправления в мое мнение.Если кто-то может предоставить конкретное официальное описание, можете добавить

0 голосов
/ 27 мая 2019

Не совсем точно, что вы ищете, но, возможно, это что-то вроде этого: 

class Tree:
    def __init__(self, label, left=None, right=None):
        self.label = label
        self.left = left
        self.right = right

    def __repr__(self, level=0, indent="    "):
        s = level*indent + repr(self.label)
        if self.left:
            s = s + "\n" + self.left.__repr__(level+1, indent)
        if self.right:
            s = s + "\n" + self.right.__repr__(level+1, indent)
        return s

    def __iter__(self):
        return inorder(self)


def tree(list):
    n = len(list)
    if n == 0:
        return []
    i = n // 2
    return Tree(list[i], tree(list[:i]), tree(list[i + 1:]))


def inorder(t):
    if t:
        for x in t.left:
            yield x
        yield t.label
        for x in t.right:
            yield x

t = tree("ABCDEFG")
[print(i.label) for i in t]

, который выводит: 

A
B
C
D
E
F
G

С этим кодом вы могли бы вместо этого:

[print('----------\n', i) for i in t]

, который выводит каждый иерархический узел в дереве от A до G.

Редактировать: Если вы спрашиваете, как работает генератор, возможно, этот пример мог быбыть просвещающим: 

>>> def list2gen(lst):
...     for elem in lst:
...             yield str(elem) + '_'
...
>>> print(list2gen([1,2,'7',-4]))
<generator object list2gen at 0x000001B0DEF8B0C0>
>>> print(list(list2gen([1,2,'7',-4])))
['1_', '2_', '7_', '-4_']

Если ваш отладчик ломается несколько раз с выходом, но эти элементы никогда не материализуются в получающемся генераторе, вам придется приписать это ошибкам в отладчике.Я не использовал его для Python более десяти лет;они были заведомо заражены ошибками.В Python парадигма «тест - король» и «избегать ручной отладки», но я с этим не согласен.(Единственная причина, по которой я этого не делаю, это отсутствие замечательных IDE и отладчиков.)

...