Python итератор через дерево со списком детей

Question

Я не совсем понимаю итераторы Python, У меня есть объект со списком детей, и я хочу перебрать эту структуру. Я хочу получить то же поведение, что и с функцией printall, но с итератором.

    class t:
            def __init__(self, i):
                    self.l = []
                    self.a = 0
                    for ii in range(i):
                            self.a = ii
                            self.l.append(t(i-1))

            def __iter__(self):
                    return self

            def next(self):
                    for i in self.l:
                            yield i.__iter__()
                    yield self

            def printall(self):
                    for i in self.l:
                            i.printall()
                    print self.a

надеюсь, хватит информации, спасибо

редактирование:

я просто хочу иметь возможность перебирать все листья дерева и что-то делать с объектом, т.е. когда у меня есть экземпляр

    bla = t(3) 

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

    for x in bla:
            print x.a

например. я хочу быть в состоянии что-то с каждым х, мне просто нужно обратиться к каждому ребенку один раз

Answer 1

Звучит так, будто вы хотите, чтобы итератор действовал как обход дерева. Изучите модуль itertools, и вы действительно сможете ходить по местам.

from itertools import chain, imap

class t:
  def __init__(self, value):
    self.value = value
    self.children = []
  def __iter__(self):
    "implement the iterator protocol"
    for v in chain(*imap(iter, self.children)):
      yield v
    yield self.value

root = t(0)
root.children.append(t(1))
root.children.append(t(2))
root.children[1].children.append(t(3))
print list(iter(root))   # -> [1, 3, 2, 0]
print list(iter(root.children[1]))  # -> [3, 2]

РЕДАКТИРОВАТЬ : Ниже первоначально принятая реализация. У него проблемы с производительностью; Я бы удалил его, но, кажется, неправильно удалять контент, который был принятым ответом. Он будет полностью проходить через всю структуру, создавая O(N*log[M](N)) объекты-генераторы (для сбалансированного дерева с коэффициентом ветвления M, содержащего N всего элементов), прежде чем будут получены какие-либо значения. Но он дает желаемый результат с помощью простого выражения.

(Приведенная выше реализация посещает области дерева по требованию и имеет только O(M+log[M](N)) объектов-генераторов в памяти за раз. В обеих реализациях ожидаются только уровни O(log[M](N)) вложенных генераторов.)

from itertools import chain

def isingle(item):
  "iterator that yields only a single value then stops, for chaining"
  yield item

class t:
  # copy __init__ from above
  def __iter__(self):
    "implement the iterator protocol"
    return chain(*(map(iter, self.children) + [isingle(self.value)]))

Answer 2

Из кода, который вы опубликовали, ясно, что вам не хватает того, что делает генератор , и как __iter__ и next должны вести себя

Итак, начнем с протокола итератора. объект является итеративным, если он возвращает итератор при вызове его метода __iter__, а итератор - это объект, имеющий метод next, который можно вызывать ноль или более раз и в конечном итоге должен вызвать StopIteration.

Для некоторых видов объектов весьма свойственно быть их собственными итераторами (которые имеют __iter__ return self), но обычно это ограничивается объектами, которые каким-то образом сами представляют позицию внутри чего-либо. Например, встроенный объект file является собственным итератором, поскольку файлы имеют внутреннюю позицию поиска (которой вы можете манипулировать с помощью file.seek() и file.tell()). Другие объекты, которые представляют совокупность коллекции, например list, возвращают что-то отличное от себя.

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

Что приводит нас к генераторам. Когда обычная функция содержит оператор yield, она автоматически вообще не является функцией, а является генератором. Разница в том, что когда вы вызываете функцию, выполняется ее тело (и, возможно, возвращает значение). Когда вы вызываете генератор, он немедленно возвращается, не выполняя тело вообще; вместо этого вы получаете итератор ! когда вы повторяете это, вызывается тело функции; переход к следующему yield каждый раз, пока он, наконец, не вернется.

Итак, все вместе,

class t:
    def __init__(self):
        self.l = []
        self.a = 0

    def __iter__(self):
        # first, yield everthing every one of the child nodes would yield.
        for child in self.l:
            for item in child:
                # the two for loops is because there's multiple children, and we need to iterate
                # over each one.
                yield item

        # finally, yield self
        yield self

Но поскольку мы выполняем итерацию последовательности итераторов (а также еще одной вещи, self), itertools.chain, как в принятом ответе, действительно имеет большой смысл.

Answer 3

Мое первое предложение - изменить название вашего класса на более понятное после PEP-8 . Было немного сложно управлять именем класса, таким как t:

class Tree:
    def __init__(self, i):
        self.l = []
        self.a = 0
        for ii in range(i):
            self.a = ii
            self.l.append(Tree(i-1))

Теперь вы должны изменить метод __iter__(), чтобы он возвращал следующий элемент в self, а не self сам - без каламбура :) Метод __iter__() должен возвращать итератор для исходного объекта, а не сам объект:

def __iter__(self):
    return next(self)

Теперь самое сложное: метод next(). Мне всегда трудно писать рекурсивные итераторы, но это не так уж и невозможно: для каждого дочернего элемента, выполнить итерацию и получить повторное значение:

def next(self):
    for i in self.l:
        for ii in i:
            yield ii
    yield self

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

Теперь ваша printall() функция должна работать без сбоев:

if __name__ == "__main__":
t = Tree(6)
t.printall()

Некоторые заключительные соображения:

• Всегда заставляйте ваши классы расширять object:

  Дерево классов (объект) ::

• Могу поспорить, что вы хотите написать __init__() метод, подобный приведенному ниже:

  def __init__(self, i):
      self.l = []
      self.a = i
      for ii in range(i):
          self.l.append(Tree(i-1))
  

• Раствор Wberry лучше, потому что он более лаконичен и, возможно, более эффективен. Тем не менее, я думаю, что ОП изучает деревья, рекурсию и т. Д., Поэтому я подумал, что более жестко закодированное решение было бы поучительно:)