iterador de python a través del árbol con la lista de hijos

Question

no entiendo todos los iteradores de python, tengo un objeto con una lista de hijos, y quiero iterar a través de esta estructura. Quiero obtener el mismo comportamiento que con la función printall pero con un iterador.

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 

esa es la esperanza suficiente información, gracias

edición:

sólo quiero ser capaz de recorrer todas las hojas del árbol y hacer algo con el objeto, es decir, cuando tengo una instancia

bla = t(3) 

quiero ser capaz de ir a través de cada nodo con

for x in bla: 
      print x.a 

por ejemplo. quiero poder algo con cada x, solo tengo que acceder a todos los niños una vez

Answer 1

Parece que desea que el iterador actúe como un cruce de árbol. Estudia el módulo itertools y realmente puedes ir a lugares.

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] 

EDITAR: A continuación se muestra la ejecución inicialmente aceptado. Tiene un problema de rendimiento; Lo eliminaría, pero parece incorrecto eliminar el contenido que fue una respuesta aceptada. Atravesará por completo toda la estructura, creando objetos generadores O(N*log[M](N)) (para un árbol equilibrado con factor de ramificación M que contenga N elementos totales), antes de arrojar ningún valor. Pero sí produce el resultado deseado con una expresión simple.

(La implementación anterior visitas áreas del árbol de la demanda y tiene sólo objetos O(M+log[M](N)) generador en la memoria a la vez. En ambas implementaciones, sólo se esperan O(log[M](N)) niveles de generadores anidadas.)

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

Mi primera La sugerencia es cambiar el nombre de su clase con una más clara siguiendo el PEP-8. Fue un poco difícil de manejar un nombre de clase como 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)) 

Ahora, usted debe cambiar el método __iter__() para devolver el siguiente elemento de self, no self en sí - sin juego de palabras :) El método debe __iter__() devolver un iterador al objeto original, no el objeto en sí mismo:

def __iter__(self): 
    return next(self) 

Ahora viene la parte difícil: el método next(). Siempre me resulta difícil escribir una iteradores recursivas, pero esto no es que imposible: para cada niño, iterar sobre ella y cedo el valor iterado:

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

Dado que el método es recursivo, que se encarga de dar lugar a todos los descendientes . Cuando se llama al método next() en un nodo hoja (un nodo sin hijos), simplemente devolverá el nodo. OTOH, cuando se llama a un nodo con hijos, se llamará a sí mismo para cada uno de los hijos y arrojará el valor devuelto.Esto significa que será llamado por los hijos de los niños y así sucesivamente hasta los nodos de las hojas. Después de ser llamado por todos los descendientes de un nodo, lo que significa que se produjeron todos los descendientes, debe producir su propio valor, por lo que debe ceder el nodo original.

Ahora su función printall() debería funcionar sin problemas:

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

Algunas consideraciones finales:

• siempre de que sus clases se extienden al object:

  árbol de la clase (objeto) ::

• I apuesta que desea escribir un método __init__() como la siguiente:

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

• solución El wberry es mejor porque es más conciso y, probablemente, más eficiente. Sin embargo, creo que el PO está estudiando árboles, recursividad, etc, así que pensé una solución más codificado sería instructivo :)

Answer 3

A partir del código que has publicado, está claro que lo que se echa en falta es lo que un generador hace y cómo __iter__ y next se supone que se comportan

Así que vamos a empezar con el protocolo de iteración. un objeto es iterable si devuelve un iterador cuando se llama a su método __iter__, y un iterador es un objeto que tiene un método next, que se puede llamar cero o más veces y debería elevar StopIteration.

No es inusual que ciertos tipos de objetos sean sus propios iteradores (que tienen __iter__ return self), pero esto generalmente se limita a objetos que de alguna manera representan una posición dentro de algo. Por ejemplo, el objeto incorporado file es su propio iterador, porque los archivos tienen una posición de búsqueda intrínseca (que puede manipular con file.seek() y file.tell()). Otros objetos, que representan la totalidad de una colección, como list, devuelven algo que no sean ellos mismos.

Por lo tanto, su árbol realmente suena más a este último que a lo anterior; No tiene un atributo de posición que represente en qué nodo está; son todos los nodos al mismo tiempo, por lo que probablemente no debe tener un método next(); __iter__ necesita devolver algo más.

Lo que nos lleva a los generadores. Cuando una función normal contiene una declaración yield, automáticamente no es una función en absoluto, es un generador. La diferencia es que cuando llamas a una función, su cuerpo se ejecuta (y posiblemente devuelve un valor). Cuando llamas a un generador, regresa de manera inmediata, sin ejecutar el cuerpo en absoluto; en cambio, obtienes un iterador! cuando itera sobre eso, se llama al cuerpo de la función; avanzando al siguiente yield cada vez hasta que finalmente regrese.

lo tanto, poner todo junto,

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 

Pero, puesto que lo que estamos haciendo es la iteración de una secuencia de iteradores (y también una cosa más, uno mismo), itertools.chain como en la respuesta aceptada, de verdad Tiene mucho sentido.